투투

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://programmers.co.kr/learn/courses/30/lessons/12982?language=python3 코딩테스트 연습 - 예산 S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 programmers.co.kr 접근 예산 내에서 최대한 많은 부서의 물품을 지원해주어야 한다. 이를 위해 그리디로 접근을 하였다. 먼저 신청금액을 오름차순으로 정렬하고 신청금액이 작은 순서부터 탐색하여 예산에서 빼준다. 빼준 값이 0이상일 때 최종해를 증가시켰다. 구현 - 먼저 부서들이 신청한 금액이 들어있는 d를 오름차순으로 정렬한다. - 이제 d의 원소를 하나씩..

https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 접근 1번 마을에서 다른 마을로 배달을 갈 때 K시간 이하가 걸리는 마을의 개수를 구해야 한다. 따라서 하나의 노드에서 다른 모든 노드까지의 최단 거리를 구하는 다익스트라 알고리즘을 이용하여 풀었다. 먼저 마을과 마을 간의 연결 정보가 담긴 road를 통해 그래프를 그려주었다. 이후 다익스트라 알고리즘을 통해 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 접근 이진 검색 트리는 루트 노드를 기준으로 루트 노드보다 작으면 왼쪽 서브트리로 크다면 오른쪽 서브트리에 저장한다. 이때 전위 순회의 결과가 주어진다고할 때 후위 순회의 결과를 출력해야 한다. 전위 순회이기 때문에 루트 노드를 먼저 방문하게 된다. 따라서 맨 처음 나오게 되는 숫자가 루트 노드에 저장된 수이다. 이제 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나누면 될 ..