Leta Learns

문제 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문으로 돌리고 ..

문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 스터디할 때는 크루스칼 어려웠는데 지금은 할 만하다. 문제 해결에 필요한 로직대로만 조금 수정하고 find, union 함수 사용하면 돼서 금방 익숙해진 것 같다. MST 어려워서 겁먹었었는데 이제는 좀 더 마음 놓고 시도해도 될 것 같다. import sys input = sys.stdin.readline def find(a): if a == parent[a]: return a parent[a] = ..

문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 확실히 여러 번 푸니까 이제는 문제 접근법이 비교적 쉽게 생각난다. 물론 실버인 것도 한 몫했겠지만... ㅋㅋㅋ 보통 m=row, n=col으로 하는데 여기서는 m=col, n=row여서 헷갈렸다. 그것때문에 배열 인덱스를 몇 번이나 바꿔서 재실행했는지 모르겠다. ㅠㅠ 그 부분 빼고는 무난한 문제였다고 생각한다. import sys input = sys.stdin.readline from collecti..

문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 아 한 번에 푼 문제 완전 오랜만이라 신난다. bfs로 풀 수 있는 문제인데 그러면 기존에 푼 dxdy 문제랑 코드가 같아서 dfs로 풀었다. 뭐 물론.. 큰 차이는 없다. 그냥 deque를 안 쓴 것 뿐.. ㅋㅋㅋㅋ input 0110100을 받는다고 가정했을 때, 이를 개별 int로 받는 과정을 생각하는 게 어려웠다. list(map(int, input().split()))으로 했더니 그냥..

문제 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 타임머신 문제와 비슷한 유형이다. 다른 점이라면 bf 함수에서 세번째 for문 안에 있는 if문을 돌릴 때, 타임머신에서는 아래의 if문을 사용하여 시작점과 연결된 경로가 있는지 확인해야 했고, if dist[a] != float('inf') and dist[next] > dist[a] + time: 웜홀 문제에서는 시작점이 주어지지 않으므로 이에 대한 확인 없이 negative..

문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만포드 코드에 문제가 있는데 모르겠어서 친구랑 스터디할 때 상의했다. for문을 세 번 돌려야 하는데 난 두 번만 돌려서 문제가 생겼다. for i in range(1, n+1) : 간선 탐색을 위한 for문 (아래 for문을 n번 반복) for a in range(1, n+1) : 노드 탐색을 위한 for문 (모든 엣지에 대해서..

문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 어제 푼 다익스트라 코드 이용해서 조금만 손 봤더니 그냥 풀렸다.. 다익스트라 코드 외우면 이 문제 저 문제 풀기 수월하겠네. 외워야겠다. 시작점, 도착점만 입력 받아서 다익스트라 이용해서 dist 배열 구하고 변수(cost) 에 저장한 다음, 해당 배열의 도착점 인덱스 값을 출력해주면 된다. (cost[end]) import sys import heapq ..