This is Mi

https://www.acmicpc.net/problem/16971. 풀이BFS 알고리즘을 사용하자문제에서 말하는 최소 시간은 결국 수빈이가 동생까지 가는 데 이동하는 최단 거리로 치환할 수 있다. 또한 앞으로 1칸 이동, 뒤로 1칸 이동, 순간 이동은 모두 이동하는 데 1초가 걸린다. 즉, 모든 이동 방식의 가중치가 모두 1이다. 따라서 이 문제는 가중치가 1로 동일한 그래프에서 최단 경로를 찾는 것이므로 BFS 알고리즘이 적합하다. 참고로 BFS는 노드를 한 번만 방문하면 되며, 처음으로 노드를 방문한 시점이 가장 빠른 시간임을 보장한다. 번외로 dp를 통해 문제를 해결할 수는 있지만, dp는 일반적으로 이동에 따른 가중치가 서로 다른 경우에 활용한다. 2. 정답 코드from collections..

https://www.acmicpc.net/problem/159611. 풀이입력이 매우 크므로 일반 input() 대신 빠른 sys.stdin.readline()을 사용하자.N의 크기가 무려 3,000,000이다. 알고리즘이 정답이더라도, 입력 받는 데서 시간이 지체되면 결국 실행 시간이 오래 걸리게 된다. 실제로 오랜만에 백준을 풀어서 습관처럼 input()을 사용했다가 시간 초과가 났었다.  어떤 초밥을 몇 개 먹었는지 저장하는 리스트(dishes)를 사용하자.리스트의 인덱스가 초밥의 종류를 나타내고, 해당 인덱스의 값이 고객이 그 초밥을 의미한다.고객이 먹을 수 있는 초밥 가짓수의 최대값은, 고객이 연속해서 먹은 k개의 접시에 쿠폰 번호 c가 포함되어 있지 않은 경우이다. 이를 다르게 생각하면 고객..

https://www.acmicpc.net/problem/14891   1. 풀이(n - 1)번째 결과를 바탕으로 가장 최소 비용을 만드는 n번째 선택을 하자.이전 결과를 담을 2차원 리스트가 필요하다. 행은 몇 번째 집인지를 의미하고, 열은 R(0), G(1), B(2) 중 어떤 색을 선택했는지에 대한 정보를 나타낸다.  위 그림은 백준의 첫 번째 입력 예제를 바탕으로 만들어진 2차원 리스트이다.예를 들어 1번 집을 초록색과 파란색 중 더 비용이 작은 색을 칠하고, 2번 집에 빨강(R)을 칠한다면 그 비용은 dp[1][0]에 담긴다. 이를 식으로 나타내면 dp[1][0] = min(dp[0][1], dp[0][2]) + COSTS[1][0]이다.그런데 사실 2번 집에 빨간색이 아니라, 초록색 혹은 파란..

https://www.acmicpc.net/problem/14891 1. 풀이회전하는 톱니바퀴의 왼쪽과 오른쪽을 나눠 각 톱니바퀴의 회전 여부를 파악하자 만약 2번째 바퀴를 회전시킨다면, 그것의 왼쪽에 있는 바퀴들과 오른쪽에 있는 바퀴들을 따로따로 고민해야 한다. 왼쪽을 먼저 보자. 2번째 바퀴의 왼쪽 부분, 즉 인덱스 6과 1번째 바퀴의 오른쪽 부분, 인덱스 2를 비교해야 한다. 두 자성이 다르기 때문에 1전째 바퀴는 2번째의 반대 방향으로 회전한다. 그리고 이제 1번째 바퀴의 인덱스 6과 0번째 바퀴의 인덱스 2를 비교해야 하는데, 0번째 바퀴가 없으므로 비교를 종료한다. 그럼 이제 오른쪽 방향을 살펴보자. 2번째 바퀴의 인덱스 2와 3번째 바퀴의 인덱스 6을 비교면하면 두 자성이 같음을 알 수 있다..

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 1. 풀이 주사위를 동서남북으로 굴린 결과를 배열로 표현하자 위 그림처럼 동쪽으로 회전하면 기존 1번 자리에는 4가, 3번 자리에는 1, 4번 자리에는 6, 6번 자리에는 3이 온다. rolled = { 1: [o[3], o[1], o[0], o[5], o[4], o[2]], # 동쪽 2: [o[2], o[1], o[5], o[0]..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 1. 풀이 DP 테이블을 활용하자 아래 9251번 문제와 현재 5582번 문제는 비슷하지만, 확연한 차이점이 하나 있다. 9251번은 공통 부분 문자열 사이에 다른 문자열이 존재해도 괜찮았지만, 현재 5582번은 반드시 공통 서브 문자열이 서로 붙어 있어야 한다. 서브 문자열 사이에 다른 문자가 들어오면 안 된다. [백준] 9251번 LCS 파이썬 풀이 https://www.acmicp..

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 1. 풀이 S에 말고 T에 집중하자 처음에는 S에서 T를 만들어 나가는 방식으로 접근했다. S 뒤에 A나 B가 붙는 모든 경우의 수를 고려하면, 그 수가 엄청나게 많아진다. 위 그림만 보아도, B 1글자에서 만들 수 있는 4글자 문자열은 2^(4 - 1) = 8개이다. 최악의 경우라면 S 길이가 1이고, T의 길이가 1,000일 때니까, 경우의 수는 무려 2^..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 1. 풀이 가장 뒤의 문자부터 검사하자 맨 뒤 문자부터 서로 비교하면서 (1) 같으면 두 문자열에서 동시에 마지막 문자를 제거하고 (2) 다르면 문자열1의 마지막 문자만 제거하거나 문자열2의 마지막 문자만 제거하는 식으로 2가지 갈래로 나누어 가자. 더 이상 문자열을 비교할 수 없을 때는, 그 동안 동시에 제거된 문자 (C, E)가 바로 두 문자열의 L..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 1. 풀이 모든 국가를 방문하면서 너비 우선 탐색(bfs)로 연합을 확인하자 N x N 크기의 땅에는 1개 이상의 연합이 존재할 수 있다. 즉, 위 그림처럼 그래프가 여러 개 존재할 수 있다는 것이다. 따라서 땅을 한 칸, 한 칸 방문해서 해당 국가가 이루는 연합 정보를 알아내야 한다. 이때 어떠한 연합에 포함된 국가는, 이전 bfs 과정에서 방문했었다는 의미이다. 따라서 재방문을 ..

https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 1. 풀이 N x N 크기의 2차원 리스트를 생성하고, (i, j) 좌표에 빈 칸, 뱀 존재, 사과 존재 여부를 저장하자 필자는 maps라는 N x N 2차원 리스트를 생성하고 빈 칸은 0, 뱀이 있으면 1, 사과가 있으면 2로 표현했다. 따라서 board[i][j]로 접근하면 곧바로 해당 칸의 정보를 알아낼 수 있다. 이때 리스트는 인덱스 (0, 0)부터 시작하는데, 문제에서는 (1, 1)부터 시작한다..