알고리즘3 [백준] 트리 1. 문제 이해하기전위 순회, 중위 순회 순서가 주어지면 후위 순회 순서를 구하는 문제이다. 예전에 동일한 문제를 풀어본 적이 있어서 어떻게 푸는지는 알았다. 근데 시간이 이렇게 오래 걸릴 줄은 몰랐다…2. 이론 세우기우선 전위 순회는 가장 앞에 있는 노드가 루트이다. 또 중위 순회는 루트를 기준으로 왼쪽은 루트의 왼쪽 자식, 오른쪽은 루트의 오른쪽 자식으로 나뉜다. 재귀 함수를 이용해 왼쪽 자식, 오른쪽 자식을 출력한 뒤 루트를 출력하는 함수를 만들면 된다.처음에는 재귀 함수로 전달하는 루트 노드를 노드 번호로 했었는데, 재귀호출 시 전위 순회[후위 순회[루트번호] + 1] 이런 식의 코드가 나오게 되었고 n이 범위를 벗어나는 경우 인덱스 오류가 났다. 이후부터 머리가 너무 아파서 그냥 예외처리 대신 .. 2025. 2. 6. [종만북] DP 돌려깎기 [종만북] 외발 뛰기 (난이도 하, 1권 215 페이지) - 2025.2.21. 문제 이해하기종만북 215p에 나온 문제이다.2. 이론 세우기이동 방향은 아래쪽, 오른쪽뿐이므로 해당 위치에서 재귀를 호출한다.3. 이론 검증하기for문에서 왼쪽 → 오른쪽, 위 → 아래로 순회할 때 정답이 나오는 이유이동 가능한 방향이 왼쪽 → 오른쪽, 위 → 아래 두 방향밖에 없으므로 가로 이동 시 0, 7에 도착하기 위해서는 0, 0과 0, 6 사이 어떤 블럭에서 이동하는 경우밖에 없다. 상하 이동도 동일하다.4. 의사코드 작성하기**- for문 dp**방문 배열을 False로 초기화한다. 0, 0은 시작점이니까 True로 초기화한다. 배열을 순회한다. 현재 위치의 방문 배열이 True라면: 현재 위치에서 오른쪽 이.. 2025. 2. 3. [백준] 2828: 사과 담기 게임 https://www.acmicpc.net/problem/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M=i and i>current-m: #사과가 이미 바구니 안 위치에 있으면 위치이동 없음 continue if current 2023. 7. 31. 이전 1 다음
