-
알고리즘 문제 풀이2
알고리즘 문제 풀이 4월에 푼 재미있는 문제들의 풀이를 작성해보았습니다. 문자열 장식 N개의 문자열이 주어지면 이 문자열들을 합쳐서 만들수 있는 사전순으로 가장 앞서는 문자열을 구하는 문제입니다. 단, 각 문자열 안에서의 상대적인 순서는 유지해야합니다. 우선 상대적인 순서를 유지해야 하니까 주어진 문자열들의 앞글자부터 하나씩 때어 온다고 생각합시다. 그러면, 매순간 각 문자열의 앞글자들 중에 사전순으로 가장 작은 알파벳이 있다면 그것을 때어 오는 것이 이득이라는 것을 쉽게 알 수 있습니다. 그런데 이러한 문자열이 여러개가 있으면 어떤 문자열에서 때어오는 것이 이득일까요?...
-
특별한 정렬 알고리즘들 2
개요 이번 글에서는 지난 달 글에 이어서 조금 더 다양한 정렬 알고리즘을 소개해 보려고 합니다. 저번 글에서도 언급했지만 정렬의 종류는 엄청나게 다양하며, 이 글에서 소개하는 정렬 알고리즘들은 그들 중 극히 일부에 불과합니다. 개중에는 병렬 처리가 되거나 쓰기 연산이 극도로 비싼 등 매우 특수한 실행 환경에서만 이득이 되는 것들도 있고, 데이터가 거의 정렬된 상태에서 매우 효율적인 알고리즘, 또는 현실 세계의 데이터들에 적합하도록 고안된 알고리즘 등도 있었고, 마지막에 잠깐 언급한, 그저 재미를 위해서만 만들어낸, 비효율적이기만 한 알고리즘들도...
-
그래프 색칠과 NP-Completeness
서론 현실의 여러 대상들은 그래프로 추상화 할 수 있다. 그래프를 색칠하는 것은, 서로 인접한 두 정점이 같은 색을 같지 않도록 색칠 하는 것이다. 이 그래프를 색칠하는 문제는, 다양한 스케쥴링 문제 혹은 컴파일러의 레지스터 배치, 패턴 매칭, 시험/수업 시간표 작성 등 다양한 문제를 해결할 수 있다. 이런 문제들이 다항시간안에 검증이 가능하지만, 다항 시간안에 풀리는지는 밝혀지지 않는 NP-Complete 문제라는 것을 알아보자. 그래프 그래프는, 정점을 나타내는 집합 $V$와, 간선을 나타내는 집합 $E$의 원소인, $G = (V, E)$로 나타낸다....
-
알고리즘 문제 풀이
알고리즘 문제 풀이 3월에 푼 재미있는 문제들의 풀이를 써보았습니다. BOJ 1352번 문자열 아래와 같은 $dp$를 정의합니다. $dp(x, sum)$ := $0$~$x-1$번째 인덱스까지 처음으로 사용한 문자들의 인덱스합이 $sum$ 일 때, $x$번째 ~ 마지막까지를 적절히 정하여 길이 $N$의 ideal string 을 만들수 있는지 여부(가능하면 1, 불가능하면 0) 이 $dp$의 transition은 어떻게 될까요? 각 상태에서 선택할 수 있는 것이 무엇인지 고민해 봅시다. 각 상태에서 우리가 정해야 하는 것은 $x$번째 인덱스에 들어올 문자입니다. 우리가 이 $dp$에서 알고자 하는 것은 최종적으로...
-
기본적인 Git 사용법과 Pull Request를 통해 프로젝트 기여하기
VCS? Git? GitHub? Git이란 버전 관리 시스템(VCS, Version Control System)의 한 종류입니다. 그렇다면 여기서 말하는 버전 관리란 무엇이고, 왜 필요할까요? 버전 관리란 이름 그대로 여러 파일을 하나의 버전으로 묶어 관리합니다. A라는 소스코드의 묶음이 있을 때, 이를 버전1이라는 이름으로 저장해봅시다. 이후 버전1에서 파일을 추가하거나, 삭제하거나, 수정하는 등의 작업을 거쳐 버전2라는 이름으로 저장합니다. 마찬가지로 버전2에서 버전3를 만듭니다. 아차, 그런데 버전2에서 수정한 파일 때문인지 오류가 생겼습니다. 이때 우리는 이전에 저장해둔 버전1을 불러와 다시 작업할 수 있습니다. 만약 문제가...