Leta Learns

# 최대 최소 - 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역량테스트, 코드트리와..

문제 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 함수 내부에..

지난 주 초반에 풀다가 못 풀어서 포기한 문제인데 드디어 풀었다. 친구랑 같이 상의해 본 문제긴 한데 그래도 내 코드로 풀고 싶어서 계속 붙잡고 있다가.. ㅋㅋ 며칠 동안 계속 안 풀려서 그냥 친구 코드 참고했다. 내 기존 코드에서는 원산지 여부를 if문에 all() 함수를 사용해서 처리했다. 유향 그래프이므로 인접리스트에 해당 값이 요소로 들어가있지 않으면 원산지이기 때문. 근데 이 방식으로 했더니 원산지가 검거되어도 dfs는 계속 돌아가는 문제가 생겼다. 원산지가 검거되면 해당 원산지로부터 공급받는 곳을 dfs로 확인할 필요가 없다. 따라서 root 리스트를 만들어서 원산지 여부를 확인하고 원산지이고, 해당 노드를 방문하지 않은 경우에만 dfs를 돌려주었다. 이렇게 하면 두 원산지로부터 공급받는 노드..

LCA (Lowest Common Ancestor) 알고리즘 : 최소 공통 조상을 찾는 알고리즘 즉, 두 노드에서 가장 가까운 공통 조상을 찾는 알고리즘 Segment Tree를 사용한 방법, DP를 사용한 방법이 존재하는데 DP 사용법에 대해서 공부하였다. 9와 6의 최소 공통 조상 : 2 4와 10의 최소 공통 조상 : 8 2와 15의 최소 공통 조상 : 1 LCA 접근법 최소 공통 조상 찾는 방법 : 각 노드에서 부모를 타고 올라가서 같은 부모를 찾는다. 이때, 양 노드의 레벨이 같아야 함. => 각 노드의 부모와 레벨을 알아야 하고, 트리가 있어야 함 각 노드의 부모 노드, 레벨 저장하는 법 => DFS 사용 재귀를 한 번씩 돌 때 마다 레벨 += 1, 부모 노드 또한 저장 가능. ex) 6과 1..

최단 경로 알고리즘 (Shortest Path) 그래프에는 어떤 정점에서 다른 정점으로의 사이를 잇는 최단 경로를 구하는 알고리즘이 존재한다. ( != MST ) MST : N-1개의 간선으로 최소 가중치 트리 만듦 그래프 내의 모든 간선의 가중치가 0 이상인 경우 => Dijkstra 알고리즘을 이용한다. 그래프가 음수 가중치 간선을 포함하는 경우 => Bellman-Ford 알고리즘을 이용한다. Dijkstra 알고리즘 출발 정점으로부터 가장 가까운 아직 방문하지 않은 정점을 찾고, 다른 모든 정점까지의 거리에 대해서 선택된 정점을 지나서 가는 경우와, 직접 가는 경우 중 최솟값으로 최단 거리를 갱신해가면서 가장 가까운 정점을 하나씩 방문한 정점 집합에 추가하는 방식으로 최단 경로를 갱신. (음의 간..

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

골드1... 함부로 건드리면 안된다... 진짜... 문제부터 잘 이해가 안 돼서 계속 읽었다. 겨우겨우 이해한 바는 각 노드에서 나아갈 수 있는 방향은 '우수마을' or 'not 우수마을' 이렇게 두 가지 경우. 루트 노드가 우수 마을이면 하위 노드는 우수 마을 일 수 없다. 루트 노드가 우수 마을이 아니면, 하위 노드는 우수 마을이거나 아니거나. (둘 중 최댓값....아마도) 이걸 dp에 저장하는 게 역시나 난관이었는데 dp[i][0] : 현재(i) 마을이 우수 마을이 아닌 경우 dp[i][1] : 현재(i) 마을이 우수 마을인 경우 로 저장했다. 제출했는데 recursion error 떠서 절망적이었다.. 근데 recursionlimit 풀어주니까 바로 됐다. 사실.. 어떻게 이렇게 빨리 풀 수 있었..

Bellman-Ford Algorithm : 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 가중치가 음수일 때도 사용 가능 다익스트라 알고리즘에 비해 느리므로 가중치가 모두 양수인 경우 굳이 벨만포드 사용할 필요 x. 다익스트라 쓰면 됨. Bellman-Ford 알고리즘의 특징 음수 가중치가 있는 그래프의 시작 정점에서 다른 정점까지의 최단 거리를 구할 수 있다. 음수 사이클 존재 여부를 알 수 있다. => 그래프 정점 개수를 v라고 할 때 인접 간선을 검사하고 거리 값을 갱신 (갱신 과정은 v-1번으로 제한) => 그래프의 시작 정점에서 특정 정점까지 도달하기 위해 거치는 최대 간선 수: v-1개 => v번째 간선이 추가되면 사이클이라고 판단 Bellman-Ford 과정 1. 시작 정점 결정..

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