기록

1. 문제 정의양과 늑대가 각각 배치된 트리 구조 상에서 루트 노드(0)부터 출발하여 특정 조건을 만족하는 경로를 탐색하는 문제이다. 각 노드에는 양 또는 늑대가 한 마리 존재하며, 현재까지 모은 양의 수가 늑대 수보다 많을 경우에만 이동을 계속할 수 있다.목표는 이러한 제약 조건 하에서 이동 가능한 경로를 완전 탐색하여 최대로 확보할 수 있는 양의 수를 계산하는 것이다.info: 각 노드에 존재하는 동물 정보를 나타내며, 0은 양, 1은 늑대를 의미한다.edges: 노드 간의 연결 관계를 정의한 트리 구조이다.url : https://school.programmers.co.kr/learn/courses/30/lessons/92343#2. 해결 전략본 문제는 일반적인 트리 탐색과는 달리 다음과 같은 특수..

문제 요약numbers: 길이가 2 이상 20 이하인 양의 정수 배열target: 만들고자 하는 정수 (1~1000)각 숫자마다 +, - 연산을 선택해서 합을 만들 수 있는 경우의 수를 구하라 DFS 풀이 전략DFS로 다음 두 가지를 매 순간 재귀적으로 선택한다:+ numbers[i]- numbers[i]def solution(numbers, target): def dfs(n, i): # 누적합 n, 현재 인덱스 i if i == len(numbers): # 모든 수를 다 썼다면 return int(n == target) # 목표값이면 1, 아니면 0 return dfs(n + numbers[i], i + 1) + dfs(n - numbers[i],..

문제 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 1) 사이클 찾기 모든 학생들을 시작점으로 두고 dfs를 통해 사이클을 탐색한다. 1. 기존에 방문하지 않은 학생이라면, 방문기록을 남긴다. 다음 학생으로 이동한다. 2. 기존에 방문한 학생이라면, 방문 경로를 찾아 사이클을 이루는 학생의 수를 반환한다. 2) 시간초과 시간초과로 오래 고민했던 문제인데, 다른 문제를 풀면서 다시 한번 도전했다. 코드 import sys sys.setrecursionlimit(10**6) input = sys.stdin.re..

문제 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 풀이 1) 문제 이해하기 지도 밖으로 나가는 방향은 주어지지 않으므로, 어느곳에서 시작하더라도 사이클을 만나게 된다. (경로의 끝은 항상 사이클이다.) SAFE ZONE을 각 사이클에 만든다면, SAFE ZONE을 최소한으로 설치할 수 있다. 사이클의 개수를 출력한다. (최소 SAFE ZONE 개수 = 사이클의 개수) 2) 사이클 찾기 모든 위치에서 dfs를 통해 성우가 피리를 불때 움직일 경로를 시뮬레이션한다. 1. 기존..

문제 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 1) dfs for grouping 지도가 아래처럼 주어지면, 깊이우선탐색을 이용해 움직일 수 있는 경로를 그룹화 할 수 있다. 1 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1은 벽이므로 0에 대해서만 탐색하여, 그룹별 원소의 개수를 저장해둔다. {g00 : 2, g10 : 3, g22 : 1, g24 : 1, g32 : 1, g33 : 1} 1 1 g00 g00 1 g10 g10 1 1 1 g10 1 g..

문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 1) DFS 원점을 옮겨가면서 깊이 우선 탐색을 진행한다. 단순하게 dfs만으로 구현하면, 시간초과를 만나게 된다. 시간을 줄이기 위해 DP를 이용해야 한다. 2) DP 2차원 배열을 선언해 한번 방문한 노드는 다시 방문하지 않도록 처리하면, 시간을 줄일 수 있다. 3) 기타 매번 dfs를 while문을 쓰다보니, 재귀범위를 넓히는 것을 잘 잊어버린다. 자주 써봐서 익숙해지기..

문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 1) dfs 깊이/너비 우선 탐색을 할 때 재귀를 잘 사용하지 않았다. 이 문제를 반복문으로 풀었더니, pypy3로 제출하더라도 시간초과가 발생했다. (물론 이 방법으로 푸는 다른 방법도 있겠지만... ) 백트래킹이 필요한 경우에 기존에는 stack에 배열 자체를 넣어서 반복문을 돌렸는데, 이런 경우 재귀를 사용할 수 있음을 알아두자. 2) 논리 unknown에 0으로 표시된 위치..

문제https://programmers.co.kr/learn/courses/30/lessons/12929 코딩테스트 연습 - 올바른 괄호의 갯수올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모programmers.co.kr풀이1. 접근하기괄호쌍 2개를 이용한다고 할때, 아래와 같다.탐색하기문자열 뒤에 "("을 붙인다.올바른 괄호쌍이라면, 탐색을 계속한다. 문자열 뒤에 ")"을 붙인다.올바른 괄호쌍이라면, 탐색을 계속한다. 올바른 괄호쌍")"의 개수가 "("보다 많지 않다.2. 시간초과'('의 개수 기록하기더보기# "("의 개수를 기록하지 않음d..