코테 알고리즘

문제링크생각보다 쉽지 않았던 문제.재귀를 내릴 때 어떤 변수를 함께 내려야 하는 지 항상 생각할 것.하노이의 탑 같은 경우 링을 옮기려는 기둥의 번호를 재귀 함수의 변수로 사용하는 것이 핵심이다.중간 단계로 사용할 기둥은 set을 사용해 구함.나머지는 기초 재귀!

가장 기본적인 정렬 방법. 배열 내 원소들을 순서대로 탐색하며 뒤에 있는 원소보다 큰 원소의 경우 뒷 원소와 순서를 바꾼다.시간복잡도는 $O(n^2)$.

배열에 존재하는 원소의 갯수를 세고, 순서대로 그 배열을 나열하는 방식의 정렬. 배열의 최댓값을 $k$라 할 때 시간 복잡도는 $O(n + k)$.$k$가 크지 않다면 매우 효율적인 방법이다. 구현에는 여러 방법이 있지만 여기서는 싸피에서 배운 걸 작성한다.

카운팅 정렬을 쓰면 된다고 나와 있어서 그냥 섰다가 메모리 에러 때문에 애먹은 문제.해결법은 생각보다 단순했다. 카운팅 정렬을 사용하되, counting 배열만 저장하고 나머지는 입력을 따로 저장하지 않고 처리하는 방법론이다.

주어진 숫자들을 정렬한 결과가 $a_1, a_2,...,a_n$ 이라 하자. 그럼 문제의 조건을 만족하는 $M$은 다음과 같이 나타내어질 수 있다.$$\\begin{aligned}&a_1 = b_1 M + r \\&a_2 = b_2 M + r \\&\\dots \\

두 문제 모두 결국 팩토리얼의 0의 개수를 세야 하는 문제다. 팩토리얼 우선 쉽게 구할 수 있는 팩토리얼의 0의 개수부터 생각해보자. 2와 5가 곱해져야 0이 생기고, 팩토리얼의 결과를 소인수분해하면 5의 지수가 2의 지수보다 작을 것이므로 결국 팩토리얼 계산 중 곱해

평범한 dp문제이지만, 왜인지 안 풀리다가 나중에 내 오류를 발견한 문제. 처음 생각한 논리 구조는 다음과 같다.메모이제이션을 할 배열을 만든다. 배열의 구조는 \[\[0, 0] for \_ in range(n+1)] . 이는 \[앞 잔을 안 먹고 현재 잔 먹음, 앞

이 문제는 점화식을 아예 외워두는 것이 의미가 있을 것 같아서 기록해둔다.LCS는 Longest Common Subsequence의 줄임말로, 두 수열(문자열)의 부분 수열 중 일치하는 최장의 수열을 의미한다. 문제에서 준 예시를 보면, ACAYKP와 CAPCAK LC

처음에는 길이가 1인 부분 구간, 2인 부분 구간...해서 길이가 $n$인 부분 구간인 경우를 모두 구하려 했다. 당연히 시간 초과가 났다.찾아보니 누적합과 나머지를 사용하여 풀 수 있는 문제였다. 예시 입력인 1 2 3 1 2을 넣었을 때의 풀이과정을 보자.문제에서

${N}\\choose{R}$을 구하는 간단한 문제이지만 $N$의 범위가 너무 커 단순 계산으로 풀 수 없는 문제이다. ($N\\le4,000,000$)수의 크기를 줄이기 위해 $\\frac{N!}{(N-R)!R!}$에서 팩토리얼을 미리 $1,000,000,007$으로

다익스트라와 거의 같은 방법으로 최소 비용 경로를 찾는 알고리즘이지만, 대신 비용에 음수가 있을 경우를 가정한 방법론.$G = (V, E)$로 표현되는 그래프에서 시간복잡도는 $O(V \* E)$이다. 모든 정점의 수만큼 반복하고($V$만큼), 각 반복마다 모든 간선을

그래프 최소거리 문제 중 각 정점에서 다른 모든 정점으로의 최소거리를 구하는 문제를 푸는 알고리즘. 백준의 11404 문제가 대표적인 문제이다.구현은 간단하다. 시작점, 끝점, 중간점을 기준으로 for문을 작성하면 된다. 모든 정점에 대해 3번 반복문이 작성되므로 시간

브루트 포스 방식으로 접근할 경우 30개의 원소를 가진 배열의 부분집합을 모두 구해야 하므로 $2^{30}$의 경우의 수를 계산해야하므로 불가능하다. 따라서 수의 크기를 줄여야 한다. 두 개의 $2^{15}$짜리 문제로 바꾼 후 투 포인터 알고리즘($O(N)$)으로 두

트리의 순회 방법의 특징들을 알면 풀 수 있는 문제. 특히 순회 별 트리의 root를 찾는 방법이 중요하다.중위순회 Inorder Traversal: left - root - right 순서로 순회. root를 중간에 순회한다.전위순회 Preorder Traversal

참조: https://smartshk.tistory.com/51풀릴 듯 안 풀려서 고민하다가 결국 풀이법을 찾아본 문제. 각 도로를 queue로 구현하면 생각보다 쉽게 풀리는 문제였다.하나 더 실수했던 점은 중간에 min_time의 초기값을 float인 1e9

문제링크카카오의 해설을 참고했습니다.오랜만에 쓰는 글...자주 좀 써 봅시다.ShiftRow 연산은 마지막 행을 첫 행으로 바꾸는 것이므로 파이썬의 list를 통해 간단히 연산 가능하지만, 스택과 큐의 연산에 초점을 맞춰 구현된 deque를 쓰도록 하자.ShiftRow

문제 출처찾아보니 많은 경우 실제로 큐를 만들어 문제를 풀었던데(파이썬의 경우 deque 이용) 나는 왠지 그러면 안될 것 같아 누적합이랑 슬라이딩 윈도우로 풀었다. 다르게 풀고 싶었다기보단 그렇게 풀어야만 하는 줄 알고...근데 조건 하나 때문에 엄청 오래 걸렸다.

문제 출처 분명 별로 어렵지 않은 문제인데 생각보다 헷갈렸다. 그러다 다른 사람의 풀이를 보니 신박한 방법이 있어 따로 작성한다. 일반적인 풀이 내가 가지고 있는 콜라병의 개수를 bottlecnt라는 변수에 저장하자. bottlecnt의 초기값은 문제에서 주어진 n

문제 출처스택으로 풀 수 있는 문제의 한 종류인 것 같아서 따로 정리한다.answer 배열을 \[0, 0, 0, ...]으로, stack은 빈 리스트로 initialize한다. 문제의 배열(arr이라 하자)을 순서대로 순회하면서 "stack의 head에 있는 값"보다

문제출처참고1참고2정말정말정말 힘들었던 문제ㅎㅎㅎ사실 아직 완전히 이해를 완료하지 못했고 위 참고 사이트들의 도움 없이는 다시 풀지도 못 할 것 같지만 컨닝으로라도 문제를 푼 과정을 정리하는 것은 의미가 있을 것 같아 여기에 정리한다.괜히 주저리주저리...문제로 들어가