기록공간

문제 A, C, G, T는 순서대로 1, 2, 3, 4 값이다. 즉 A < C < G < T이다. A, C, G, T를 입력한 문자열 S와 탐색할 범위 P[i] ~ Q[i] 가 주어진다. 탐색 범위에 들어있는 알파뱃 중 가장 값이 작은 것을 컨테이너에 담아 출력하면 되는 문제이다. 예를 들어 CAGCCTA를 S로 입력받았고, P와 Q는 다음과 같이 입력되었다고 가정하자. P[0] = 2 Q[0] = 4 P[1] = 5 Q[1] = 5 P[2] = 0 Q[2] = 6 i가 0일때 범위는 2 ~ 4번째 까지이다. 2번째 인덱스 G부터 4번째 인덱스 C까지 범위에서 가장 작은 알파뱃은 C이므로 정답은 2이다. i가 1일때 범위는 5번째이므로, 5번째 알파뱃 T가 가장 작으므로 정답은 4이다. i가 2일때 범위..

문제 A와 B 사이에 있는 수들 중 K와 나눠지는 개수를 출력하는 문제이다. 해결 방법 갯수만 출력하면 되기 때문에 A부터 B까지 반복하며 K와 나눠지는지 검사할 필요가 없다. A가 0일 경우 B까지의 K로 나눠지는 숫자의 개수는 (B / K) + 1이다. 1이 더해지는 이유는 0일 때에도 K와 나눠지기 때문이다. A가 0이 아닐 경우에는 0부터 B까지의 개수인 (B / K) + 1에서 A까지 K와 나눠지는 개수를 빼주면 된다. 만약 A가 K와 정확히 나눠진다면 (B / K) + 1 - (A / K) 를 해주면 된다. 만약 그렇지 않은 경우 (B / K) + 1 - ((A / K) + 1)을 해주면 된다. 둘의 차이는 A를 K로 나눠지는 것을 포함하느냐 안 하느냐의 차이이다. 코드는 다음과 같다. int..

문제 주어진 N개의 원소들을 담은 컨테이너에 1 ~ N까지 모두 존재하는지 확인하면 되는 간단한 문제였다. 해결 방법 주어진 컨테이너 원소들을 오름차순 정렬 한 후 차례대로 탐색하며 1부터 N까지 있는지 검사하면 된다. 만약 없는 경우 바로 0을 리턴한다. 반복문을 정상적으로 마친 경우 1을 리턴한다. 코드는 다음과 같다. #include #include using namespace std; int solution(vector& A) { int check = 1; sort(A.begin(), A.end()); for (const auto iter : A) { if (iter != check++) return 0; } return 1; }

올해 졸업을 마치고, 공채 취업을 위해 필요한 기본기를 익히기 위해 지금까지 달려왔다. 학교에서 못했던 각종 컴퓨터 지식을 꾸준히 공부하고 부족한 포트폴리오를 새로 만들거나 고쳐나갔다. 상반기를 노리면서 준비했지만, 공채공고를 낸 게임 회사는 정말 별로 없었다. 그 중 두 회사를 지원했지만, 결과적으로 모두 안좋은 결과를 가져 왔다. 취업 준비를 하면서 점점 게임업계에 대한 회의감이 들기 시작한건 이 시점부터가 아닐까 생각한다. 우리나라 게임은 내가 원하는 방향과는 전혀 반대의 길을 가고 있다고 생각한다. 정말 게임다운 게임을 만들고 싶어서 이 분야를 택했지만, 현재 상황과 전망을 살펴보면 이러한 꿈을 이루기 위해서는 우리나라를 떠나는 방법밖에는 없다고 생각한다. (인디게임 제작을 생각해 볼 수도 있겠다..

문제 주어진 숫자들 중 연속되지 않고 중간에 비어 있는 숫자가 있는 경우 가장 작은 정수를 출력하는 문제이다. (이 정수는 0보다 크다) 만약 연속으로 끝까지 이어진 경우에는 그 이후의 숫자를 출력하면 된다. 그리고 음수만 존재하는 경우에는 조건을 만족하는 가장 작은 정수인 1을 출력하면 된다. 해결 방법 우선 주어진 숫자가 순서가 맞아야 쉽게 정답을 찾을 수 있으므로 오름차순 정렬한다. 음수만 있는 경우를 알 수 있도록 가장 끝 값이 음수인지 검사한다. 만약 음수라면 1을 출력한다. 이제 처음부터 끝까지 반복하며, 중간에 숫자가 비었는지 검사한다. 음수는 정답에 포함되어 있지 않으므로 생략하고 진행한다. 만약 이전 값과 현재 값의 차가 2이상이라면 중간에 숫자가 한가지 이상 비어있다는 것으로 현재 값의..

문제 입력 된 숫자를 이진수로 변환시키고, 변환된 이진수중 1과 1 사이에 있는 0이 가장 많은 경우 0의 갯수를 출력하는 문제이다. (다만 1과 1사이에 있지 않은 0은 포함되지 않는다.) 예를들면, 1041 숫자는 이진수로 변환하면 10000010001이다. 1과 1 사이에 있는 0은 앞에 5개, 뒤에 3개가 있다. 그러므로 가장 많은 경우의 5개를 출력하면 된다. 해결 방법 우선 이진수로 변환하는 방법은 이전에 사용하였던 것이다. 비밀지도 (프로그래머스) 이진수로 변환하는 방법만 안다면 어렵지 않게 풀 수 있는 문제이다. 이진수 변환에는 쉬프트 연산을 사용하였다. 예를 들어 9를 이진수로 변환한다고 하자. 9의 이진수는 1001이다. (전체 이진수 lipcoder.tistory.com 코드는 다음과..

개요 허프만 코딩(Huffman coding)은 텍스트 압축을 위해 널리 사용되는 방법으로, 원본 데이터에서 자주 출현하는 문자는 적은 비트의 코드로 변환하여 표현하고 출현 빈도가 낮은 문자는 많은 비트의 코드로 변환하여 표현함으로써 전체 데이터를 표현하는데 필요한 비트 수를 줄이는 방식이다. (마치 UTF-8과 비슷하게 동작한다) 이러한 압축 과정에서 가장 중요한 부분이 각 문자를 표현하기 위한 허프만 트리(Huffman tree)를 구성하는 것인데, 예를 통해 그 과정을 이해해 보자. 원리 다음의 텍스트를 허프만 코딩을 통해 압축해 보려고 한다. AAAAAAABBCCCDEEEEFFFFFFG 우선 원본 데이터에 포함된 각 문자에 대한 출현 빈도수를 구하여 내림차순으로 정렬한다. A(7개) F(6개) E..

개요 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(short path)탐색 알고리즘이다. 보통 인공위성 GPS 소프트웨어 등에 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 하지만 주의할 점이 있는데 음의 간선은 포함할 수 없다는 점이다. 물론 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라 알고리즘은 현실 세계에 사용하기에 매우 적합한 알고리즘 중 하나이다. 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리는 여러 개로 이루어져 있기 때문이다. 그렇기 때문에 작은 문제가 큰 문제의 부분 집합에 속해 있다고 볼 수 있다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 ..