Leta Learns

문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 단순 bfs 였다. 이제 그래프는 잠시 쉬어도 될 것 같은 느낌.. import sys from collections import deque input = sys.stdin.readline def bfs(cur_y, cur_x): chess[cur_y][cur_x] = 1 q = deque() q.append((cur_y, cur_x)) while q: y, x = q.popleft() if ..

문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 항상 dxdy 기법에 익숙한 bfs를 dxdy 없이 그냥 큐로 구현하는 것 빼고는 어렵지 않은 문제였다. 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문해야 해서 인접리스트를 sort 해주어야 했는데, 왠지 당연히 입력할 때부터 제대로 정렬해서 줄 것 같다는 근거 없는 생각에 sort를 안 해서 틀렸다. 입력받으면서 각각의 인접리..

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 골드라서 좀 겁먹었었는데 무난한 그래프 문제였다. 그리드에 색 입력 받을 때 'R', 'R', 'R', 'B', 'B' 이런 식으로 되어야 하는데 자꾸 'RRRBB' 이렇게 받아져서 그 부분 조금 헤맸다. 색약이 아닌 경우를 먼저 구하고, 'R'을 'G'로 바꾼 후 색약인 경우를 구한다. ('G' -> 'R'도 가능) 이때 visited 초기화 해주어야 하는 것 잊지 말기. impor..

문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 아 아래가 0이고 위가 m, n이라서 인덱스 정리 다 해주어야 하는 줄 알고 한참 헤맸었는데 생각해보니까 굳이 인덱스 안 바꿔주어도 되는 문제였다. 영역만 구하면 되는 거니까 그림이 뒤집혀 있어도 상관 없었기 때문에.. 쨌든 그거 해결하고 나니 순조로웠다. bfs 함수 만들 때 자동적으로 가장 마지막 (n, m)인 경우 break를 넣어주었더니 여기서 에러가 났다. : b..

문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 그래프 기본문제였다. 너무 오랜만에 풀어서 잘 기억도 안 나고, 재귀 제한 걸어줘야 한다는 것도 깜빡했다. 😅 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline def dfs(v): visited[v] = 1 for i in adjList[v]: if not v..

문제 https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 막 어렵진 않은데 그냥 좀 복잡한 문제인 것 같다. 풀긴 했는데 주먹구구식으로 풀어서 코드가 하나도 안 예쁘다.. import sys input = sys.stdin.readline n, k = map(int, input().split()) medals = [[0, 0, 0, 0]] #국가, 금, 은, 동 rank = [0 for _ in range(n+1)] cnt_r..

문제 https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 소수 판별 함수와 팰린드롬 판별 함수만 만들면 되는 거라서 생각보다 금방 풀었다. 근데 자꾸 시간초과가 나서 짜증났다. 다른 사람들 코드 찾아봐도 내 코드와 비슷한 것 같아서 이유가 뭘까 했는데 어떤 사람이 소수 판별 전에 팰린드롬 판별을 먼저 해서 한 번에 여러 개를 쳐낸 걸 보았다. 그래서 나도 while문 안에서 팰린드롬 판별 먼저 하고 소수 판별을..

문제 https://www.acmicpc.net/problem/2621 2621번: 카드게임 근우는 오늘 재미있는 카드 게임을 배우고 있다. 카드는 빨간색, 파란색, 노란색, 녹색의 네 가지 색이 있고, 색깔별로 1부터 9까지 숫자가 쓰여진 카드가 9장씩 있다. 카드는 모두 36(=4x9)장이다. www.acmicpc.net 역시나 어려운 구현 문제.. card 변수에 색과 숫자를 리스트로 입력 받은 후 colors, numbers에 각각 색과 숫자 정보를 따로 넣어주었다. 색과 숫자의 개수를 구하기 위해 cnt_color 딕셔너리와 cnt_num 리스트를 만들었다. for문을 돌려서 입력 받은 카드의 색과 숫자를 확인하며 cnt를 1씩 증가시켜주면 초기 작업이 끝난다. 9개의 조건을 만들어줄 차례이다...

문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 크루스칼 사랑해. 이제 크루스칼은 문제 이해만 잘 하면 나름 수월하게 풀 수 있다. 근데 그 문제 이해가 오래 걸린다.. 이걸 어떻게 크루스칼로 풀어야 하는지, 이게 왜 크루스칼인지.. 뭐 풀다보면 익숙해지겠지..? import sys input = sys.stdin.readline def find(a): if a == parent[a]: return a..

문제 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 박스에 맥주를 최대 20개 까지 담을 수 있고, 50m에 맥주 한 병씩을 마셔야 한다. => 노드들 간의 거리가 1000m를 넘어서는 안 된다. 문제가 복잡해보이게 적혀있어서 그렇지 이것만 이해하면 나름 괜찮았던 것 같다. 입력 받는 부분에서 1차로 막혔었는데 편의점이 n개라서 for문을 n+2로 돌려서 입력값 전체를 다 받으려고 했었다. 다시 보니까 편의점 n개만 for문으로 돌리고 ..