Leta Learns

문제 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()))으로 했더니 그냥..

#subproblem을 그대로 합치면 되는 DP - 피보나치 수 https://www.codetree.ai/missions/2/concepts/6/problems/fibonacci-number/description 코드트리 삼성 SW역량테스트, 코드트리와 함께 www.codetree.ai n = int(input()) def fibonacci(n): if n = coin[j-1]: dp[i] = min(dp[i], dp[i - coin[j-1]] + 1) if dp[m] == float('inf'): print(-1) else: print(dp[m]) 아 이 문제는 너무 어려웠다.. 해설 다시 보면서 공부 더 해야 할 것 같다... DP 점화식 고안하는 거 너무 어렵다.. 전에는 그래프가 더 어렵다고 생..

#DFS 탐색 - 그래프 탐색 https://www.codetree.ai/missions/2/concepts/4/problems/graph-traversal/description 코드트리 삼성 SW역량테스트, 코드트리와 함께 www.codetree.ai import sys input = sys.stdin.readline def dfs(v): visited[v] = 1 for i in range(len(adjList[v])): w = adjList[v][i] if not visited[w]: dfs(w) n, m = map(int, input().split()) adjList = [[] for i in range(n+1)] visited = [0 for i in range(n+1)] for i in ran..

문제 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 ..

# 최대 최소 - n개의 숫자 중 최소 https://www.codetree.ai/missions/2/concepts/1/problems/min-of-n-num/description 코드트리 삼성 SW역량테스트, 코드트리와 함께 www.codetree.ai n = int(input()) arr = list(map(int, input().split())) min1 = min(arr) print(min(arr), arr.count(min1)) - n개의 숫자 중 최대 2개 https://www.codetree.ai/missions/2/concepts/1/problems/two-max-of-n-num/description 코드트리 삼성 SW역량테스트, 코드트리와 함께 www.codetree.ai n = int..

#단순 반복문 - 19단 출력 https://www.codetree.ai/missions/2/concepts/1/problems/nineteen-times-table/description 코드트리 삼성 SW역량테스트, 코드트리와 함께 www.codetree.ai for i in range(1, 20): for j in range(1, 20, 2): if j == 19: print(i,"*",j,"=",i*j) else: print(i,"*",j,"=",i*j,"/",i,"*",(j+1),"=",i*(j+1)) - 별 그리기 https://www.codetree.ai/missions/2/concepts/1/problems/star-drawing/description 코드트리 삼성 SW역량테스트, 코드트리와..