조준장 개발자 생존기

문제 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 알고리즘 - 반복문을 통해 종이를 확인한다. - 시작점에 종이의 수가 현재 종이의 수와 다르다면 3* 3 범위를 재귀적으로 탐색한다. - 탐색할 때 3으로 나눈 범위를 그 종이의 수 x, y 좌표를 탐색한다. - 탐색이 모두 끝난 구역은 카운트한다. 코드 import sys def dfs(x, y, z): global answer visited = graph[x][y] # 반복문을 통해 종이를 확인 for i in range(x, x + z): ..

문제 1986번: 체스 첫째 줄에는 체스 판의 크기 n과 m이 주어진다. (1 ≤ n, m ≤ 1000) 그리고 둘째 줄에는 Queen의 개수와 그 개수만큼의 Queen의 위치가 입력된다. 그리고 마찬가지로 셋째 줄에는 Knight의 개수와 위치, www.acmicpc.net 알고리즘 - queen과 knight가 이동할 수 있는 곳을 dfs로 탐색한다. - knight의 경우 한 번만 이동해야 되므로 한 번만 탐색하게끔 한다. - 반복문을 통해 모든 좌표를 탐색 후 queen과 knight가 이동할 수 없는 좌표의 개수를 출력한다. 코드 import sys sys.setrecursionlimit(10**9) # queen을 dfs 탐색 def dfs_queen(x, y, v): if x < 0 or x..

문제 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 알고리즘 - 반복문을 통해 갈 수 있는 그래프의 좌표를 탐색한다 - 현재 탐색하는 좌표가 오른쪽 아래 맨 끝 점이면 반복을 멈추고 오른쪽 아래 맨 끝 점까지 이동 가능한 개수를 출력한다. - 오른쪽과 아래로 이동할 수 있다면 이동하고 그전 좌표까지 이동 가능한 값을 더한다. 코드 import sys n = int(sys.stdin.readline()) graph = [list(map(int, sys.stdin.readline().split()))..

문제 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 알고리즘 - 반복문을 통해 추천을 확인한다. - defaultedict 메서드를 이용하여 추천을 받는다. - 추천받은 사람의 수가 사진틀보다 크다면 추천받은 사람의 사진 중에서 하나를 삭제한다. - 반복문을 통해 추천받은 사람을 확인한다. - 추천받은 사람이 이번에 추천받은 사람이라면 무조건 사진틀에 들어가야 하기 때문에 넘긴다. - 추천받은 횟수가 제일 적은 사람을 찾아 삭제한다. - 추천을 모두 확인했다면 사진틀에 있는 사람을 학생 번호로 오름..

문제 1706번: 크로스워드 동혁이는 크로스워드 퍼즐을 좋아한다. R×C 크기의 크로스워드 퍼즐을 생각해 보자. 이 퍼즐은 R×C 크기의 표로 이루어지는데, 퍼즐을 다 풀면 금지된 칸을 제외하고는 각 칸에 알파벳이 하나씩 www.acmicpc.net 알고리즘 - 반복문을 통해 가로와 세로로 연속되는 단어를 찾는다. - 찾는 방법의 알고리즘은 다음과 같다. - 반복문을 통해 가로, 세로의 문자를 확인한다. - 현재 문자가 '#'가 아니면 문자를 낱말에 더해준다. - 현재 문자가 # 이면서 낱말의 길이가 2 이상이라면 낱말 모음에 추가한다. - 현재 문자가 # 이면서 낱말의 길이가 2 미만이라면 필요 없는 낱말이므로 ""로 낱말을 초기화한다. - 가로, 세로 모든 낱말 모음을 구했으면 사전식 순으로 정렬 후..

문제 1421번: 나무꾼 이다솜 첫째 줄에 이다솜이 가지고 있는 나무의 개수 N과 나무를 자를 때 드는 비용 C와 나무 한 단위의 가격 W이 주어진다. 둘째 줄부터 총 N개의 줄에 이다솜이 가지고 잇는 나무의 길이가 한 줄에 하나 www.acmicpc.net 알고리즘 - 반복문을 통해 나무를 1부터 제일 긴 나무의 길이만큼 잘라본다. - 반복문을 통해 모든 나무를 확인한다. - 나무를 자른 후 개수와 남은 나무의 길이를 구한다. - 남은 나무의 길이가 있다면 자른 나무 수만큼 비용을 낸다. - 남은 나무의 길이가 없다면 자른 나무 수 -1 만큼 비용을 낸다. - 자른 나무를 판 후 이익이 나는지 확인한다. - 이익이 난다면 money에 이익을 더한다. - 모든 나무를 확인한 후에 money가 이익의 총합..

문제 1411번: 비슷한 단어 첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 모든 단어의 길이는 같고, 중복 www.acmicpc.net 알고리즘 - 반복문을 통해 단어를 확인한다. - 단어를 확인하는 과정으로는 단어의 각 알파벳을 확인하며 알파벳과 수를 dic에 추가한다. - 현재 확인한 알파벳을 temp에 추가한다. - dic에는 각 알파벳과 수가 추가되어 있을 것이고 temp에는 알파벳을 숫자로 바꾼 값들이 있을 것이다. - temp와 반복문을 통해 같은 단어인지 확인하고 카운트한다. 코드 import sys n = int(sys.stdin.readline()) temp = [..

문제 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 반복문을 통해 건너야 하는 다리를 모두 탐색한다. - 2개의 반복문을 통해 현재 다리에서 앞으로 가는 경우와 뒤로 가는 경우를 나눠 탐색한다. - 탐색 중 탐색하지 않은 다리가 나타나면 건너야 하는 다리 리스트에 추가하고 그 다리까지 점프한 수를 초기화한다. - 그때 탐색한 다리가 b번 다리라면 그때 탐색한 다리까지 점프한 수를 출력한다. - 모든 다리를 탐색한 후에도 b번 다리를 가지 못했..

문제 1283번: 단축키 지정 첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하 www.acmicpc.net 알고리즘 - 반복문을 통해 모든 단어를 확인한다. - 1번과 2번의 방법을 한 번에 수행한다. - 반복문을 통해 단어의 첫 글자의 알파벳을 확인한다. - 현재 단어의 첫 글자가 단축기로 지정되어 있지 않다면 현재 단어의 첫 글자를 단축기로 지정하고 "[]"를 감싼 후 출력한다. - 다음으로 위 방법을 통해 break가 되지 않았다면 3번의 방법을 수행한다. - 위 방법과 다르게 단어의 첫 글자의 알파벳이 아닌 모든 단어의 알파벳을 순서대로 확..

문제 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 알고리즘 - 재귀와 백트래킹을 통해 문제를 수행한다. - 백트래킹 함수를 만들어 매개변수를 idx와 수열의 합으로 선언한다. - 현재 idx가 정수의 개수보다 크면 리턴한다. - 수열에 현재 idx 정수를 더한다. - 현재 수열의 합이 s라면 카운트한다. - 현재 idx 정수를 더한 값을 백트래킹 함수에 넣어 재귀적으로 탐색한다. - 위 탐색이 끝난 후 현재 idx 정수를 더하지 않은 값을 백트래킹으로 재귀적으로 다시 탐..