728x90 반응형 Study/Algorithm2 [baekjoon] 11729 - 하노이 탑 이동순서(Java) 하노이 탑 이동순서 단계별로 풀어보기 10단계 재귀에 나오는 문제로 재귀로 풀어보자 접근법 제일 큰 원판이 우리가 목표로 하는 3번 장대(to)에 들어가야 순서대로 쌓을 수 있다. 그러기 위해서는 제일 큰 원판의 위에 있는 원판들을 2번 장대(remains)에 올려놓고 제일 큰 원판을 3번 장대에 옮겨야 한다. 케이스 1번장대(from) 2번장대(remains) 3번장대(to) 원판 1개 0개 0개 제일 큰 원판 원판 2개 0개 1개 제일 큰 원판 원판 3개 0개 2개 제일 큰 원판 ... ... ... ... 원판 N개 0개 n-1개 제일 큰 원판 이 이후에 다시 2번 장대에 있는 n - 1개의 원판들을 3번장대로 옮겨주면 된다. 원판을 옮기는 총 횟수 케이스 횟수 원판 1개 1번 원판 2개 제일 큰 .. 2022. 9. 29. [Algorithm] 공간복잡도와 시간복잡도 공간복잡도란? 공간복잡도(Space Complexity)란 프로그램이 실행되고 완료되기까지 필요한 저장공간(memory)의 양을 말한다. 필요한 저장공간은 고정공간과 가변공간으로 나뉜다. 컴퓨터의 성능이 발전하면서 공간복잡도의 중요도는 점차 줄어들고 있다. 그래서 최근에는 시간복잡도를 더 우선하여 프로그래밍을 한다. 고정공간 알고리즘의 실행에 독립적인 공간이다. 단순하게 변수나 상수등 코드를 저장하는 공간이다. 가변공간 알고리즘의 실행에 의존적인 공간이다. 문제를 해결하려는 과정에서 동적으로 필요한 공간이다. S(P) = c + S𝚙(N) c : 고정공간 S𝚙(N) : 가변공간 고정공간 c는 상수이므로 공간복잡도는 가변공간의 크기에 좌우된다. 공간복잡도 계산법 - 빅-오(Big-O) // 1 int x.. 2022. 9. 26. 이전 1 다음 728x90 반응형
