2021/03

    [Algorithm] LCA 알고리즘

    [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의 조..

    스코페 2021 후기

    스코페 2021 후기

    알고리즘 공부에 전념하고 있던 요즘 친구의 추천으로 스코페 2021에 지원하게 되었다! 떡상중인 스타트업과 함께하는 코딩테스트? 잘하면 채용기회도 준다고 한다. 하지만 지금 채용 기회에는 관심이 없당 내가 관심 있는건 바로 상금과 상품...💰 goorm 플랫폼을 사용한다는데 도대체 왜...모의테스트를 쳤는데 경험해본 코테 환경중에 제일 별로였다. 어쨌든 2차까지 꾸역꾸역 가보장! 1차 후기 코딩테스트 경험이 거의 없기 때문에 큰 기대 없이 1차 코테를 쳤는데 생각보다 너무 쉬워서 시험시간 4시간 중에 2시간 조금 넘게 사용하고 끝냈다. 특별히 이렇다 저렇다 할 알고리즘도 없었다. 생각나는 건 DP정도 올솔하고 1시간 남겨두고 그냥 나왔당 올솔했으니까 결과는 당연히 합격😊😊 하지만 2차 코테는 절대 비슷한..

    [Python] 프로그래머스 지형 이동

    [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으로..

    [Python] 프로그래머스 합승 택시 요금

    [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] Dijkstra 다익스트라 최단 경로 알고리즘

    [Algorithm] Dijkstra 다익스트라 최단 경로 알고리즘

    다익스트라 알고리즘은 A에서 B까지의 최단 경로를 찾고자 할 때 사용한다. 먼저, 알고리즘을 직관적으로 살펴보자 다음과 같은 그래프에서 A->C로 가고자 할 때 최단 경로를 구해보자. 우선 출발지로부터 인접한 노드들과의 거리를 갱신한다. (빨간색) 그 다음 노드로 이동한다. 해당 노드에서 인접한 노드들 중에 방문하지 않은 노드들 과의 거리를 갱신한다. 다음과 같이 D의 거리가 5에서 3으로 갱신 되었다. (최단 거리) C가 5에서 4로 갱신되었다. 현재 방문한 노드가 도착지라면 알고리즘을 종료한다. 그림처럼 A->C의 최단경로는 4가 된다. 위와 같이 동작하는 알고리즘이 다익스트라 알고리즘이다. 📌 Rule 1. 출발 노드로부터 인접한 노드들 사이의 거리를 갱신한다. 2. 다음 노드로 방문하여 인접 노드..

    [Python] 백준 7453

    [Python] 백준 7453

    세상 복잡하고 까다로웠다.. 이것 저것 시도해보았는데 12초나 주어진 시간이 자꾸 초과돼서 이틀이나 걸린 문제,, 비슷한 유형의 문제가 많다. 백준 1208번 문제도 같은 유형이므로 유형에 대한 설명은 아래 링크에서 참조 📌https://990427.tistory.com/48 [Python] 백준 1208 구글링이 잘 안돼서...직접 쓰는 리뷰 😅 1182번 부분수열의 합과 같은 유형의 문제이지만 범위와 시간제한 등으로 다른 풀이 방법을 적용해야한다. n개의 원소를 가진 수열의 부분 수열을 구하 990427.tistory.com 우선 1208번과 같이 딕셔너리를 사용해서 문제를 풀었더니 시간초과가 났다. 이유는 정말 모르겠다... 딕셔너리의 시간복잡도가 O(1)이긴 하지만 숨어있는 상수가 매우 크다고 한..

    [Python] 백준 1208

    [Python] 백준 1208

    구글링이 잘 안돼서...직접 쓰는 리뷰 😅 1182번 부분수열의 합과 같은 유형의 문제이지만 범위와 시간제한 등으로 다른 풀이 방법을 적용해야한다. n개의 원소를 가진 수열의 부분 수열을 구하는 방법은 2**n 이라고 한다. 이 문제의 최대 범위는 n==40이므로 최악의 경우 2**40의 복잡도를 가지게된다. 그래서 이 문제는 리스트를 반으로 나눠 반에 해당하는 부분 수열을 구할 것이다. 그럼 최악의 경우 (2**20)*2이다. (2**20)*2 = 2097152 VS 2**40 = 1099511627776 효율 ㅇㅈ? 나는 딕셔너리를 사용해서 부분 수열을 구했다. (이유는 뒤에) key : 부분 수열의 합 value : 해당 부분 수열의 합이 나온 횟수 예제를 예로 들어 코드 설명을 하자면 우선 l=[..

    [Python] 백준 1167, 1967

    [Python] 백준 1167, 1967

    입력값의 차이 외에는 똑같은 문제이다. 먼저 트리의 지름을 찾는데에는 rule이 있다. ✔ 트리에서 임의의 노드(A)를 선택해 가장 먼 노드를 찾는다. -> B ✔ B에서 가장 먼 노드를 찾는다. -> C ✔ 그러면 B와 C사이의 거리가 가장 멀다. (==지름) 이 규칙을 알면 쉽게 쉽게 풀 수 있겠다. 모르면 ㅠㅠ 삽질 하니까 알고있자... Answer 1167 import sys from collections import defaultdict from collections import deque n=int(sys.stdin.readline()) dic=defaultdict(list) for i in range(n): l=list(map(int,sys.stdin.readline().split())) a..

    [Python] 백준 10917

    [Python] 백준 10917

    어려웠던 문제는 스스로 솔브해도 다른 사람 풀이랑 비교하기 위해서 검색을 해보는데 푼 사람이 별로 없어서 검색해도 안나와서 슬펐당... 내 답이 최적인지는 모르겠으나 일단 풀었고 푼 사람이 별로 없어서 나라도 리뷰를 써놔야지,,😇 일단 나는 BFS + 우선순위Q로 풀었다. 딕셔너리를 만들고 x를 key로 y를 value로 두고, value는 우선순위Q 내림차순으로 저장했다. (꿈은 더 큰 수로 이동하고 N이 가장 크기 때문에 N을 가지고 있다면 바로 그만 할 수 있게하기 위함) 그리고 queue에 현재 위치와 현재 상황이 바뀐 횟수를 저장하며 BFS를 한다. N을 만나면 그만한다. (bfs니까 처음만날 때 최소) Result import sys from collections import defaultdi..

    [Python] 백준 2089

    [Python] 백준 2089

    덕분에 파이썬에서 a//b가 어떻게 동작하는지 정확히 알 수 있었다. 이렇게 동작한다고 한다. import sys n = int(sys.stdin.readline()) if n == 0: print(0) else: res = [] while n != 0: if n%(-2) == 0: res.append('0') n = n//(-2) else: res.append('1') n = n//(-2) +1 print(''.join(reversed(res)))