히치키치

문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 풀이 중위 순회 : root 왼쪽 자식 - root - root 오른쪽 자식 후위 순회 : root 왼쪽 자식 - root 오른쪽 자식 - root 전위 순회 : root - root 왼쪽 자식 - root 오른쪽 자식 후위 순회 마지막 노드 = 중위 순회의 루트 노드 후위 순회에서 루트를 뽑기 -> 전위 순회에 차례로 붙이기 루트 노드 찾아서 왼쪽 오른쪽 나눠서 재귀 진행 (왼쪽 실행 -> 오른쪽 실행) 예시 후위 순회 :..

문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 dp + dfs dp[x][y] : 지도 arr[x][y]까지 가는 경우의 수 / 방문 상태 기록 dp[x][y]=0 : 지도 arr[x][y]까지 가는 경로 없음 dp[x][y]=>1 : 이전의 방문 경로가 있음. 해당 값에 더해줌 dp[x][y]=-1 : 아직 방문하지 않은 경로 #문제 : https://www.acmicpc.net/problem/1520 import sys inp..

문제 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 요점 큐 : 불 좌표 -> 사람 좌표 BFS 탐색 : 미로 나가기까지 최소 탐색 횟수 사람은 빈칸으로만 이동 가능 #문제: https://www.acmicpc.net/problem/4179 from sys import stdin from collections import deque input = stdin.readline R, C = map(int, input().split()..

문제 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 정리 d 시작 방향 (0 ≤ d ≤ 3) 0) x좌표가 증가하는 방향 (→) 1) y좌표가 감소하는 방향 (↑) 2) x좌표가 감소하는 방향 (←) 3) y좌표가 증가하는 방향 (↓) 세대에 따른 숫자 표현 0:0 1:0 1 2:0 1 2 1 3: 0 1 2 1 2 3 2 1 4: 0 1 2 2 3 3 2 1 2 3 0 3 2 3 2 1 이전 세대의 역방향으로 +1..