S E P H ' S

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제풀이 처음 풀었던 풀이는 idx 값과 코어 작업시간을 필드로 갖는 Core 클래스를 만들었다. 그 뒤로 PQ를 사용하여 n 이 0이 될때까지 조건에 맞춰 n을 조작했다. 작업이 처리되는 경우는 현재 코어의 작업처리 시간과 현재시간이 같거나, 현재 코어 작업처리 시간이 현재 시간보다 큰 경우이다. 현재 코어 처리시간이 큰 경우는 현재 시간을 코어 시간으로 처리해준다. 그 다음 남은 작업이 없다면 반복문을 종료시키고 그때의 코어 인덱스를 반환하게하고 아직 작업이 남았다면 PQ에 새 코어를 만들고 그 코어의 작..

MST(Minimum Spanning Tree) 최소 신장 트리 그래프의 모든 정점을 사이클 없이 잇는 (신장 트리) 트리에서 간선의 가중치의 합이 최소가 되는 트리를 말한다. 크루스칼 알고리즘 간선 중심으로 최소 신장 트리를 구하는 알고리즘. 간선이 적을때 프림 알고리즘보다 유리하다. 내부적으로 union-find 알고리즘을 사용 간선들을 가중치의 오름차순 정렬하여 가장 작은 간선을 선택한다. 그 간선이 지금까지 만들어진 MST와 싸이클을 형성한다면 제외하고 아니라면 MST에 추가한다. 모든 간선에 대해 반복한다. 프림 알고리즘 정점 중심으로 최소 신장 트리를 구하는 알고리즘 정점이 적을때 크루스칼 알고리즘보다 유리 임의의 정점 선택 그 정점과 인접한 정점을 잇는 간선 중 가중치가 가장 낮은 간선 선택..

최소 공통 조상 LCA(Lowest Common Ancestor) 알고리즘 LCA(Lowest Common Ancestor)는 주어진 두 노드 a, b의 최소 공통 조상을 찾는 알고리즘이다. 예를 들어 아래의 트리에서 5번과 6번의 최소 공통 조상 LCA는 2번 노드이다. 일반적인 LCA 풀이방법 1번 루트노드를 기준으로 DFS 탐색을 하면서 각 노드의 트리의 높이(h)와 부모 노드(parent)를 저장한다. LCA 를 구하기 위한 a, b 노드가 주어지면 해당 두 노드의 h를 일정하게 맞춘다. (a의 높이 == b의 높이) 높이가 맞춰졌으면 각 부모 노드가 일치할 때 까지 비교하여 구한다. (최대 LCA는 루트노드 1) LCA를 찾는 과정을 보면 탐색을 할 때 편향트리를 만나게 되면 엄청 많은 반복을 ..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제풀이 키포인트는 이진 트리를 이해하고 응용할 수 있는지와 트리의 성질을 이용해 답을 도출해나갈 수 있는지 두 가지로 보았다. 트리의 성질을 더욱 잘 이해하고 있어야 하는 이유가 있는 문제였다. 트리를 활용한 기본 문제들은 입력에서 자식 노드의 인덱스들을 parentIdx * 2 (왼쪽 자식 인덱스), parentIdx * 2 + 1 (오른쪽 자식 인덱스) 그대로를 주는 문제들이 대부분이었다. 다시 말하자면 부모 인덱스가 무조건 자식 인덱스보다 작았었다. 하지만 이 문제의 입력값을 보자면 부모 인덱스가 자식 인덱스보다 값이 큰 경우도 확인해볼 수 있다. 그래서 ..