이분 매칭 알고리즘은 유량 그래프의 특수한 형태이다. 유량 그래프는 다음 포스팅에서 다루기로 하고... 이분 매칭 알고리즘에 대해 알아보자. 이분 매칭 알고리즘을 알아보기 전에, 이분 그래프에 대해 먼저 알고 넘어가야 한다. 이분 그래프란 정점을 두 개의 그룹으로 나누었을 때, 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 그래프를 말한다. 위의 그림에서 보면 파란색 노드의 집합을 X, 빨간색 노드의 집합을 Y로 표현할 수 있고, 따라서 위의 그래프는 이분 그래프이다. 이분 매칭 알고리즘은 위와 같은 이분 그래프에서 최대 매칭의 개수를 찾는 것과 같다. 매칭이란 간선 하나를 선택하는 것을 말하는데, 예를 들어 그림에서 A와 a를 연결하는 간선을 선택하면 (A, a)라는 매칭이 생기는 것이다..
https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 2020 카카오 공채 1차 코딩테스트 7번 문제로 출제된 블록 이동하기 문제이다. 이렇게 맵을 탐색하는 문제는 굉장히 흔한데, 그런 문제들과 이 문제의 가장 큰 차이점은 바로 로봇이 한 칸이 아닌 두 칸을 차지한다는 점이다. 또한 로봇이 이동할 때에도 두 칸이 모두 이동할 수 있어야 한다는 제약이 걸려있다. 또 이러한 점을 고려하여 로봇이 회전까지 할 수 있다... 위의 조건들을 고려..
https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 작년 하반기 카카오 공채 문제로 나왔던 표 병합 문제이다! union-find 문제인데 당시에 문제를 풀 때는 거의 마지막쯤에나 깨달아서 결국 효율성 점수를 받지 못했었다... union-find 알고리즘 자체가 어려운 편은 아니라 구현만 꼼꼼하게 한다면 충분히 풀 수 있는 문제다. 구현 문제인 만큼 문제를 꼼꼼히 읽고 시작하자! 마치 엑셀을 연상시키는 것 같은 문제였는데, 엑셀과는..
https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 카카오 인턴십 문제로 출제된 코딩 테스트 공부이다! dp 문제는 언제나 구현하는 시간보다 생각하는 시간이 길어지는 것 같다. 나는 항상 dp 문제와 그리디 문제를 헷갈려하는데, 풀 때 먼저 그리디 하게 풀려고 했을 때 직관적인 풀이가 잘 떠오르지 않으면 dp로 푸는 것 같다. 코딩 테스트 공부 문제는 완전 탐색과 dp를 결합한 문제이다. 문제 요구 사항을 살펴보자. 문제에서 초기 알..
이번에는 LCP 배열에 대해 알아보자! LCP 배열을 이해하기 위해서는 이전에 쓴 글인 접미사 배열을 우선적으로 이해해야한다. 2023.03.27 - [Algorithm] - [Algorithm] 맨버-마이어스 알고리즘(Suffix Array) [Algorithm] 맨버-마이어스 알고리즘(Suffix Array) 접미사 배열이란 특정 문자열에 대한 접미사들을 모두 나열한 뒤, 사전 순으로 정렬을 진행한 배열을 의미한다. 일반적으로 접미사 배열을 만드는 방법은 다음과 같다. 문자열에 대해 모든 접미 codable.tistory.com 위의 글에서 들었던 예시인 banana를 사용하자. LCP 배열을 만들기 위해서는 우선 해당 접미사가 정렬된 Suffix 배열에서 어느 위치에 있는지를 기록해야한다. 이를 위..
접미사 배열이란 특정 문자열에 대한 접미사들을 모두 나열한 뒤, 사전 순으로 정렬을 진행한 배열을 의미한다. 일반적으로 접미사 배열을 만드는 방법은 다음과 같다. 문자열에 대해 모든 접미사들을 만들어준다. 만들어진 접미사들을 맨 앞글자를 기준으로 정렬한다. 이후 정렬 기준을 앞에서 2번째 문자, 3번째 문자 ... 로 늘려가면서 최대 문자열의 길이인 n번째 문자까지 바꿔가며 정렬을 진행한다. 위의 과정을 따르면, 한번 정렬을 진행하는데 $O(n log n)$ 만큼의 시간이 걸리고, 정렬을 최대 문자열의 길이만큼 반복한다고 했으므로 총 시간복잡도는 $O(n^2 log n)$ 과 같이 나타날 것이다. 이를 맨버-마이어스 알고리즘을 통해 $O(n log^2 n)$의 시간복잡도로 단축시킬수 있다. 이제 정렬이 ..
이번에 풀 문제는 그래프 수정 문제이다. 위상 정렬을 활용하는 문제인데, 일단 문제를 보고 가자. - N개의 정점으로 구성된 그래프가 입력으로 주어진다. 이때 노드의 번호는 1보다 크거나 같고 N보다 작거나 같다. - 만약 노드 U에서 노드 V로 연결되는 간선이 존재한다면, 노드 V의 번호는 노드 U의 번호보다 커야 한다. - 위의 조건을 만족하도록 노드의 번호를 바꾸고, 원래의 1번 노드부터 N번 노드까지 각각 바뀐 노드의 번호를 출력해야 한다. 위의 말만 봐서는 문제에서 원하는 것이 무엇인지 정확히 감이 오지 않을 수 있다. 다음 입력값을 그림으로 나타내서 이해해 보자! n = 5 node1 : 00110 node2 : 00001 node3 : 00000 node4 : 01000 node5 : 000..
이번에 풀어볼 문제는 빙산 문제이다. 시간이 지나면서 입력으로 주어진 빙산이 녹아가는데, 빙산이 처음으로 분리되는 시간을 구하는 문제이다. 문제의 조건은 아래와 같다. 빙산이 상하좌우로 맞닿아 있는 바닷물의 칸수만큼 녹는다. 빙산이 차지하는 칸의 개수는 최대 10,000개이다. 배열의 첫 번째 행과 마지막 행, 첫 번째 열과 마지막 열에는 빙산이 존재하지 않는다. 빙산의 높이는 최대 10이다. 기본적인 탐색 문제이다. 먼저 바닷물과 맞닿아 있는 빙산들을 녹이고 나서, 아직 녹지 않은 빙산을 기준으로 탐색을 진행하여 연결된 빙산들을 모두 방문처리 해주는 방식이다. 이렇게 탐색이 한 번 진행된 이후에도 아직 방문하지 않은 빙산이 존재한다면, 빙산이 둘 이상으로 갈라지게 된 것이므로 탐색을 종료한다. 다만 이..
위상 정렬(Topology Sort)이란? 위상 정렬이란 DAG에서 정점을 선형으로 정렬한 것이다. 이때 간선의 정보가 u -> v 형식으로 주어진다면, 위상 정렬의 결과는 항상 정점 u가 정점 v보다 앞에 오게 된다. DAG(Directed Acyclic Graph) DAG는 비순환 방향 그래프를 의미하며, 사이클이 없고 간선에 방향이 존재하는 그래프를 의미한다. DAG가 아닌 그래프, 즉 간선에 방향이 없거나 사이클이 존재하는 그래프에 대해서는 위상 정렬이 불가능하다. 위상 정렬을 활용하는 적절한 예시로 대학교 선수 과목을 들 수 있다. 다음 그림과 함께 살펴보자. 위와 같이 선수 과목들이 정해져 있을 때, 자연어처리와 데이터베이스 시스템 과목을 수강하기 위해서 먼저 들어야 하는 과목을 순서대로 나열..
이번 포스팅의 주제는 최단 경로 알고리즘이다. 그래프 상에서 특정 노드에서 다른 노드까지의 최단 경로를 구하는 알고리즘인데, 대표적인 알고리즘으로 오늘 알아볼 다익스트라 알고리즘과, 추후 포스팅 할 예정인 플로이드-워셜 알고리즘, 벨만-포드 알고리즘이 있다. 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 그리디 알고리즘의 한 형태이다. 알고리즘의 진행 과정은 아래와 같다. 초기 distance table의 값을 모두 INF 값으로 설정해 주고, 시작 노드의 값만 0으로 설정한다. 현재 distance table에서 아직 방문하지 않았으며, 남은 경로 중 가장 경로가 짧은 노드에 대해서 검사를 진행한다.(초기의 경우 시작 노드) 현재 노드와 인접한 노드들을 검사한다. 현재 노드까지의 최단 경로..
