투투

https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 접근 만약 O 표시가 없을 때는 특정 위치 (i, j) 까지 이동할 수 있는 경우의 수를 구하기 위해서는 해당 위치의 위쪽과 왼쪽의 경우의 수를 더하면 된다. 왜냐하면 오른쪽과 아래로만 이동할 수 있고 두 방향의 경우의 수를 더하면 해당 위치까지 이동할 수 있는 경우의 수가 나온다. 이때 O표시가 있을 때는 (1, 1)위치부터 O 표시가 있는 위치까지의 경우의..

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 접근 위의 그림은 문제에서 예시로 주어진 트리이다. 정점 n을 루트로 갖는 서브트리의 경우 n이 얼리어답터일 때 n의 자식 노드는 얼리어답터일 수도 있고 아닐 수도 있다. 반면 n이 얼리어답터가 아닐 때는 자식 노드들은 모두 얼리어답터이어야 한다. 따라서 dp라는 2차원 리스트를 생성하고 dp[n][0]일 때는 n이 얼리어답터일 때의 최소 정점 수를, dp[n][..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 접근 다익스트라의 주요 개념을 이해하는데 도움이 되었다. (1, 1)에서 출발하여 (N, N)에 도착할 때의 비용을 구해야한다. 벽을 부시는 것을 비용이라고 한다. 기본적으로 현재의 위치를 기준으로 상하좌우를 탐색한다. 이어서 벽일 때는 현재의 비용에서 +1, 벽이 아닐 때는 현재의 비용을 그대로 힙에 추가한다. 그렇다면 힙은 비용을 기준으로 다음 탐색할 위치가 나오게된다. 여기서 이미 벽을 부시..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 접근 N이 1부터 3일 때 경우의 수를 먼저 구하였다. 각각의 크기에서 사자를 0마리, 1마리, 2마리 등을 놓을 수 있을 때로 나누어 계산을 하였다. 그 결과는 다음과 같다. N=1 -> 1 + 2 = 3 N=2 -> 1 + 4 + 2 = 7 N=3 -> 1 + 6 + 8 + 2 = 17 N=4 -> 41 여기서 규칙을 구할 수 있었다. 현재 N이 i일 때의 경우의 수를 구할 때 i-1번째 경우의 수 x 2 + i-2번째 경우의 수를 하면 i번째의 경우의 수가 나왔다. 구현 - 먼저 N이 1일 때와 2일 때의 경우의 수를 저장하..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 접근 각 행에는 3개의 숫자들이 적혀져있다. 이때 첫 번째 숫자는 바로 위에 있는 행 중에 첫 번째, 두 번째 숫자를 선택할 수 있다. 또한 두 번째 숫자는 모든 숫자를 선택할 수 있고, 세 번째 숫자는 두 번째 숫자와 세 번째 숫자를 선택할 수 있다. 따라서 두 번째 행부터 탐색을 진행하여 각 열이 선택할 수 있는 숫자 중에서 최댓값과 최솟값을 더해나가서 마지막 행에서 최종 해를 찾는다. 여기서 2차원 리스트..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 접근 정사각형에서 오른쪽 맨 아래의 지점을 기준으로 왼쪽, 위, 대각선 위에서 최솟값을 구하고 그에 대한 +1을 오른쪽 맨 아래에 저장한다. 계속해서 누적해 나갔을 때 각각의 칸에는 한 변의 길이가 저장이되고 이 중 최댓값을 찾아 넓이를 구하면된다. 구현 - 입력 예시대로 입력을 받는다. - 2차원 리스트인 memo에는 각 지점에서의 한 변의 길이가 저장된다. - answer에 가장 긴 한 변의 길이가 저장된다. N, M = map(int, input().split(..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 접근 출발지에서 도착지까지 문제에서 주어진 조건에 부합하는 경로의 개수를 구해야한다. 이를 위해 DFS를 활용하였다. 출발지에서부터 상하좌우를 탐색하여 현재 위치보다 낮은 위치로 재귀호출을 진행하였다. 이때 현재 위치가 도착지일 때는 도착지까지 올 수 있는 경우의 수를 증가하였다. 하지만 DFS만을 이용하여 풀 때는 답은 정확하게 출력될 수 있지만 이미 가봤던 경로도 계속해서 탐색을 진행하기 때문에 시..

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 접근 이진 검색 트리는 루트 노드를 기준으로 루트 노드보다 작으면 왼쪽 서브트리로 크다면 오른쪽 서브트리에 저장한다. 이때 전위 순회의 결과가 주어진다고할 때 후위 순회의 결과를 출력해야 한다. 전위 순회이기 때문에 루트 노드를 먼저 방문하게 된다. 따라서 맨 처음 나오게 되는 숫자가 루트 노드에 저장된 수이다. 이제 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나누면 될 ..

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 접근 다음 칸으로 이동했을 때 해당 칸의 모래의 양은 없어지고 미리 정해진 위치로 비율만큼 흩어지게 된다. 그리고 방향에 따라 특정 위치의 비율도 달라진다. 따라서 미리 방향에 따라 특정 위치로 이동했을 때의 비율을 저장해둔 후에 사용하도록 하였다. 아래와 같이 현재 위치와 방향을 기준으로 흩어지는 모래의 비율을 저장하였다. 행의 번호는 현재 방향을 가리키고 있는 ..

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 접근 4개의 말로 10개의 턴이 진행된다. 주사위에 나오는 숫자는 미리 알고있다. 그렇다면 매 턴마다 어떤 말을 이동할지 선택해야 한다. 이를 비트시프트를 활용하여 모든 경우의 수를 구하여 말을 선택한다. 0부터 1