Leta Learns

문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 처음에는 문자를 하나하나 비교해서 풀어야 하나 라는 생각을 했다. 귀찮기도 하고 감도 잘 안 잡혀서 생각 좀 하다가 java 풀이를 검색했다. combination을 사용한 풀이가 있길래 나도 combination 함수를 사용하였다. combination 함수 사용하기 전에 입력받은 알파벳들 정렬하는 과정을 빼먹어서 시간이 좀 걸렸다. 문자열 합칠 때 join 함수 사용하는 것도 잊지말자. imp..

문제 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 브론즈 문제인데 처음에 접근법 생각하는 게 시간이 좀 걸렸다. 9명 중에 2명을 뺐을 때 나머지 7명 키의 합이 100이 되는 경우 그 2명을 빼주었다. import sys input = sys.stdin.readline height = [int(input()) for _ in range(9)] total = sum(height) for i in range(9): for j in range(i+1, ..

문제 https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net bfs 풀 때 visited 배열 안 쓰고 푸는 게 편하길래 이 문제도 그렇게 접근했는데 잘 안 풀려서 결국 visited 배열을 사용하였다. 모든 L에 대해서 bfs 탐색을 시도해야 해서 시간초과 날까봐 코드 짤 때부터 걱정했는데 역시나였다. pypy3로 제출해서 성공하였다. import sys from collections import deque input = sys.stdin.readlin..

문제 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문 안에서 팰린드롬 판별 먼저 하고 소수 판별을..