알고리즘 문제풀이 기법

격자에서의 완전탐색을 해야한다면, 바로 이 테크닉이다. dfs, bfs, 완전탐색 시뮬레이션 등등 아마 제일 많이 사용되는 테크닉 아닐까 생각된다. 구현방법은 간단하다.이런식으로 4방향으로 이동할 수 있는 좌표를 만들고, 그 방향으로 이동하도록 for 문을 돌리면 된다

코딩테스트에 밥먹듯이 나온다는 그 유형이다. 대부분의 문제는 이중배열 격자를 주고, 그 안을 전부 탐색하면서 답을 찾는 문제인데 이중배열이라 함은 보통 O(n^2)의 시간복잡도를 가지기때문에, 이를 잘 해결해야하는 문제이다. 대표 유형 몇가지를 살펴보도록 하겠다. 현재

백트래킹은 사실 엄청 어렵다고 생각한다. 이론적으로는 쉬운데, 그걸 실제 문제에 적용하기가 진짜 어렵다고 느낀다. 그래도 문제는 풀어야겠으니 유형을 좀 살펴보도록 하겠다. 그리고 백트래킹은 대부분 DP나 dfs로도 풀 수 있을거같다?우선 백트래킹의 기본은 재귀함수이다.

그래프탐색의 기본이 되는 DFS, BFS 인데 사실 둘이 코드도 거의 유사하고, 문제들도 특정 문제들을 뺴면 둘다 사용해서 풀 수 있다. 보통은 BFS로 많이 푸는것같다.그래프의 탐색이지만, 실제로는 격자위에서 움직이는 문제가 더 많다. 만약 그래프 탐색이라면 자료구조

Dynamic Programing은 큰 문제를 작은 문제로 나눠서 푸는 유형이다. 사실 이게 백트래킹보다 훨씬 어렵다.dp를 풀 떄, Top-down tabulation으로 풀거나, memoization으로 풀거나 두가지 방식이 있는데 tabulation만 알아도 된다

동전을 n개 주고 m의 거스름돈을 준다고 할때 최소로 줄 수 있는 동전의 수를 찾는 문제이다. 접근방식은 다음과 같다.dp0 = 0이다. 만약 j번째 동전을 뽑는다고 하면, i의 값이 j번째 동전의 값 coinj 보단 커야한다. 작다면 그 자리에 들어갈 수 없기 때문이

사실 피보나치는 nacci라고 한다.백준 1003번 문제이다. 친절하게 식까지 주길래 뭐지 싶었는데 역시나 풀이시간 함정이 있는 문제였다.이렇게 풀면 시간초과가 난다. 그럼 어떻게 풀어야할까? 처음에는 이 방식에서 memoization을 쓰면 되지 않을까 생각해서 코드

문제알면 쉽지만 모르면 못푸는 dp문제다.패드산지가 반년인데 필기어플을 아직도 안샀다그림을 보면서 이해하면 편한데 1일때는 1타일 하나만 들어가서 dp1 = 12일때는 11, 00 두개가 가능해서 dp2이다.3일때는 어떨까?우선 00타일을 고정으로 놓자. 남은 자리는

각 계단 별로 점수가 있고 계단이 있고, 그 계단을 한칸, 두칸씩 올라갈 수 있고 연속해서 3개는 접할 수 없는 조건을 가진 문제들이다.이 조건들을 정리하면1\. 1칸 혹은 2칸씩 이동 가능2\. 3개 연속으로는 불가능이다. 가끔 포도주 마시기라던가 다른 형태로도 나온

LIS에 대한 설명은 문제를 읽어보면 이해가 빠를것이다.6개의 수를 가진 수열 10 20 10 30 20 50이 있다고 하자.이때 최장 증가 부분수열을 어떻게 구해야할까?일단 모든 자리는 기본적으로 1이라는 최장수열을 가진다. 자기자신이 그 수열이 되기 때문이다.2번째

크냅색각 물건별로 value와 weight가 주어지고, 이 값에 맞추서 배낭에 물건을 넣어서 가장 가치가 높은 경우를 찾아내는 문제이다.이는 Brute-Force로 푸는 방법이다. 다만 이는 2^n시간복잡도를 가지고, 아마 이렇게 푸는 일은 없을것이다.이는 그리디 방식

다른 언어들과 비슷하게 std::algorithm 안에 sort라는 아주 강력한 정렬함수가 내장되어 있지만, 이것만 가지고는 못푸는 문제들이 진짜 많다.문제다른 정렬문제에 비해 유난히 정답률이 낮다... 아마 통상적으로 counting을 풀면 timeout이 나오기 때

편하게 받으려고 vector로 값들을 받았는데 이게 실수였다. vector로는 counting 정렬을 정확하게 구현할 수가 없다.일단 값들을 arr로 받아야 counting 처리하기가 편하고 counting으로 최빈값을 받을 때, 한번의 for문으로 처리하기보다는, 최

