본문 바로가기

Algorithm

Algorithm/Tip 2021. 3. 28. [Algorithm] LCA 알고리즘 LCA는 "Lowest Common Ancestor" 가장 가까운 공통 조상을 찾는 알고리즘이다. 백준 3584번을 풀면서 이해해보장 www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 해당 트리에서 3번과 2번의 가장 가까운 공통 조상은 10번이라는 것을 바로 알 수 있다. 그렇다면 a와b가 주어졌을 때 알고리즘으로 최소 공통 조상을 찾아보자. Rule 📌 a의 조상을 모두 찾아 리스트로 만든다. 📌 b의 조..
Algorithm/Solution 2021. 3. 11. [Python] 프로그래머스 지형 이동 문제 programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 계속 틀려서 다른 사람의 풀이를 보고 푼 문제이다. 어떻게 이런생각을 떠올리지...? heap을 사용해서 풀었다. 상,하,좌,우 칸 중에 방문하지 않은 칸과의 길이가 height보다 크다면 heap에 차이와 점을 기록한다. height보다 작다면 0과 점을 기록한다. 이를 이용해서 min heap으로..
Algorithm/Solution 2021. 3. 11. [Python] 프로그래머스 합승 택시 요금 문제에 대한 자세한 설명은 아래 링크 참조 programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr Dijkstra 알고리즘을 사용해서 풀었다. (최단거리..
Algorithm/Tip 2021. 3. 11. [Algorithm] Dijkstra 다익스트라 최단 경로 알고리즘 다익스트라 알고리즘은 A에서 B까지의 최단 경로를 찾고자 할 때 사용한다. 먼저, 알고리즘을 직관적으로 살펴보자 다음과 같은 그래프에서 A->C로 가고자 할 때 최단 경로를 구해보자. 우선 출발지로부터 인접한 노드들과의 거리를 갱신한다. (빨간색) 그 다음 노드로 이동한다. 해당 노드에서 인접한 노드들 중에 방문하지 않은 노드들 과의 거리를 갱신한다. 다음과 같이 D의 거리가 5에서 3으로 갱신 되었다. (최단 거리) C가 5에서 4로 갱신되었다. 현재 방문한 노드가 도착지라면 알고리즘을 종료한다. 그림처럼 A->C의 최단경로는 4가 된다. 위와 같이 동작하는 알고리즘이 다익스트라 알고리즘이다. 📌 Rule 1. 출발 노드로부터 인접한 노드들 사이의 거리를 갱신한다. 2. 다음 노드로 방문하여 인접 노드..
Algorithm/Solution 2021. 3. 9. [Python] 백준 7453 세상 복잡하고 까다로웠다.. 이것 저것 시도해보았는데 12초나 주어진 시간이 자꾸 초과돼서 이틀이나 걸린 문제,, 비슷한 유형의 문제가 많다. 백준 1208번 문제도 같은 유형이므로 유형에 대한 설명은 아래 링크에서 참조 📌https://990427.tistory.com/48 [Python] 백준 1208 구글링이 잘 안돼서...직접 쓰는 리뷰 😅 1182번 부분수열의 합과 같은 유형의 문제이지만 범위와 시간제한 등으로 다른 풀이 방법을 적용해야한다. n개의 원소를 가진 수열의 부분 수열을 구하 990427.tistory.com 우선 1208번과 같이 딕셔너리를 사용해서 문제를 풀었더니 시간초과가 났다. 이유는 정말 모르겠다... 딕셔너리의 시간복잡도가 O(1)이긴 하지만 숨어있는 상수가 매우 크다고 한..
Algorithm/Solution 2021. 3. 8. [Python] 백준 1208 구글링이 잘 안돼서...직접 쓰는 리뷰 😅 1182번 부분수열의 합과 같은 유형의 문제이지만 범위와 시간제한 등으로 다른 풀이 방법을 적용해야한다. n개의 원소를 가진 수열의 부분 수열을 구하는 방법은 2**n 이라고 한다. 이 문제의 최대 범위는 n==40이므로 최악의 경우 2**40의 복잡도를 가지게된다. 그래서 이 문제는 리스트를 반으로 나눠 반에 해당하는 부분 수열을 구할 것이다. 그럼 최악의 경우 (2**20)*2이다. (2**20)*2 = 2097152 VS 2**40 = 1099511627776 효율 ㅇㅈ? 나는 딕셔너리를 사용해서 부분 수열을 구했다. (이유는 뒤에) key : 부분 수열의 합 value : 해당 부분 수열의 합이 나온 횟수 예제를 예로 들어 코드 설명을 하자면 우선 l=[..