기록공간

문제 N개의 정수를 담은 컨테이너가 주어진다. 그리고 0 (2 + 2) / 2 => 2 일때 가장 작은 평균값이 나오기 때문에 답은 P = 1 이다. 해결 방법 단순하게 위의 방법을 코드로 구현하여 접근한다면, 효율성이 떨어지게 된다. 이때 시간 복잡도는 O(N^2)이 나온다. O(N)이 나와야 효율성에서 통과가 되기 때문에, 다른 방법을 생각해야 한다. 평균값의 원리를 잘 알고 있다면, 다른 방법을 사용해 볼 수 있다. 평균값은 항상 평균값을 계산할 숫자중에 가장 작은 값보다 크거나 같다. 예를들어 (1, 2, 3)이 있다면 (1 + 2 + 3) / 3 = 2로 가장 작은 값인 1보다 크다. 이 뜻은 최소 범위에서의 평균값을 알고 있다면, 그 이후 범위의 평균값은 구할 필요가 없다는 것이다. 예를들어 ..

문제 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 소프트웨어 등에 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 하지만 주의할 점이 있는데 음의 간선은 포함할 수 없다는 점이다. 물론 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라 알고리즘은 현실 세계에 사용하기에 매우 적합한 알고리즘 중 하나이다. 다익스트라 알고리즘이 다이나믹 프로그래밍 문제인 이유는 최단 거리는 여러 개로 이루어져 있기 때문이다. 그렇기 때문에 작은 문제가 큰 문제의 부분 집합에 속해 있다고 볼 수 있다. 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 ..