손으로하면 참 쉬운 최대공약수 (GCD), 최소공배수(LCM)가 코드로 짜면 좀 쉽지가 않다. 그래서 우리가 쓰는게 유클리드 호제법이다.원리는 인터넷 찾아보고 n m 이 있을 때, m == 0이면 gcd는 n그렇지 않으면 gcd(m, n % m) 반환

검문은 영어로 SwordGate이다. 유난히 정답률이 낮은 문제인데 직관적인 풀이법은 시간초과가 나서 그런거같다.컴퓨터 성능이 발달하니깐 실제 코테에서는 시간좀 낭낭하게 주면 좋겠다... 문제의 조건을 정리하면1\. N개의 숫자를 입력받는다.2\. 이 입력받은 숫자들을

이항계수를 구하는 방법은 몇가지가 있겠지만, 난 그냥 기억하기 편하게 백트래킹으로 풀기로 했다. pick함수는 5개중 2개를 백트래킹으로 고를 때 쓴다. 원래대로면 count++자리에 cout든 뭐든 문제조건에 맞는게 들어아겠지만 아무튼 이렇게 풀어도 풀린다.이번에는

어려운 계단수백준 10844번이다.45656 이라는 수는 각 수간의 격차가 1이다. 이를 우리는 길이가 5인 계단수라고 부른다.문제는 n자리수의 계단수를 구하는 문제이다.길이가 1인 계단수는 1 2 3 4 5 6 7 8 9이다. 조건상 0으로 시작하는 수는 빠졌기에 9

Longset Common Substring과 Longest Common Subsequence 두가지 의미가 있다,둘이 꽤 다르다.최장 공통 문자열을 의미한다. 예를들어서, ABCDEF 와 GBCDFE가 있다면, 최장 공통 문자열은 BCD이다. 즉, 연속된 '문자열'중

이 문제들은 사실 그렇게 어렵지는 않다. 근데 대부분 시시간제한에 걸린다. 따라서 그냥 푸는걸 넘어서 빠르게 푸는게 필요하다. arr= 1, 2, 3, 4, 5가 있다고 하자. 이를 입력받으면서 동시에 이전자리수까지의 합을 전부 더해준다.그러면 sum = 1, 3, 6

젤다수열이 주어지고, 그 수열들의 부분합중에서 m으로 나누어지는 값을 구하는 문제이다. 역시나 시간부족으로 틀린다.브루트포스로 전부다 하나씩 방문해보는 방식이다.당연히 시간초과다. 이렇게 풀렸다면 골3이 아니겠지...검색해본 결과 이 문제는 PrefixSumj - Pr

문제는 복잡하지만 아무튼 부분합을 구하는 문제이다.조건이 좀 널널한 버전과, 조건이 빡센 버전 두개가 있다.단순하게 해당 구간을 빙빙 돌면서 그 안에 있는 a들의 수를 전부 카운팅한다.원래 2번째 케이스를 풀어보려고 준비한건데, 타임아웃이 나는건지 70%쯤에서 아예 풀

그리디 알고리즘의 대표주자문제이다.반례를 찾아보면 쉽게 안된다는걸 알 수 있다.이런 예제가 있다면 실제로 가능한 값은 (2, 3) (4, 5) 이겠지만, 우리가 받아볼 결과는 1, 10하나이다.따라서 이렇게는 안된다.이런 예제가 오더라도이렇게 정렬하면 문제를 풀 수 있

이 헤더에 스택이 존재한다. 이를 선언하려면 vector와 동일하게 으로 선언해주면 된다. 다른 언어에서의 스택이랑 크게 다를게 없다. 함수명도 똑같고.

교차되는 전기줄을 없애야한다.입력을 보면 순서가 정렬되어 나오지 않는다. 따라서 우선 왼쪽 전봇대를 1~n순서로 정렬을 해줘야한다. 연결할 수 있는 최대의 전기줄을 구하면, 반대로 연결 할 수 없는 전기줄 역시 구할 수 있다. 따라서 오른쪽 정렬안된 전봇대에서 가장 긴

말 그대로 정렬을 도와주는 함수이다. Sort를 사용하기 위해서는 을 사용해야 한다. 이렇게 3가지가 있다.1번의 경우 단순히 start 에서 end 범위 내의 값을 오름차순값으로 정리해주는 기능이다. 이런식으로 정렬해보면이렇게 정렬되는것을 볼 수 있다. 다만 신경쓸점

N까지의 자연수중에서 M개의 수를 중복없이 뽑는 문제이다.그다지 어렵지 않은 코드이다. 1부터 n까지 루프를 돌면서 특정 숫자가 방문하지 않은 숫자라면, visited를 1로 바꾸고 방문한걸로 처리한다. cnt(자리수)를 한자리 늘리고 다시 pick 함수를 불러서 다음

유명한데 풀라하면 잘 못푸는 그런문제가 아닐까싶다. N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.퀸은 가로, 세로, 대각선으로 이동하면서 공격할 수 있다. 이를 염두에두고 한번 풀어보자같은 행(row)에는 퀸을 놓