[백준] 9251번 LCS 파이썬 풀이
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..
[백준] 16234번 인구 이동 파이썬 풀이
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 과정에서 방문했었다는 의미이다. 따라서 재방문을 ..
[백준] 3190번 뱀 파이썬 풀이
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)부터 시작한다..
[백준] 14503번 로봇 청소기 파이썬 풀이
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 1. 풀이 지문을 똑바로 읽자... 문제 조건을 제대로 확인해야 한다. 실제 이 문제의 질문 게시판을 보면 문제를 이해하지 못해서 많은 분들이 실수했단 걸 알 수 있다. ✅ 0은 빈 칸, 1은 벽 ⇒ 청소했다는 표시는 0이나 1이 아닌 다른 숫자(예를 들면 2)를 통해 나타내야 한다. ✅ 벽과 달리, 청소한 칸은 후진할 수 있다. ⇒ 따라서 현재 ..