Leta Learns

문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라.. 아무 생각 없이 시도했다가... 피 봤다.... heapq 쓰는 방법 어려워서 고민하다가 다익스트라 예제 코드 구글링해서 참고했다. 이 문제에서 포인트는 파티를 여는 마을(x)로 갈 때 dijkstra 한 번, 파티가 끝나고 집에 갈 때 dijkstra 한 번. 총 두 번 dijkstra 함수를 호출해야 한다는 것이다. dijkstra 함수 내부에..

문제 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 스터디 할 때 트리 DP 예제 코드를 받아놔서 그거 보고 좀 고치면서 풀었더니 골드1 치고는 엄청 빨리 풀었다. 사실 두 시간 만에 푼 거라 난이도 떠나서도 내 기준 엄청 빨리 푼 편에 속한다. 문제 이해부터 쉽지 않았는데, 문제에서 중요한 바는 각 노드에서 나아갈 수 있는 방향은 '우수마을' or 'not 우수마을' 이렇게 두 가지 경우. 루트 노드가 우수 마을이면 하위 노드는 우..

문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 이번 주 MST 스터디에서 1197번은 프림으로, 1922번은 크루스칼로 풀 생각이었는데 보통 문제 풀 때는 거의 다 크루스칼로 푸니까 둘 다 크루스칼로 풀기로 스터디원이랑 협의했다. 그랬더니.. 1197번이랑 입력 부분 빼고 코드가 전부 똑같다. 이번 주는 크루스칼에 익숙해지는 주간.. import sys input = sys.stdin.readline def find(a): if a == parent[a]: return a parent[a] = find(parent[a]) re..

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 처음에 Prim으로 풀었는데 예제만 맞고 또 일반화에 실패했다. ㅋㅋ 찾아보니까 Prim은 우선순위큐를 쓰더라고.. 복잡하길래 그냥 Kruskal로 풀었다. 유니온 파인드 공부해놨더니 별로 안 어려워서 풀만 했다. import sys input = sys.stdin.readline def find(a): if a == parent[a]: retu..

문제 https://www.acmicpc.net/problem/18126 18126번: 너구리 구구 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이 www.acmicpc.net 일반적인 dfs 문제들과 비슷하다. 거리의 최댓값을 구해서 갱신해주기만 하면 되는 문제이다. 최댓값들을 리스트에 저장한 후 그 리스트에서의 최댓값을 출력하면 된다. 최댓값 저장할 때 뻘짓을 좀 했는데 2021.07.24 - [HUFS/HUFS 모각코 캠프] - [모각코] 210724 Today I Learned 여기에 그 내용을 자세히 적어놓았다. import sys sys.se..

문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 모각코에서도 얘기했듯이 이번 문제는 m, n을 구별하는 게 어려웠다.. 선형대수학 공부해야되나봐... row, col 왜 이리 헷갈리지.. 어제 스터디 할 때 관련 얘기 해서 row랑 col에 대해서 10분 동안 토의했는데 꼭 잘 기억해야지.. 이 문제는 모각코 Today I Learned에서 이미 리뷰를 했기 때문에 조금만 더 덧대려고 한다. 2021.07.22 - [HUF..

문제 https://www.acmicpc.net/problem/17220 17220번: 마약수사대 최근들어 세계적으로 마약과 관련한 사회적 문제들이 많이 발생하고 있다. 이에 따라 경찰은 마약 수사대의 한정된 인력이 허용하는 선에서 최대한 마약공급을 막고자 한다. 마약 공급책들은 www.acmicpc.net dfs 골드3은 무리였나.. ㅋㅋㅋ 인접리스트 입력을 문자열로 받는 것부터가 어려워서 헤맸다. 아스키 코드 써서 간신히 해결. 2021.07.20 - [Python] - 아스키코드 변환 함수 ord(), chr() 유향그래프 문제도 거의 처음 푸는 것 같다. check에 맨 마지막 줄에서 입력 받은 2 b c 를 리스트로 넣고 인덱싱 사용해서 문제를 풀었다. check는 경찰이 소재를 파악하고 있기 ..

문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 1697번 숨바꼭질 문제랑 알고리즘이 거의 같았다. 2021.07.12 - [Coding/백준] - [Python] 백준 1697번 - 숨바꼭질 비슷한 구조의 bfs문제를 한 번 더 풀 수 있어서 bfs 이해하는데 더 도움이 됐다. count를 처음에는 그냥 변수로 만들어서 갱신해줬는데 그렇게 하다보니 갈라지는 부분이라고 해야하나... 쨌든 그런 곳에서 count가 여러 개로 나뉘어져야 하는데 변수 하나..

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미로 탐색 학교 수업 때 과제로 풀었었는데 그래서.. 그냥 그때 푼 코드 거의 참고했다.. bfs 너무 어렵다.. 풀어놓은 코드 조금만 수정해서 풀면 되는데 인덱스 잘못 생각해서 자꾸 틀렸었다. 왜 틀린지 몰랐을 땐 풀기 싫어져서 잠시 내팽겨치고 있었다. bfs함수 if v_row == n-1 and v_col == m-1: 이 부분에서 n-1, m-1이 아니라 n, m으로 해놨어서 입력한 값 다 돌았는데 또 돌게된 것이었..

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net bfs......... 나 bfs 진짜 싫어....... 과제할 때 결국 못 풀고 그냥 제출한 경험이 있음.... 번아웃까지 야기했던 그 문제.... bfs....... 사실 이 문제 접근하면서 bfs를 코드로 짜는 방법을 드디어 이해한 것 같다. 큐에 넣고 빼고 하면서 이걸 어떻게 한다는 건지 학기 중에는 이해하지 못했다. 그래서 실버1이어도 긴장하면서 풀었는데...