네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 2. 풀이과정 BFS를 사용한 이유 처음엔, dfs로 풀고 시간 초과가 났다. 생각해보니 이 문제는 가다가 해당 노드에 더 작은 비용으로 갈 수 있는 경우, 굳이 더 갈 필요가 없어서 버리기 때문에 bfs가 유리하다. dfs를 사용할 경우, 초반에 전체 탐색을 하기 때문에 시간 초과가 나는 것 같다. Priority Queue를 사용한 이유 bfs임에도 priority..

1. 문제 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2. 풀이 과정 1 => N번째 집을 차례대로 색을 칠한다. 각자 자신의 앞의 집의 색깔만 피하면 된다. 단, 마지막 집은 첫 번째 집의 색깔도 고려해야하기 때문에 처음부터 첫 번째 집의 색에 따라 나눠 계산했다. 첫 번째 집 색에 따라 R[], G[], B[]를 만들어서 값을 업데이트해갔다. 이는 Dynamic Programming을 사용한 풀이 방법이라 ..

1. 문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 2. 풀이과정 1. mid보다 작거나 같은 값 개수 세기 n이 5이고 검사하는 값을 mid = 6이라고 할 때, 6보다 작거나 같은 값의 개수를 세는 법은 아래와 같다. 1*1, 1*2, 1*3, 1*4, 1*5 2*1, 2*2, 2*3, 2*4 ,2*5 3*1, 3*2, 3*3, 3*4, 3*5 4*1, 4*2, 4*3, 4*4, 4*5 5*1, 5*2,..

1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 풀이과정 최단거리 구하기는 보통 bfs, 도착지점까지 경로를 구한다면 dfs를 주로 사용하는 것 같다. 이 문제는 최단거리를 구하는 문제로 bfs를 사용하여 풀었다. 최단거리만큼만 모든 경로를 탐색하기 때문에 최악의 경우(모든 경로 끝까지 전체탐색)을 막을 수 있다. 처음에는 boolean visited[N][M][2]로 3차원배열을 사용해서 visited..

1. 문제 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 2. 풀이과정 문제를 처음 봤을 때, BFS를 떠올렸다가 1~3칸 전진과 1(90도)~2(180도)번 전진 처리가 복잡해 DFS로 풀었다. 그런데, 풀고나서 보니 DFS보다 BFS를 썼을 때 더 빠르게 구현할 수 있을 것 같아 BFS로 다시 풀어보았다. 결과적으로 BFS가 메모리, 시간 측면에서 더 효율적이다. 아래 그림은 두 코드에서 사용한 방향 전환할 때, 걸리는 시간을 구하는 방법이다. 동서..

1. 문제 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 2. 풀이과정 1. 궁수 3명의 위치에 대해 조합 구하기 2. 각 조합마다 simulation() 실행 [Simulation] 1.시간이 N(배열의 세로)만큼 지나서 더 봤자 적들이 없는 경우 or 그 전에 적들을 다 물리친 경우 반복 종료 1-1. 각 궁수마다 bfs로 가장 가까운 적을 찾음 but 찾고 있는 거리가 D보다 커지면 다음 궁수로 넘어감. 1-2. 가장 가까운 적을 찾으면, -cas..

1. 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 2. 풀이 과정 1) 입력을 받으면서 집과 치킨집의 위치를 각각 저장 2) 저장된 치킨 집 중 M개를 뽑는 조합 구현 3) 조합마다 결과를 비교해서 최소값 찾기 tip) 집과 치킨집과의 거리는 매조합마다 쓰이므로 미리 저장해놓고 가져다 쓴다. import java.io.BufferedReader; import java.io.InputStreamReader; impo..

1. 문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2. 풀이과정 n의 경우의 수 = (n-1에서 1x2블럭을 추가했을 때) + (n-2에서 2x1블럭 2개 혹은 2x2블럭 1개를 추가했을 때) 정리하면, f(n) = f(n-1) + f(n-2) * 2로 수식을 나타낼 수 있다. n = int(input()) x, y = 1, 3 for i in range(n-2): temp = y y = y + x*2 x = temp if n == 1: print(x) else: ..

1. 문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 2. 풀이 과정 1. 주어진 문자열이 "AFCA"이라면 A = 1000+1, F = 100, C = 10으로 자릿수만큼 수를 더해준다. 다음 문자열을 읽을 때는 이 값에 누적으로 더해주면 된다. 2. 누적으로 더한 수들을 정렬해서, 제일 큰 수를 가진 알파벳부터 9 => 8 => 7 ... 순으로 할당하는 것이 제일 큰 수를 만들 수 있다. 따라서 출력값은 (해당 알파벳이 가진 수..

1. 문제 2. 풀이과정 방법 1) heapq 내장 모듈 활용 import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) while scoville[0] < K: if len(scoville) == 1: return -1 answer += 1 #가장 안매운거, 두 번째 안매운거 heap에서 빼서 연산 a = heapq.heappop(scoville) + heapq.heappop(scoville)*2 #섞은거 넣기 heapq.heappush(scoville, a) return answer 방법 2) heapq대신 deque만 이용하였다. 섞은 결과는 새로운 배열 mix에 따로 저장하여 scoville와 mix의 맨 앞 원소만 비교하..