기록

문제 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/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 풀이 1) 비트 마스킹 행렬의 각 칸은 "가로, 세로" 두가지 중 한 상태를 가질 수 있다. 예를 들어서, 아래와 같이 표현할 수 있다. 따라서, 이진수를 사용하면 16칸에 가로와 세로를 채우는 모든 경우를 쉽게 구할 수 있다. 이를 위해서 세로를 0, 가로를 1이라고 정한다. 2) 브루스포트 2진수로 만든 배열이 가지는 값을 연산한다. 위의 예시처럼 "가로" 상태를 가지는 값끼리, "세로..

문제 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 풀이 1. make team 팀1이 가질수 있는 선수들의 경우의 수를 구한다. 선수의 수를 n//2로 둔 이유는 중복을 제거하기 위해서이다. (아래 두 경우를 같게 취급) team1 team1 team1 team2 team1 team1 team2 team2 team2 team2 team1 team2 team2 team1 2. calculation ..

문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 1) 분할 정복을 이용한 거듭제곱 number을 n번 곱한다고 하면, 아래처럼 적을 수 있다. 이를 행렬에도 적용하면, 문제를 해결할 수 있다. def power(number, n) : if n==0 : return 1 elif n이 짝수 : return power(number², n//2) elif n이 홀수 : return number*power(number², n//2) 문제에서는 n의 최대값을..

문제 https://www.acmicpc.net/problem/2961 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net 풀이 1) dfs 해당 음식을 사용할 때와 사용하지 않을 때를 나누어서, 모든 경우를 탐색한다. 코드 import sys sys.setrecursionlimit(10**6) N = int(input()) arr = [list(map(int, input().split())) for i in range(N)] def dfs(p, sour, bitter) : if p+1>=l..

문제 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 풀이 board의 내부의 점 (r, c)가 주어질 때, board[r][c]에 적어야 할 값을 반환하는 함수 f가 있다고 하자. ex) f(-3, -3) = 37 f(0, 1) =2 1) 어느 그룹에 속하는가? 메인그룹 mg = abs(max(r, c, key = abs)) 안쪽에서 바깥쪽 껍데기로 나오면서 0, 1, 2... 그룹으로 묶을 수 있다. 0그룹 : 1 1그룹 : 2~9 2그룹 : 10~25 ... 점A (-2, 3)이 주어졌다고 할때 점 A는 3그룹에 속한다. 서브그룹 # corner일때 if abs(r)==abs(c) : if c>0 and r