조준장 개발자 생존기

문제 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 알고리즘 - 1, 2, 3을 통해 만들 수 있는 경우의 수를 찾는 것이기 때문에 1, 2, 3의 경우의 수를 구하고 그것을 재귀 함수를 통해 입력받은 수를 만들 수 있는 경우의 수를 찾는다. - 피보나치 수 0번째는 0이기 때문에 0을 리턴 - 피보나치 수 1번째는 1이기 때문에 1을 리턴 - 그 외 2보다 크거나 같은 피보나치 수는 앞 피보나치 수의 합이므로 재귀 호출을 통해 구해서 합을 구한다. 코드 import s..

문제 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 알고리즘 - 1, 2, 3을 통해 만들 수 있는 경우의 수를 찾는 것이기 때문에 1, 2, 3의 경우의 수를 구하고 그것을 재귀 함수를 통해 입력받은 수를 만들 수 있는 경우의 수를 찾는다. 코드 import sys # 점화식 : (n > 3), f(n) = f(n - 1) + f(n - 2) + f(n - 3) def dp(v): # 1을 만들 수 있는 경우의 수 : 1 if v == 1: return 1 # 2을 만들 수 있는 경우의 수 : 2 elif v == 2: return 2 # 3을 만들 수 있는 경우의 수 : 4 elif v == 3: re..

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 알고리즘 - dp를 통해 문제를 수행한다. - 1부터 n까지 반복하여 각 수의 최소 연산 횟수를 구한다. - 반복문에서 2 부터 n + 1까지 반복한 이유는 1이 되기 위한 연산 횟수는 필요없기 때문이다. - 1을 빼주는 연산은 현재 연산 횟수를 이전까지에 연산 횟수에서 + 1 해준 연산 횟수로 초기화 해줘 확인한다. - 현재 3으로 나눠진다면 현재 수를 구하기 위한 연산 횟수와 3으로 나눈 값의 연산 횟수에서 + 1해준 값과 비교하여 작은 값을 현재 연산 횟수로 초기화한다. - 현재 수가 2로 나눠진다면 현재 수를 구하기 위한 연산 횟수와 2로 나눈 값의 연산 횟수에서..

문제 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 알고리즘 - 물건의 수에 따라 가방에 물건을 얼마나 담을 수 있는지 확인한다. - 반복문을 통해 각 물건의 무게와 가치를 확인하고 가방에 담을 수 있는 물건의 최대 가치를 각각 구한다. - 현재 비교하고 있는 가방의 최대 무게가 현재 물건의 무게보다 작다면 이전에 비교했던 가방의 무게에 담겨져 있는 가치가 최대 가치가 된다. - 현재 비교하고 있는 가방의 최대 무게가 비교하고 있는 물건의 무게..

문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 모든 칸에 가중치를 -1로 초기화한다. - 시작 칸에 가중치를 0으로 초기화한 후 모든 구역을 탐색할 때 벽을 만나게 되면 가중치에 +1을 해준다. - 빈 곳을 이동할 때는 현재 가중치를 이전에 가중치로 초기화한다. - 큐에 다음 탐색할 좌표를 추가할 때는 벽을 부시지 않고 이동한 좌표부터 먼저 탐색할 수 있게 한다. 코드 import sys from collections impor..

문제 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 반복문을 통해 시작점의 위치와 물의 위치를 리스트에 담는다. - 고슴도치가 이동할 수 있는 곳과 물이 잠길 수 있는 곳을 bfs 탐색을 한다. - bfs 탐색을 할 때 주의해야 할 점은 임시 리스트를 하나 만들어 현재 탐색해야 하는 곳과 다음에 탐색해야 하는 곳을 나눠 탐색해야 한다는 것이다. (고슴도치의 이동과 물이 잠기는 것은 현재!! 기준으로 수행해야 하기 때문.) - 물이 잠겼다면 고슴도치가 이동할 수 없는 ..

문제 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 알고리즘 - dfs 탐색과 dp를 통해 문제를 수행한다. - dp 배열에 모든 칸에 초기값을 -1로 초기화한다. - 각 칸을 탐색 시 0으로 초기화해주어 탐색 유무를 판단하고 목적지까지 도착하면 1을 리턴 받는다. - dp값이 -1이라면 탐색하지 않은 곳으로 탐색한다. - dp값이 0이라면 탐색한 곳이지만 그 후에 탐색할 곳이 없는 칸이 된다. - dp값이 1 이상의 값이라면 이전에 도착지까지 방문한 값으로 dp값을 리턴 받아 다시는 그 경로를 탐색하지 않게 한..

문제 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 시간복잡도를 생각해보면 단순 bfs 탐색을 통해 문제를 풀면 시간초과가 나오는 것을 확인할 수 있다. - 방문 여부에 따른 탐색이 아닌 벽을 부실 수 있는 상태, 벽을 못 부시는 상태 이 2가지 상태에 따라서 탐색을 해야한다. - 벽을 만났고 부실 수 있는 상태라면 벽을 부순 후 상태를 바꿔주어 이동횟수를 초기화한 후 큐에 담는다. - 벽이 아닌 이동 가능한 곳이고 현재 상태로 ..

문제 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 알고리즘 - bfs 탐색을 통해 문제를 수행한다. - 나이트가 이동할 수 있는 방향을 탐색한다. - 다음칸까지 이동하는 과정에서 현재 칸 + 1을 하여 다음 칸까지 이동하는 횟수를 체크한다. - 이동하려는 칸에 도착하면 리턴한다. 코드 import sys from collections import deque # bfs 탐색 def bfs(): # 나이트가 이동할 수 있는 8가지 방향 표현 dx = [1, -1, -2, 2, -2, 2, 1, -1] dy = ..

문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘 - 체스 판에서 퀸이 움직일 수 있는 방향을 생각하면 하나의 열의 하나의 퀸만을 놓을 수 있다. - 따라서 n개의 열의 퀸을 다 놓을 수 있는지 확인한다. - 이때, 대각선으로 퀸은 이동할 수 있으므로 대각선의 퀸을 놓을 수 있는지 확인해준다. - 백 트래킹을 통해 퀸을 n개 놓을 수 없다면 다른 경우의 수로 문제를 해결할 수 있게 한다. 코드 import sys # pypy3 해결.. python(3%) 시간초과 # 대각선의 퀸이 있는지 확인 def check(..