o_onn5

이분매칭 알고리즘이란? 2개의 정점 그룹이 있을 때, 그룹에서 그룹으로 정점의 최대 매칭을 찾는 알고리즘입니다. 아래와 같은 두 그룹의 정점이 있다고 합시다. 각 그룹을 연결할 수 있는 간선의 정보입니다. A: 2, 5 B: 2, 3, 4 C: 1, 5 D: 1, 2, 5 E: 2 위 간선들 중에서 정점을 한 번만 사용해서 최대 매칭을 이룰 수 있게 만드는 것이 이분매칭 알고리즘의 목적입니다. 알고리즘은 깊이 우선 탐색(DFS)로 진행이 되며, 과정은 아래와 같습니다. 우선 A와 매칭이 가능한 1을 매칭 시킵니다. 현재 연결 정보 A -- 2 B -- C -- D -- E -- A는 매칭했으니 B를 보도록 합시다. B를 2와 매칭시키려했는데 이미 A가 차지했네요. 이런 경우는 이전에 매칭됐던 A가 양보를..

알고리즘이번에 방학하고 알고리즘 공부하는게 재밌어서 학업과 계속 병행중에 있다. 틈틈이 시간 날때마다 푸는중. 현재 백준으로 진행중인데 이제 프로그래머스와 코드포스도 같이 해볼까 생각중이다. 백준현재 백준 solved 티어다. 3월 초에는 플래티넘 찍을거고, 매일 한 문제씩 계속 푸는 게 목표다. 중간에 스트릭 깨진게 너무 아쉽다... solved가 오전 6시에 업데이트하는 것을 몰랐어서 오전 1~2시쯤에 풀고 기록이 전날에 됨ㅠㅠ 그 이후로는 주의하면서 스트릭 유지 중. 코드포스백준에 있는 칼라 닉네임이 너무 멋졌다. 그래서 나도 닉네임 색깔 바꾸려고 코포 도전한다ㅋㅋㅋㅋ 동기가 유치하긴한데 뭐 어떤가. 하는게 중요한거지. 코드포스 div2 대회가 있길래 최근에 한 번 신청했는데 한 문제만 맞고 시간이..

https://www.acmicpc.net/problem/10875 10875번: 뱀 가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 www.acmicpc.net 문제 가로 길이와 세로 길이가 모두 2L + 1인 2차원 격자판이 있다. 이 격자판의 각 칸을 그 좌표에 따라 (x, y)로 표현하기로 한다. 격자판의 가운데 칸의 좌표는 (0, 0)이고, 맨 왼쪽 맨 아래 칸의 좌표는 (−L, −L), 그리고 맨 오른쪽 맨 위 칸의 좌표는 (L, L)이다. x좌표는 왼쪽에서 오른쪽으로 갈수록, y좌표는 아래에서 위로 갈수록 증가한다. 이 격자판의..

seq2seq 모델의 문제 2가지 앞서 배운 seq2seq 모델에는 문제점이 있었습니다. 첫째, 하나의 고정된 크기의 벡터에 모든 정보를 압축하려고 하니까 정보 손실이 발생합니다. 둘째, RNN의 고질적인 문제인 기울기 소실(vanishing gradient) 문제가 존재합니다. seq2seq의 대안 어텐션 메커니즘 어텐션 메커니즘의 아이디어는 다음과 같습니다. 디코더에서 출력 단어를 예측하는 매 시점(time step)마다, 인코더에서의 전체 입력 문장을 다시 한 번 체크를 해줍니다. 이때 해당 time step에서 예측해야할 단어와 가장 연관성이 높은 입력 단어를 더 집중(attention)해서 봅니다. 아래 그림을 통해서 전체적인 어텐션 메커니즘을 이해해봅시다. i am a student → je ..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번..

seq2seq seq2seq는 대표적으로 번역기 또는 챗봇에서 사용되는 모델이다. RNN의 구조를 어떻게 만들었냐에 따라서 seq2seq이 만들어지는데 아래 그림을 보면서 이해해보자. 영어 문장을 입력 받고 seq2seq을 통과하여 프랑스어로 출력하는 모습을 볼 수 있다. 크게 인코더와 디코더로 구성이 되어있고 인코더에서 입력받은 문장을 압축하여 CONTEXT라는 하나의 벡터가 되고, 이 벡터는 디코더의 입력벡터로 들어가게 된다. 즉, 입력문장 ->인코더 -> 컨텍스트 벡터 -> 디코더 -> 출력문장으로 진행이 된다. 인코더와 디코더의 내부에 대해 조금 자세히 알아보자. 인코더 위 사진을 보면 입력 문장이 단어 단위로 토큰화가 진행된 것을 확인할 수 있다. 각 단어 토큰은 RNN 셀의 각 시점이 된다(실..

https://www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다. 출력 GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다. n이 주어졌을 때 n이하의 서로소 개수를 구하면 된다는 뜻이다. 이 문제를 해결하는 기가 막힌 공식이 있다. 오일러 피 함수인데 n이하의 서로소 개수를 구하는 ..

모델에 학습을 시켰지만 정작 테스트 할 때 모르는 단어가 나오면 문제를 해결하는 데 힘들어질 수 밖에 없다. 이러한 상황을 OOV(Out-of-Vocabulary) 문제라고 한다. OOV의 문제를 최소화하기 위해서 하나의 단어를 여러 서브워드로 분리하는 작업을 하는 데 이를 서브워드 분리(Subword segmentation)이라고 한다. ex) birthplace = birth + place 대표적인 서브워드 분리 알고리즘인 BPE에 대해 알아보자. BPE(Byte Pair Encoding) BPE는 기본적으로 데이터 압축 알고리즘이다. 간단한 작동 방법에 대해 알아보자. 아래와 같은 문자열이 주어졌다고 하자. aaabdaaabac aa가 반복되어 나온다. aa를 Z로 치환하자. ZabdZabac ab..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이나믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시..

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 인터넷 방송 KOI(Korea Open Internet)의 음악 프로그램 PD인 남일이는 자기가 맡은 프로그램 '뮤직 KOI'에서 가수의 출연 순서를 정하는 일을 매우 골치 아파한다. 순서를 정하기 위해서는 많은 조건을 따져야 한다. 그래서 오늘 출연 예정인 여섯 팀의 가수에 대해서 남일이가 보조 PD 세 명에게 각자 담당한 가수의 출연 순서를 정해오게 하였다. 보조 PD..