요즘 괜찮은 회사들은 많이들 알고리즘 테스트를 본다. 그럼 알고리즘 해결능력이 실무에 도움이 되는가에 대한 질문이 항상 꼬리를 물고 따라오는데 내 생각은
아티클이나 기술에 대한 이해 및 시각을 넓혀준다.
문제 해결 습관이 발전한다.
정도이다. 이는 물론 큰 도움이 되지만, 어플리케이션 개발에 알고리즘이 직접적으로 사용 되는 경우는 흔하진 않으리라 생각한다.
그러니 이 글의 목적은 다음과 같다.
1.
문제 해결 습관을 발전시킨다.
2.
프로그래밍에 대한 전반적인 시야를 넓힌다.
3.
스스로 알고리즘을 훈련하기에 충분한 학습 가이드를 제공한다.
언어 및 플랫폼 선택
1. 언어 선택
언어 선택에 대한 비교는 이미 좋은 글들이 많아 검색해보면 원하는 답을 얻으리라 생각한다. 의견을 덧붙이자면 언어가 장벽이 되는 순간은 구현 과 문자열 처리 에 해당되는 문제를 풀 때이다.
해시로 분류되어 있지만 프로그래머스의 베스트앨범 문제와 2021 카카오 블라인드 채용에서 신규 아이디 추천 문제를 참고해보면 좋을꺼 같다.
정답을 맞출 필요는 없고 선택한 언어로 자료를 가공을 하는데 많은 어려움을 겪는 다면 해당 언어는 피하는 것을 추천한다.
가끔 C++이 퍼포먼스를 위해 선택되는 경우가 있는 것 같은데, 여태까지는 알고리즘 테스트를 보면 모두 언어에 대한 퍼포먼스 보정 수치를 적용하고 있었다. 때문에 실제 시험에서 언어 선택에 대한 퍼포먼스 차별은 경험상 한 차례도 없었다.
그 외에 좋은 답안으로 책 또는 여러 블로그에 Python과 C++ 이 많이 시중에 공유되고 있어 이는 큰 도움이 될 수 있다.
2. 플랫폼 선택
불편하더라도 백준에 익숙해지는 것을 추천한다. 문제량도 많을 압도적으로 뿐더러 내 실력을 수치화하여 객관적으로 판단할 수 있는 플랫폼이다. 가령 A사의 시험을 친다고 할 시에 많은 리뷰에서 “실버5에서 골드3 사이에요.” 와 같은 것들을 쉽게 볼 수 있다.
문제들의 난이도는 solved.ac 에서 확인 가능하다.
확실한 목표는 동기를 일으키기 쉽고 동기야 말로 성장에 가장 중요한 동력이기 때문에 잠시만 UI의 불편함에 익숙해지면 얻어가는 것이 더욱 많으리라 확신한다.
다만 알고리즘 테스트가 잡혀 있다면 해당 회사에서 사용하는 플랫폼으로 꼭 연습하길 바란다. 그리고 학습 이후 알고리즘 문제에 익숙해지면 어떤 다른 플랫폼으로 이동하더라도 좋다.
자 이제 스스로 훈련하기 위해 어떻게 학습하면 좋을 지 한 사이클 돌려보자
공략 추천
튜토리얼 및 공략집이기 때문에, 최대한 틀에 맞춰 정리했다. 초기에 익혀야 할 알고리즘을 기준으로 중요도에 따라 과감히 버릴 부분은 버렸다. 중요하다고 여기는 부분은 볼드 처리하였고
그 외에 팁은 callout 으로 표현하였다.
공략 사이 사이마다 문제를 첨부했으니 문제를 익혀가며 정진하길 추천한다.
v1.0.0 - 22.05.31 초안 작성
개요
0. 문제 이해 및 해결 과정
1.
입출력
2.
반복문과 재귀가 없는 완전탐색
3.
정수론
4.
재귀가 있는 기본적인 완전탐색
5.
정렬된 자료구조
6.
이진 탐색
7.
자료 구조(스택, 큐, 트리)
8.
Graph 탐색
9.
DP(Dynamic Programming)
0. 문제 이해 및 해결 과정
알고리즘 문제를 해결하는 데 있어 가장 중요한 영역이다. 스스로 문제를 정확히 이해 했다고 생각했지만 문제 제출 후 “틀렸습니다.” 문구를 보고 나서야 잘못 이해 했거나 고려하지 않은 케이스를 발견하는 경우가 부지기수이다. 특히 입력 값과 출력 값만 보고 예측하는 경우가 가장 위험하다.
문제가 길어지고 난해하면 본능적으로 눈이 흐려진다.
특히 놓치는 것이 제한사항 인데 이는 알고리즘 해결을 위해 결정적인 힌트를 제공한다. 문제 설명과 제한사항 모두 반드시 100% 정확하게 이해해야 한다.
답을 아는 것보다 질문이 무엇인지 아는 것이 더 중요하다.
틀린 질문에서 옳은 답은 절대 나올 수 없다.
구종만님이 집필한 “알고리즘 문제풀이 해결 전략” 에서 문제를 접근하는 과정에 대해서 설명한다.
1. 문제를 읽고 이해한다.
2. 문제를 익숙한 용어로 재정의한다.
3. 어떻게 해결할 지 계획을 새운다.
4. 계획을 검증한다.
5. 프로그램으로 구현한다.
6. 회고한다.
C++
여기서 몇가지 포인트를 집고 넘어 가자면
2. 문제를 익숙한 용어로 재정의한다. 에서 내가 제대로 문제를 잘 이해 했는지 “나의 언어”로 재정의를 해야 한다고 말한다. 이러한 과정을 문제를 추상화 한다. 라고도 표현한다. 문제는 아주 길지만, 핵심적인 부분만 도려내는 것은 문제 풀이에 있어 굉장히 중요하다.
5. 프로그램으로 구현한다. 에서 처럼 코드 작성을 하는것은 충분히 문제를 해석하고, 가설을 세운 후 마지막에 작성하는 것이다. 알고리즘은 문제를 해결할 나의 가설을 세우는 일이다. 구현은 그 다음이다.
그 외에 제공된 테스트 케이스 외에 다른 엣지 케이스도 프로그램 작성 전에 검토하길 강력히 추천한다. 예시만 통과했다고 통과 된 것이 아니다. 놓친 케이스를 찾는 것 또한 알고리즘 문제 중 일부이다.
시간 분배
풀리지 않는 문제를 하루 종일 붙잡는 것도, 안 풀린다고 바로 답을 찾아 보는것도 좋지 않은 것에 다들 동의할 것이다.
결국 적절하게 대처해야 하는데 처음 알고리즘을 배우는 시점에서는 개인적으로 한 문제에 최대 2시간을 나눠 쓰는 것을 추천한다.
첫번째 30분은 위의 1~4번 까지 설계 및 계획을 세운다. 어떤 알고리즘을 세울 지 어떤 예외 케이스가 있을지 생각해보는 시간이다. 빨리 설계되었으면 다음 단계로 넘어가도 좋으나 충분히 이 시간에 활용하는 것을 추천한다. 반대로 30분 이상 걸리면 애초에 풀 수 없는 경우도 많아서 코드를 작성하면서 문제를 찾아가길 바란다.
두번째 30분은 5번 과 같이 프로그램을 작성하고, 디버깅하는 시간을 가진다.
세번째 30분은 추가로 두번째 30분에서 정답에 근접하거나 풀 수 있을 거 같을 경우에 추가적으로 구현하는 시간을 가진다. 만약 이 시간이 필요없다면 다음으로 넘어가도 좋다.
마지막 30분은 6 번 처럼 답을 찾아보고, 무엇이 잘못 됐는지 혹은 내가작성한 코드에 개선할 점은 무엇인지 회고한다. 그리고 다음에 같은 문제를 만났을 때, 어떻게 해결할 지 등을 고민하여 정리하는 것도 좋은 방법이다.
1. 입출력
백준을 포함한 일부 플랫폼은 입력과 출력을 직접 해야한다. 물론 특정 플랫폼이 아니더라도 디버깅을 하기 위해 원하는 자료를 출력하는 것은 일은 비일비재하다.
입출력이 어렵진 않지만 그렇다고 간과하고 넘어가선 절때 안된다. 특히 입력을 잘못 처리하면 정확한 알고리즘을 구사 하더라도 처음부터 틀린 상태로 시작하게 된다.
// 값의 구분자 없이 입력을 받는 경우
1. 0123456789
// 공백을 값의 구분자로 입력을 받는 경우
2. 0 1 2 3 4 5 6 7 8 9
// 줄바꿈으로 값의 구분자를 입력 받는 경우
3. 0
1
2
3
...
9
JavaScript
때문에 입력을 제대로 받도록 주의해야 하고 처음에는 예상한대로 입력 값이 들어왔는지 수시로 확인하는 편도 좋으리라 생각한다.
2. 반복문과 재귀가 없는 완전탐색
실무에서도 많이 쓰여 아주 익숙한 개념이기 때문에 연습해야하는 것이라는 가치를 못 느낄 수 있다. 하지만 실무에서의 반복문과 알고리즘의 반복문은 다르다. 이중 for문이 밥먹듯이 나오고, 그 이상의 for문도 나올 수 있다. 일반적인 어플리케이션 제작에서는 마주할 일이 적기 때문에 분명이 실수한다.
for문을 익히기 위해 가장 고전적인 연습은 별 그리기 문제이다.
위 문제에서 입출력과 반복문에 익숙해졌다면 정적인 for문 및 재귀가 없는 완전탐색 문제를 풀어보는 것을 권장한다.
그 외에 추가적으로 문제가 필요하다면
https://www.acmicpc.net/category/301
https://www.acmicpc.net/category/55
한국 올림피아드 지역 예선 및 본선 문제 중 초등부 문제 및 중등부의 첫번째 문제에서 비슷한 문제들을 찾아볼 수 있다.
알고리즘 분류를 클릭하면 “구현" 이라고 나와있는 문제들이 그러하다.
대체로 2차원 배열 혹은 그 이상을 만든후에 값을 모두 탐색하는 방향으로 진행된다.
가능한만큼 모두 반복하여 탐색하기 때문에 성능적으로 매우 떨어지나, 문제 해결을 위한 가장 기본 되는 방법이기 때문에 충분히 연습하는 것이 중요하다.
정적인 for문 혹은 재귀가 없는 완전탐색은 특별한 알고리즘 기법이 들어가지 않기 때문에, 기본적인 문제 해결능력이 있는지에 대한 질문들이 많다.
난이도는 일반적으로 브론즈2에서 실버 4까지의 난이도를 보인다.
3. 정수론
수학적인 요소가 포함된 문제이다.
두 가지 케이스로 갈리는 데 첫 번째는 단순히 수의 패턴을 발견해서 문제를 해결하는 방식이다. 두번째는 알려진 공식을 대입하는 문제인데 이 경우는 전형적인 알면 쉽게 맞추는데 모르면 문제가 어려워진다. 하지만 기업 테스트에서 잘 나오지도 않는 유형일 뿐더러, 그 공식이 많지도 않고 외울 필요없이 필요할 때 검색해서 개념 적용만 할 수 있게 알아두면 충분하리라 생각한다.
수의 패턴을 발견하는 문제는 다음과 같다.
문제를 풀어보면 알겠지만 아이디어를 찾아내는 것이 쉽지 않다. 학습보다는 훈련에 가까운 영역이기 때문에 많이 풀어보는 것 말고는 방법이 없다. 때문에 해당 글에서는 깊게 다루진 않을 예정이다. 다만 수의 패턴을 발견하는 문제는 특히 코드로 옮기기 전에 정확한 수의 패턴을 발견한 후에 코드를 작성하는 것을 권장한다.
그리고 대표적으로 알려진 정수론을 활용하는 대표적인 규칙을 소개한다.
⺵ 소수 판별하기
소수 판별은 가끔 다른 알고리즘과 함께 섞여 나오는 경우가 종종 있다. 최근 2022 카카오 블라인드 리쿠르트 에서도 소수를 찾는 법을 물어보았다.
소수의 정의는 다음과 같다.
자연수 중 1과 자기 자신만을 약수로 가지는 수다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다.
즉, 소수를 찾기 위해서는 2부터 시작해서 자신과 나누어 떨어지는 수가 단 하나도 없을 경우에 그 수를 소수라고 판단 할 수 있다.
// 코드로 작성하면 아래와 같다.
bool isPrime(int n)
{
int r = 2;
while (n > r) // 2부터 시작하여 자기 자신 바로 전까지
{
if (n % r == 0)
return false;
r++; // 하나씩 증가하며 나누어 떨어지는 수가 있는지 계속 확인한다.
}
return true; // 나누어 떨어지는 것이 하나도 없다면 이는 소수이다.
}
C++
하지만 소수 판별하기가 소수를 구별하는 코드를 구현하는가를 질문하는 경우는 잘 없다. 대신 연산량에 대한 기본적인 이해를 가지고 있는가? 연산과 메모리를 교환할 수 있는가? 그리고 자료형의 범위를 감지하는 능력을 가졌는가? 이러한 것들을 평가한다.
위의 코드에서 n이 10이라면 반복은 r이 2부터 9까지 7번 반복한다.
가령 제한사항에 n의 크기가 1 ≤ n ≤ 1억이라고 한다면 r은 2부터 99999999까지 반복한다. 이는 1억번 실행하는 것과 거희 같다고 봐도 무방하다.
그렇다고 할 시에 1억이 소수인지 아닌지 판단하는 요청을 10번 반복하면 10억번의 연산이 수행되어야 한다.
시간 복잡도
시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 알고리즘 문제 해결에 있어서는 반복문이 최대 몇 번 반복하는가에 대한 횟수를 세는 정도로 이해해도 좋다. log(n) 이니 amortized O(1) 같은 표현식도 흔히 쓰이지만 가장 기본은 반복 횟수 중 가장 큰 연산을 세는 것이다.
간단한 예를 확인하자.
for(int i=0; i<10만; i++) {
for(int j=0; j<10만; j++) {
}
}
C++
위의 코드는 i가 10만까지 반복하며 i 하나에 대하여 j가 10만개씩 반복한다.
즉 위의 연산 횟수는 10만 * 10만으로 총 10억번의 연산량을 가진다.
for(int i=0; i<10만; i++) {
}
for(int j=0; j<10만; j++) {
}
C++
이번에는 중첩된 for문이 아니라 각각의 for문을 사용하고 있다.
서로의 for 문이 연산량에 영향을 주지 않기 때문에 총 20만번 실행될 것이다. 하지만 반복 횟수 중 가장 큰 연산만 세면 되기 때문에 10만이라고 생각하면 된다.
허용되는 연산량에 대한 제한 사항은 보통 문제에 기술되어 있지만 기본적으로 10억번의 연산량을 가지면 대부분의 문제가 시간초과가 발생한다. 때문에 문제를 풀기 전에 반드시 입력 받을 인자의 크기를 통해 작성할 코드가 얼마만큼의 연산량을 가질 것인지 예측하는 것은 아주 중요하다.
참고로 정확하지는 않으나 보통 1억번의 연산을 1초에 처리한다고 기준을 잡고 문제를 푸는 경우가 더러 있다.
위 소수구하기의 범위를 살펴보면 다음과 같다.
1부터 1,000,000 사이의 모든 소수를 출력하는 경우가 발생할 수 있다는 것이다.
1,000,000이 소수인지 알기 위해서는 약 1,000,000번의 반복을 즉 n이 소수인지 알려면 n만큼 반복해야 한다고 가정하면 등차수열의 합을 통해 총 반복횟수를 확인 할 수 있다.
1,000,000 * (1,000,000 + 1) / 2 = 500,000,500,000
C++
최대 5천억번의 반복이 실행되어야 한다. 이는 시간 제한 2초와 너무 동떨어진 수이고 분명 성능을 개선할 여지가 필요하다.
⺵ 연산과 메모리의 교환 그리고 에라토스테네스 체
알고리즘 문제를 해결하는데 있어 퍼포먼스 개선을 위한 가장 기본적인 테크닉은 연산과 메모리의 교환에 대한 개념이다. 조금 더 구체적으로는 연산들을 줄이기 위해서는 배열 혹은 그 밖에 자료구조에 저장하는 것으로 문제를 해결할 수 있다.
이는 실무에서도 쉽게 접할 수 있는 테크닉이다. 데이터베이스 성능이 떨어지면 인덱싱 된 테이블을 만든다. 이는 정렬된 데이터를 담은 저장공간을 만들어서 연산량을 줄이는 경우이다. 인메모리 캐시 혹은 메모라이즈 기법은 이미 한번 계산 했던 값들은 인자를 키로 저장하여 다음에 똑같은 요청이 들어왔을 때 연산하는 대신 저장된 값을 가져오는 방식이다.
에라토스테네스 체의 첫번째 아이디어는 배수들을 모두 체크한 후에 체크되지 않은 수는 소수라고 판단하는 방식이다.
즉 저장공간을 활용하여 연산을 대체하는 아이디어를 채택한 것이다. 그리고 저장공간에 한번 저장하고 나면 다음부터는 연산 없이 필요한 값을 매번 가져오기만 하면 된다.
위의 문제에서는 1,000,000 까지 소수인지 아닌지 한번 저장해 놓으면 나면 다음부터는 배열에서 필요한 값을 가져오기만 하면 된다.
두 번째 아이디어는 수학적인 측면인데 n이 소수인지 알고 싶다면 만큼만 조사하면 된다는 아이디어이다. 마주보는 수는 중복된 약수를 가지기 때문에 조사할 필요가 없다는 이유이다.
예를 들어 20의 약수는 2x10 4x5와 5x4 10x2 가 있을 텐데 4x5 이후로는 순서가 다를 뿐이지 같은 수의 곱셈이기 때문에 마주보는 수 이후의 수는 확인 할 필요가 없다는 의미이다.
즉 에라토스테네스의 체를 활용하면 다음과 같은 코드 결과를 작성할 수 있다.
bool* checkPrime(int n) // n까지의 소수인지 아닌지를 판단하는 배열을 리턴한다.
{
bool* PrimeArray = new bool[n + 1]; // n 즉 1,000,000 까지 소수인지 아닌지를 담을 배열
for (int i = 2; i <= n; i++)
PrimeArray[i] = true; // 일단 모두 참으로 초기화 한다.
for (int i = 2; i * i <= n; i++) // 루트 n만큼 조사한다.
{
if (PrimeArray[i]) // 소수인 경우에는
for (int j = i * i; j <= n; j += i) { // 소수를 약수로 둔 수들을
PrimeArray[j] = false; // 약수를 두고 있으므로 거짓으로 변환한다.
}
}
return PrimeArray;
}
C++
순열과 조합
순열과 조합의 수를 구하는 문제는 정수론에 속한 문제이나, 순열 리스트 혹은 조합 리스트를 출력하는 경우는 재귀가 포함된 완전탐색문제로 자주 출제된다.
순열과 조합의 수를 활용하는 문제들은 출제되는 경우가 적으므로 이번 파트에서는 정의를 정리하는 정도로만 마무리해도 좋으리라 생각한다.
순열 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열
(permutation)이라고 한다.
예를 들어 A,B,C,D,E 와 같은 카드가 존재할 때, 3장을 뽑는다고 하자. 이 때 가능한 순열 리스트로는
A, B, C 와 C, D, E 처럼 요소가 다르거나
A, B, C 와 C, A ,B 처럼 요소는 같으나 순서가 다른 경우도 가능하다.
하지만 A, A, B 와 같이 중복된 요소를 선택하는 것은 불가능하다.
n개중 r개를 뽑을 때, 총 나올 수 있는 순열의 수는 다음 공식으로 구할 수 있다.
조합 조합이란 n 개의 원소를 갖는 집합에서 r 개의 원소를 선택하는 것 혹은 선택의 결과로 정의되며, 어떤 순서로 원소를 선택했는지는 중요하지 않다.
예를 들어 A,B,C,D,E 와 같은 카드가 존재할 때, 3장을 뽑는다고 하자. 이 때 가능한 조합 리스트로는
A, B, C 와 C, D, E 처럼 요소가 다를 때만 선택 가능하다.
수열 과는 다르게
A, B, C 와 B, C, A 는 순서에 상관이 없기 때문에 불가능하다.
n개중 r개를 뽑을 때, 총 나올 수 있는 조합의 수는 다음 공식으로 구할 수 있다.
공식은 절대적으로 외우지 않아도 무관하나, 개념에 대해 이해하고 공식을 코드로 작성할 수 있도록 익혀가면 좋다. 그리고 조합 구현 시에 특정 자료형에서 overflow가 나는 경우도 있으니 구현을 해보며 직접 직접 찾아보길 바란다.
참고 연습 문제
그 외
이외에도 최대공약수와 최대공배수를 구하기 위한 유클리드 호제법 이나 특수 수열 역평균 수열 등 특별한 공식이 미리 정해져있는 문제들이 있다. 하지만 빈도가 아주 낮을 뿐더러, 공식을 일일이 외우는 것은 의미가 없다. 수학의 영역이 큰 부분이기도 하기에 지금 당장 여기에 많은 시간을 투자하기 보다는 그때 그때 문제를 만나면 개념을 익히는 정도로만 알아두고 빨리 넘어가는 것을 추천한다.
4. 재귀가 있는 기본적인 완전탐색
완전 탐색중에 조합, 순열, 중복순열을 활용하여 해결하는 문제들이 있다. 이번 파트에서는 이를 중점적으로 살펴본다.
재귀 함수
재귀함수(再歸函數)는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다.
코드로 확인하자. 아래는 3층짜리 별 그리기 함수이다.
void Recursive(int n){
if(n == 4) return;
for(int i = 0; i < n; i++){ // 별 그리기
printf("*");
}
printf("\n");
Recursive(n + 1); // Recursive(재귀)
}
Recursive(1);
// 결과
// *
// **
// ***
C++
Recursive 는 한번 호출한 이래로 if(n == 4) 의 조건에 만족하기 전까지 계속해서 본인 스스로인 Recursive 를 다시 호출한다. 이와 같은 코드를 재귀적인 함수라고 부른다.
재귀 함수는 크게 세 부분으로 나뉜다. 이 때 세 부분으로 나뉠 뿐 순서는 정해져 있지 않다. 하지만 세 가지 요소가 반드시 포함되어야 한다.
1.
종료 조건 ( 재귀를 더 이상 하지 않을 조건 )
if(n == 4) return;
C++
2.
실행 로직
for(int i = 0; i < n; i++){ // 별 그리기
printf("*");
}
printf("\n");
C++
3.
재귀 호출
Recursive(n + 1); // Recursive(재귀)
C++
재귀 함수와 CallStack
우리가 함수를 만들고 실행하면 함수가 실행이 완료되기 전까지 호출 스택(CallStack) 이라는 곳에 담긴다.
const a = (v) => {
if(v > 10000000) return;
a(v + 1);
}
JavaScript
위와 같은 재귀를 만든 브라우저의 개발자 도구에 실행하면 다음 에러를 만나는데,
보시다시피 CallStack이 최대를 초과했다는 에러를 확인 할 수 있다. 이를 StackOverflow 라고도 부른다. 즉 함수 호출을 하면 CallStack 에 담긴다는 것을 실제로도 확인 할 수 있는데 이 때 stack 이라는 자료구조에 대해서 조금 더 살펴볼 필요가 있다.
Stack정의는 다음과 같다.
스택이란 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료 구조이다.
LIFO(Last In First Out), 즉 가장 마지막에 들어온 값이 가장 먼저 나온다는 매커니즘이다.
이러한 매커니즘 때문에 stack은 몇 가지 추가적인 경향성을 가진다.
1.
탐색과 처리 중 탐색을 만나면 우선적으로 탐색을 마치는 것을 우선시 한다. 이러한 성질 때문에 컨테이너에 자료들이 보관되는 양과 기간이 긴 편에 속한다.
2.
탐색이 필요한 계층 구조를 가지는 자료에 사용된다.
CallStack 같은 경우를 살펴보자. 내부에 존재하는 함수를 먼저 모두 탐색하는 방식으로 동작하고 그 동안의 상위 호출은 스택에 계속해서 저장된다.
void FunctionA() {}
void FunctionB() {}
void FunctionC() {
FunctionB(); // B가 실행되는 동안 C는 여전히 실행중이다.
// C함수 종료
}
void FunctionD() {
FunctionA(); // A가 실행되는 동안 D는 여전히 실행 중(스택에 담겨있는 중)이다.
FunctionC(); // C가 실행되는 동안 D는 여전히 실행 중이다.
// D함수 종료
}
C++
FunctionD 내부에서 FunctionA 가 실행되면 실행을 마치고 FunctionD 로 돌아가는 당연한 이야기다.
즉 정리하자면 자식의 탐색이 우선이고 부모의 상태는 매번 저장되었다가 자식의 실행이 마치는 대로 부모의 실행이 진행된다는 것이다.
이는 스택을 사용하는 Parser 등에도 마찬가지로 보이는 경향성이다.
한 번 곰곰히 생각해보길 바란다.
이러한 경향성을 이용하여 앞으로 배울 DFS(깊이 우선 탐색)등에도 마찬가지로 적용된다.
우리는 방금 별 그리기를 재귀로 풀었다.
void Recursive(int n){
if(n == 4) return;
for(int i = 0; i < n; i++){
printf("*");
}
printf("\n");
Recursive(n + 1);
}
Recursive(1);
// 결과
// *
// **
// ***
JavaScript
만약 별 찍기-3 와 같이 역으로 별을 그리려면 어떻게 하면 좋을까?
가장 마지막 함수가 3이기 때문에, 스택이 탐색을 우선시 한다는 것을 활용하여 탐색을 먼저 호출하여 가장 마지막 n인 3까지 모두 함수 호출을 한 후에 CallStack 에 담긴 부모 함수들을 하나씩 빼나가며 별을 그린다.
void Recursive(int n){
if(n == 4) return;
Recursive(n + 1);
for(int i = 0; i < n; i++){
printf("*");
}
printf("\n");
}
Recursive(1);
// Recursive(1) 실행 stack []
// Recursive(2) 실행 stack [Recursive(1)]
// Recursive(3) 실행 stack [Recursive(1), Recursive(2)]
// *** for문으로 별 그리기 stack [Recursive(1), Recursive(2)]
// ** stack [Recursive(1)]
// * stack []
JavaScript
처음부터 재귀함수를 이해하는 것은 쉽지 않을 수 있다. 하지만 앞으로 나올 알고리즘들의 가장 기초가 되는 아이디어 이기 때문에 위의 코드와 앞으로 나올 문제들은 반드시 이해하고 넘어가야 한다.
머리로만 이해하려 하지 말고 반복하고 익히길 바란다.
자 이제 재귀를 활용한 문제들을 풀어보자.
백트래킹과 중복 순열, 순열 및 조합 재귀
중복 순열
중복 순열은 문제와 같이 순열의 특징을 가지면서 동시에 순열 내에 중복을 허락한다.
위의 예시는 1부터 4까지의 수 중에 2가지를 골라서 선택할 수 있는 수의 열거들을 출력한다.
문제를 조금 더 깊이 보자.
1부터 4까지의 2가지를 고르는 수의 리스트는 2중 for문으로 출력 가능하다.
for(int i=1; i<=4; i++) {
for(int j=1; j<=4; j++) {
printf("%d %d", i, j);
}
}
C++
즉 N가지를 고르는 수의 리스트는 N중 for문으로 가능하다.
입력의 제한된 수는 (1 ≤ M ≤ N ≤ 7) 이기 때문에 7중 for문으로 구할 수 있으나 N의 수가 많아질 수록 사실상 작성 불가능할 것이다.
이를 재귀로 표현하면 N번의 for문을 반복하는 것도 가능하다.
재귀를 작성할 때, 함수의 정의 및 인자가 어떤 역할을 하는지 정하는 것은 매우 중요하다.
재귀를 작성하는게 익숙하지 않다면, 함수와 증가하는 인자들이 어떤 역할을 하는지 주석등을 통해 먼저 정리를 한 후에 진행하는 것을 추천한다.
int n, m;
int arr[8]; // 뽑은 카드를 임시로 보관하는 배열
// repeatPermutation는 1부터 n까지의 카드를 뽑는 함수이다.
// 카드를 모두 뽑으면 뽑은 카드들을 출력한다.
// x는 뽑은 카드의 수 즉, arr에 저장할 인덱스의 위치이다.
// 예를 들어 arr[0] = 1 이라면 첫번째 뽑은 카드는 1이다. 총 m장 뽑으면 종료한다.
void repeatPermutation(int x) {
// 카드를 모두 뽑으면 종료한다.
if(x == m) {
for(int i=0; i<m; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return;
}
// 1부터 n사이의 카드를 뽑고, 다음 장을 뽑을 함수를 실행한다.
for(int i=1; i<=n; i++) {
arr[x] = i;
repeatPermutation(x + 1);
}
}
repeatPermutation(0);
// n = 3, m = 2 일때,
// 1 1
// 1 2
// 1 3
// 2 1
// 2 2
// 2 3
// 3 1
// 3 2
// 3 3
C++
다시금 말하지만 재귀의 기본은 스택이다.
첫번 째 1을 뽑고 두번 째 1을 뽑은 후 두번 째 카드를 뽑는 것이 종료되더라도 여전히 첫번 째 1을 뽑은 것은 유효하다.
순열
중복을 허용하지 않고 순서와 상관 있는 수열의 집합의 출력이다.
위의 중복 순열과 달리 M번째 카드를 뽑았다면 M이후 카드는 뽑을 수 없다.
알고리즘에서는 방문한 인덱스를 체크하기 위해 방문을 위한 배열을 별도로 선언하는 경우가 일반적이다.
int n, m;
int arr[8];
bool visited[8]; // 방문한 인덱스를 체크하기 위한 배열
// x는 현재 방문할 인덱스 (뽑아야 할 카드 번 째)
void Permutation(int x) {
if(x == m) {
for(int i=0; i<m; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return;
}
for(int i=1; i<=n; i++) {
if(visited[i]) continue; // 방문한 인덱스에 대해선 재방문 하지 않는다.
visited[i] = true;
arr[x] = i;
Permutation(x + 1); // 다음 카드를 뽑는다.
visited[i] = false; // 스택을 정리하는 과정에서 방문 여부를 초기화 한다.
}
}
Permutation(0);
C++
세 개의 카드를 뽑는다고 가정하자.
1.
1번 카드에서 1을 뽑는다.
2.
2번 카드에서는 이미 1을 뽑았기 때문에 2를 뽑는다.
3.
3번 카드에서는 이미 1과 2를 뽑았기 때문에 3을 뽑는다.
4.
뽑은 세 개의 카드를 출력한다.
5.
3번 카드의 3을 뽑은 스택을 정리한다.
6.
“3번을 반복한다.” 3번 카드에서 이미 1과 2를 뽑았고 3은 지나갔기 때문에 4를 뽑는다.
7.
계속 반복한다.
조합
중복을 허용하지 않고 순서가 상관없는 수열의 집합의 출력이다.
예제 출력을 보면 1 2는 존재하지만 2 1 은 존재하지 않는다. 두 수의 차이는 앞의 수가 더 작다. 예제 출력의 다른 수도 동일하다. 즉 수열들 중 오름차순인 수만 출력하면 이는 즉 조합이다.
int n, m;
int arr[8];
bool visited[8];
// x는 현재 방문할 "인덱스", start는 오름차순으로 출력하기 위한 "이전 값보다 큰 값"
void Combination(int x, int start) {
if(x == m) {
for(int i=0; i<m; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return;
}
for(int i=start; i<=n; i++) { // 다음에 뽑을 카드들은 start부터 n까지의 수를 뽑는다.
if(visited[i]) continue;
visited[i] = true;
arr[x] = i;
Combination(x + 1, i + 1); // 다음에 뽑을 수를 호출한다.
// 이 때, 내가 뽑은 수보다 큰 수부터 뽑게 start를 지정.
visited[i] = false;
}
}
Combination(0, 1);
C++
이러한 문제 해결방식 처럼 하나 씩 되돌아가면서 문제를 해결하는 방식을 백트래킹 이라고도 부른다.
아래는 연습용 백트래킹 문제이다. 몇 문제만 같이 풀어보도록 하자.
먼저 중복순열, 순열, 조합 중 어느 영역인지 분류하자.
위에서 보듯 중복순열 코드는 다음과 같다.
void repeatPermutation(int x) {
if(x == m) {
for(int i=0; i<m; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return;
}
for(int i=1; i<=n; i++) {
arr[x] = i;
repeatPermutation(x + 1);
}
}
repeatPermutation(0);
C++
정답을 위해서 조금만 수정하자. 첫번 째로 종료 시점은 수열의 수가 아닌 수열의 합이다.
수열의 합 역시 동적이므로 수열의 합을 나타내기 위한 인자가 필요할 것으로 보인다.
int m;
int cnt = 0;
void repeatPermutation(int sum) {
if(sum == m) { // 수열의 합을 통해 m을 만들었으면 cnt를 증가시킨다.
cnt++;
return;
}
for(int i=1; i<=3; i++) { // 1부터 3까지의 수를 사용한다.
if(sum + i > m) continue; // 만약 m이상이면 수열을 더 이상 진행하지 않는다.
repeatPermutation(sum + i); // 현재 수열에 i를 더한다.
}
}
repeatPermutation(0, 0);
C++
다음은 삼성 코딩테스트 기출문제인 연산자 끼워넣기 문제이다.
덧셈, 뺄셈, 곱셈, 나눗셈의 수가 정해져 있고 한번 사용한 연산자는 사용할 수 없다.
1 + 2 X 3 와 1 X 2 + 3 은 다른 결과를 가지므로 즉 “순열” 문제임을 확인 할 수 있다.
다만 이전까지와는 다르게 수가 수열을 이루는 것이 아니라 연산자가 수열을 이루는 것이 다르다.
이처럼 수가 아닌 경우에도 순열 혹은 조합을 이루는 경우가 많기 때문에 이런 케이스를 알고 있길 바란다.
순열 코드는 다음과 같이 방문한 값을 체크하여 중복을 방지한다.
int n, m;
int arr[8];
bool visited[8];
void Permutation(int x) {
if(x == m) {
for(int i=0; i<m; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return;
}
for(int i=1; i<=n; i++) {
if(visited[i]) continue;
visited[i] = true;
arr[x] = i;
Permutation(x + 1);
visited[i] = false;
}
}
Permutation(0);
C++
종료 조건은 연산자의 수만큼일 것이고, 인덱스도 연산자를 재귀하며 진행할 것이다.
그리고 동적으로 sum의 결과가 연산자에 따라서 변해야 하기 때문에 그 점 고려하면 다음과 같은 방식의 코드가 작성된다.
const int PLUS = 0, MINUS = 1, MULTI = 2, DIVIDE = 3;
int n, arr[15], operatorArr[15];
bool visited[15];
int max = -1000000000, min = 1000000000;
// x는 연산자의 인덱스, sum은 결과
void Permutation(int x, int sum) {
if(x == n - 1) {
int result = sum;
if(max < result) max = result;
if(result < min) min = result;
return;
}
for(int i=0; i<n-1; i++) { // 연산자의 총 개수는 수에 하나 모자란 값.
if(visited[i]) continue;
visited[i] = true;
switch(operatorArr[i]) {
case PLUS: {
// "수 연산자 수" 형식이기 때문에 연산을 할 수의 인덱스는 x+1
Permutation(x + 1, sum + arr[x+1]);
break;
}
case MINUS: {
Permutation(x + 1, sum - arr[x+1]);
break;
}
case MULTI: {
Permutation(x + 1, sum * arr[x+1]);
break;
}
case DIVIDE: {
Permutation(x + 1, sum / arr[x+1]);
break;
}
}
visited[i] = false;
}
}
Permutation(0, arr[0]); // 첫번째 sum은 연산 값의 맨 앞 숫자이다.
C++
그 외 문제 리스트들이다.
하지만 이러한 완전탐색은 큰 문제점이 있는데, stack을 사용하기 때문에 오랫동안 이전 값들이 저장된 채라는 점이다. 이는 즉 “메모리 초과 혹은 stackoverflow” 등이 발생하는 원인이 된다. 그 때문에 위의 문제들에서도 다시 한 번 살펴보면 N의 범위가 크지 않는 것을 확인 할 수 있다.
때문에 이와 같은 문제 풀이를 적용하기 전에 반드시 N의 크기가 크지 않은지 확인해야 한다. ( 아무리 커도 100 이하 정도 )
5. 정렬된 자료구조
알고리즘은 대게 탐색이다. 그리고 탐색에서 가장 중요한 것은 위치를 얼마나 구체적으로 아는 것이다.
그리고 저장된 공간이 정렬 되어 있다면 더 빠르게 찾을 수 있는 값들이 존재한다.
프로그래머스의 정렬 태그의 문제들인데 모두 어렵지 않으니 정렬의 파괴력을 체험해보고 오길 바란다.
분할 정복을 통한 병합 정렬(Merge Sort)
사실 버블 정렬, 삽입 정렬 등 여러가지 정렬 방법이 존재하고, 이러한 정렬 들을 구현하는 문제를 직접적으로 만나지 않는다. 정렬을 하려면 각 언어가 제공하는 sort 메서드를 쓰면 가장 빠르게 정렬해준다.
그럼에도 불구하고 병합 정렬과 퀵 정렬 을 구현하는 연습을 해보는 것을 추천 한다. 병합 정렬과 퀵 정렬에 기본적인 아이디어는 분할 정복(Divide and Conquer)인데 이를 연습하기 위해 병합 정렬과 퀵 정렬은 대표적으로 좋은 예시기 때문이다.
아래 병합 정렬에 대해서만 간단히 설명한다. 하지만 이미 좋은 글들이 많기 때문에 중복되는 내용이나 쉬운 내용들은 제거했다. 그렇기 때문에 이해가 더욱 필요한 부분이 있다면 직접 찾아보는 것을 부탁 드린다.
병합 정렬
구현에 앞서 O(nlog n) 라는 키워드에 주목하자.
시간 복잡도라는 표현인데 이는 간단히 가장 큰 연산량이 얼마인지 수식화 한 것이다. 더 자세한 내용은 좋은 글이 많으니 검색 하시길 바란다.
즉 병합 정렬을 하기 위해서는 n * 만큼의 시간이 걸린다고 한다. 은 2를 몇 번 제곱해야 그 수가 나오는지에 대한 값이다.
예를 들어 는 2의 10제곱이 1024 이므로 즉 10이다. 이는 1024라는 연산량이 10회만으로 해결될 수 있음을 의미하고, 알고리즘 실무등 컴퓨터 프로그래밍에 있어 퍼포먼스 향상에 있어 가장 상징적인 수식 중 하나이다.
분할 정복
분할 정복은 말 그대로 문제를 나누어 정복한다는 아이디어이다. 혹은 크고 어려운 문제를 작고 간단한 문제로 만들어 푼 후 다시 합쳐 문제를 해결한다는 의미로도 사용된다.
그리고 분할 정복 중 절반 씩 계속 줄여나가는 경우에 의 연산량을 만드는 알고리즘인 경우가 더러 있다.
병합 정렬의 기본은 더 이상 나눌 수 없을 때까지 정렬할 수를 절반 씩 계속 나눈다. 그리고 정렬된 작은 배열들의 요소중 작은 값을 순서로 정렬한다. 그리고 정렬된 배열들은 더 큰 배열로 합친다. 모두 합쳐 졌을 때 완전히 정렬된 원래 배열을 얻는다. ( 위의 gif 이미지 참고 )
그렇다면 이 아이디어가 어떻게 만에 해결 될까?
분할 정복을 활용한 병합 정렬의 시간 복잡도
을 하기 위해서는 왼쪽 절반의 정렬된 배열과 오른쪽 절반의 정렬된 배열을 합한 값과 같다.
왼쪽 절반 혹은 오른쪽 절반 정렬하려면 만큼의 연산량이 필요하다.
그리고 두 배열을 합하는 과정은 두 배열의 값을 하나씩 탐색하는 과정이기 때문에 만큼 소요된다.
즉, 이다.
위 식에 대신 를 넣으면 다음과 같아진다.
이를 다시 식에 대입하면
으로 볼 수 있다.
이 중 상수의 곱을 다시 풀면
이 된다.
이를 즉 더 이상 나눌 수 없는 1까지 반복하면 다음과 같아 진다.
- 2번 대입
- 3번 대입
- k번 대입
이 때 이 되어야 하므로 이는 즉, 와 같아 진다.
이를 원래식에 대입하면
이고
이기 때문에
이 된다.
알고리즘 문제 푸는데 도움이 되진 않는다. 이해 해보거나 혹은 수식으로 확인 가능하다 정도로만 그만둬도 좋다.
중요한 것은 절반 씩 쪼개는 아이디어는 만큼 연산량이 줄어들고 이는 만큼 연산할 수 있는 가능성이 생긴다는 의미를 가진다.
구현
몇가지 포인트만 집고 넘어가고자 한다.
먼저 mergeSort 을 통해서 나눌 수 있을 때 까지 배열을 쪼갠다. 이 때, 직접 배열을 수정하는 것은 아니고 배열의 인덱스 범위를 줄이는 방식으로 그런 효과를 만들어 낸다. 그리고 탐색이 우선인 특징을 이용하여 종료 시점 전까지 반복한다.
더이상 나눌 수 없으면 병합을 merge함수를 통해 진행한다. 시작 값과 중간 값이 왼쪽, 중간 값의 다음 값부터 마지막 값 까지가 오른쪽이다.
왼쪽 값과 오른 쪽 값의 인덱스에 해당하는 값들을 임시 배열을 만들어 정렬하고 원래 배열에 추가한다.
void merge(int s1, int e1, int s2, int e2) {
int temp[100005];
int cursor= 0;
int start = s1, end = e2;
while(s1 <= e1 && s2 <= e2) { // 왼쪽 인덱스 혹은 오른쪽 인덱스가 남을 때까지
if(arr[s1] < arr[s2]) { // 더 작은 값을 임시 배열에 담는다.
temp[cursor++] = arr[s1++];
} else {
temp[cursor++] = arr[s2++];;
}
}
// 담기지 않은 남은 배열 처리
while(s1 <= e1) {
temp[cursor++] = arr[s1++];
}
while(s2 <= e2) {
temp[cursor++] = arr[s2++];
}
// 기존 배열에 병합
for(int i=start; i<=end; i++) {
arr[i] = temp[i-start];
}
}
void mergeSort(int start, int end) {
if(start == end) return; // 종료 조건
int middle = (start + end) / 2; // 절반씩 나눈다.
mergeSort(start, middle);
mergeSort(middle + 1, end);
merge(start, middle, middle+1, end); // mergeSort가 종료 되었을 때 자식 호출부터 처리한다.
}
C++
읽어만 보면 쉬워 보이지만 막상 안보고 작성하면 start와 end의 역할 temp 배열의 인덱스 컨트롤등 디테일들에서 어려운 부분이 많다.
꼭 참고 코드를 보지 않고 작성할 수 있을 정도로 연습하길 추천한다.
알고리즘을 디테일하게 작성하는데 있어 성장에 도움이 될 것이라 확신한다.
6. 이진 탐색
이진 검색 알고리즘은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.
병합 정렬과 같이 씩 줄어들며 결국 만큼의 연산량을 보이는 알고리즘이다.
지금 까지 잘 따라오셨다면 구현 방식은 까다롭게 느껴지지 않을 것이다.
다만 주의할 점은 while 내의 종료 포인트와 s, e, mid의 역할을 잘 설정해야 한다는 것이다.
가령 아래 코드는 마지막 검색에서 값을 찾을 경우 그 값은 s 가 가지도록 역할을 부여 했다.
그 때문에 e의 시작이 N + 1 로 시작해야 하는데 마지막 검색이 마지막 인덱스라면 s가 N 이 될 수 있어야 하기 때문이다.
int N, Q;
int int arr[MAX] = {3,7,9,13,16,19,23,44,45};
bool binarySearch(int x) {
int s=0, e = N + 1;
while(s + 1 < e) {
int mid = (s + e) / 2;
if(arr[mid] == x) return true;
else if(arr[mid] < x) s = mid;
else e = mid;
}
if(arr[s] == x) return true;
return false;
}
binarySearch(9)
C++
탐색할 기준을 선택하는 것이 이진 탐색의 핵심
이진 탐색은 어떤 값을 찾을 것인가에 대한 기준을 정하는 것이 핵심이다. 그리고 이런 특징이 이진 탐색 문제들이 어려운 편에 속하는 이유이다.
두 용액 문제는 리스트 중 두개의 용액을 선택하여 두 값을 합쳤을 때 0에 가장 가까운 조합을 찾는 문제이다.
이전 단계에 있었던 조합 기술로도 문제는 해결할 수 있다. 순서에 상관 없는 두 개의 용액을 선택하여 더하는 문제이기 때문이다. 하지만 조합 은 CallStack 을 활용하는 기법이고 100,000 이하의 N을 처리할 연산량을 감당하기 어렵다.
이를 어떻게 이진 탐색으로 풀면 좋을까? 그리고 어떻게 이진 탐색 문제임을 알 수 있을까? 결국 이러한 아이디어를 떠올려야 하는 점이 이진 탐색을 어렵게 만든다. 이는 많은 문제를 접해보는 수 밖에 없다.
두 용액 문제에서 두 수의 합이0에 가장 가까운 수는 “수 하나를 고른 후, 그 값과 부호가 다른 가장 가까운 값” 을 찾는 문제이다. 일반적인 이진 탐색과는 달리 “정확한 값” 을 찾는게 아니고 가장 “근처의 값” 을 찾는 용도로도 이진 탐색을 활용할 수 있다는 것이다.
매개 변수 탐색 ( parametric search )
이와 같이 특정 값 대신 범위 내의 가장 가까운 값을 찾는 기법을 매개 변수 탐색 ( parametric search )
라고 부른다. 매개 변수 탐색은 이진탐색과 다르게 주어진 일련의 값들이 아니라 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘이다. 때문에 N이상의 값 혹은 N이하의 값 등 특정 값을 탐색하는 데 있어 최적화에 큰 도움을 준다.
나무 자르기 문제가 이분 탐색을 적용할 수 있는 대표적인 문제 중 하나이다. 절단기를 통해 가져갈 수 있는 높이의 최대값을 찾는 문제이다.
이는 절단기에 높이가 얼마 이상이어야 하는지 범위를 이분하며 찾는 문제이다.
예를 들어 위의 예시에서 절단기에 높이가 14이라면 [6, 1, 0, 3] 만큼 나무를 얻을 수 있고 이 요소의 합은 7보다 크므로 원하는 량의 나무를 얻을 수는 있다.
하지만 더 낮은 절단기로 얻을 수 있는 경우를 확인해야 하므로 절단기의 높이를 이보다 높여 탐색한다.
절단기에 높이가 16이라면 [4, 0, 0, 1] 으로 이 요소의 합은 7보다 작기 때문에 절단기의 높이는 이보다 작아야 한다.
공유기 설치 문제이다. 마찬 가지로 “가장 인접한 두 공유기 사이의 최대 거리” 를 구하는 범위를 탐색하는 문제이다.
인접한 공유기 사이의 거리가 1이라면 1 2 4 8 9 지역에 모두 공유기가 설치 가능하므로 총 5개의 공유기가 설치 된다.
인접한 공유기 사이의 거리가 4라면 1지역에 설치 이후 5이상의 집을 찾아야 하므로 8에 설치할수 있게 된다. 즉 총 2개의 공유기가 설치 된다.
이렇게 인접한 공유기의 최대 거리를 계속해서 이분 탐색 하여 결과를 얻을 수 있다.
항상 그렇지 않지만 “출력 결과”가 이분 탐색에 기준이 되는 경우가 많다!
7. 자료 구조(스택, 큐, 트리)
자료 구조의 특별한 성질과 경향성은 성능 향상에 도움을 준다. 앞으로 배울 그래프 탐색, DFS, BFS등은 스택과 큐를 활용하는 알고리즘 기법이고 trie와 같은 자료구조의 특징을 활용한 여러 특별한 알고리즘이 존재한다.
그리고 스택과 큐는 그 자체로도 문제 해결에 많이 쓰인다. 실무를 먼저 접하신 분들이라면 딴건 몰라도 스택과 큐는 한 번씩은 들어 봤을 것이다. 과연 어떤 특징을 가지고 있기에 다양한 용도로 활용 되는지 탐구해보자.
스택
이전 챕터에서 CallStack 을 통해 스택을 이미 활용 해보았다. 스택은 탐색을 최우선으로 진행하며, 새로운 탐색이 시작되면 이전 탐색에 상태는 모두 저장되었다. 이 때문에 탐색을 모두 끝내야 처리 가능한 일부 알고리즘에 도움이 된다. 하지만 때문에 내부 상태들의 생애주기가 긴 편이며 이 때문에 메모리의 초과나 stackoverflow 등 다른 자료 구조에 비해 큰 수를 처리하기에는 힘든 경향이 있다.
다만, 이전과는 다르게 직접 stack 자료 구조를 활용할 것이다. 특정 언어에서는 stack 자료구조가 존재하지만 아닌 경우도 많은데 stack 은 논리적인 개념이다. 가장 먼저 들어온 값이 가장 마지막에 나온다( LIFO ) 를 지키기만 한다면 무엇이든 이를 stack 이라 부를 수 있다.
// C++
#include <stack>;
stack<char> s;
s.push(1);
s.top(); // 1
s.pop();
s.top(); // empty;
C++
// javascript
const s = []
s.push(1);
s[s.length-1]; // 1
s.pop(); // 1
s[s.length-1]; // undefined
JavaScript
모두 stack 에 부합한다.
스택에 가장 기본적인 문제는 VPS(올바른 괄호 문자열) 문제이다.
실제로 파서등을 구현할 때 기본이 되는 알고리즘과 유사하다. 괄호는 열리면 닫히는 괄호가 있어야 하고 괄호 안에는 또다른 괄호가 있을 수 있다. ( 올바르지 않은 괄호가 무엇인지는 아시리라 생각한다. )
이렇듯 닫히는 괄호를 만나기 전까지는 계속 다음 내부 괄호를 탐색해야 하는 특징 때문에 Stack 이 사용된다.
( 를 만나면 현재 상태인 ( 을 스택에 Push 한다.
) 를 만났을 때 현재 열려있는 괄호를 종료 즉 Pop 한다. 종료할 괄호가 없다면 잘못된 괄호이다.
괄호의 값 역시 유사한 문제이니 풀어보는 것을 추천한다.
모노톤 스택
스택의 특징을 활용한 알고리즘 하나를 소개 하려고 한다. 스택의 원소들을 O(n)의 시간복잡도로 (중복을 허용하지 않고) 오름차순 혹은 내림차순 상태로 유지하는 방법을 모노톤 스택이라고 한다.
일부 문제에서는 동적으로 N의 위치에 있을 때의 가장 큰 값을 요구하는 문제들이 있다.
현재 탑은 이전의 탑들 중 가장 가까운 나보다 큰 높이의 탑에 신호를 보낸다.
이전 스택에 나보다 큰 수가 있는지 계속 확인하고 없다면 0을 출력한다.
그 이후에 본인을 이전 스택에 추가한다.
6은 이전 스택이 없으므로 0이다. 그 이후에 6을 이전 스택에 추가한다. stack = [6]
9의 이전스택을 top, pop하며 나보다 큰 수를 찾는다. 하지만 그 값이 없기 때문에 0이다. 그 이후에 6을 이전 스택에 추가한다. stack = [9]
5의 이전스택을 top, pop하면서 나보다 큰 수를 찾는다. 9를 발견했고 9의 인덱스를 출력한다. 그 이후에 5를 스택에 추가한다. stack = [9, 5]
7의 이전스택을 top, pop하면서 나보다 큰 수를 찾는다. 5를 발견했으나 7보다 작으므로 pop한다. 9를 발견하고 9의 인덱스를 출력한다. 그 이후에 5를 스택에 추가한다. stack = [9, 7]
4의 이전 스택을 top, pop하면서 나보다 큰수를 찾는다. 7을 발견하고 7의 인덱스를 출력한다. 그 이후에 4를 스택에 추가한다. stack = [9,7,4]
이 처럼 내림차순으로 높은 값들을 정렬하게 되면 현재 참고할 수 있는 스택에서 가장 높은 값 == 가장 멀리 있는 값, 스택에서 가장 낮은 값 == 가장 가까이 있는 값이 성립되고 이를 통해 문제를 해결할 수 있다.
모노톤 스택의 활용을 이용한 문제들이다.
문제를 읽어보면 유형의 패턴을 알 수 있으리라 생각한다.
즉, 내 위치에서 이전까지의 가장 큰 값 혹은 가장 작은 값을 찾는 문제에 적용할 수 있다.
큐
큐는 컴퓨터 과학 분야에서 쓰이는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO구조로 저장하는 형식을 말한다.
스택과 반대로 넣는 족족 다음 상태에서 바로 처리한다. 때문에 처리 시기가 빨라 스택 보다 많은 정보를 가지고 있진 않지만 훨씬 효율적으로 메모리를 활용하며 탐색할 수 있다. 때문에 탐색을 하는데 탐색해야 할 N이 100,000 정도의 큰 값이라면 큐를 사용하는게 도움이 될 수 있다.
사실 큐는 문제에서 노골적으로 요구하는 경우가 많다. 가령 “들어온 순서대로 처리되어야 한다” 와 같은 텍스트들이 그렇다.
아래 문제가 어렵진 않으니, 큐에 익숙해 질 겸 풀어보는 것을 추천드린다.
8. Graph 탐색
알고리즘 문제 중 DP, 분할 정복과 함께 가장 빈번하게 나온는 유형 중 하나이다. 이전 파트에서 활용한 stack과 queue를 활용하여 주어진 연결된 요소를 돌아보며 최적 해를 찾는 문제이다.
트리
트리 구조란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 트리에서 최상위 노를드 루트(뿌리) 노드, 마지막 노드를 리프(나뭇잎) 노드라고 한다. 그리고 노드들을 잇는 선을 간선(edge)라고 부른다.
이러한 트리를 잘 관찰하면 재귀적인 성질을 가지고 있음을 알 수 있는데 아래 그림을 보자.
위 트리는 ABCDE로 이루어진 트리로 볼 수 있지만 BDE 혹은 C로 이루어진 또 하나의 트리라고 생각 할 수 있다. 이러한 트리를 서브 트리라고 부르는데, 이렇게 트리 안에 트리가 있는 재귀적인 성질을 이용하여 모든 노드를 탐색 할 수 있다.
이진 트리
이진 트리는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조이다.
그렇기 때문에 트리를 그리기 위해서는 노드를 표현 하기 위해서는 두 개의 자식 노드만 표현하면 된다. 이를 left-node 와 right-node 라고도 부른다.
표현 할 수 있는 방법이 몇 가지 있는데 아래와 같이 객체(구조체)를 활용하는 방법과 배열을 이용하는 방식이 있다.
// 객체(구조체)를 활용하는 방법
Node tree[10];
struct Node {
char name;
char leftNode;
char rightNode;
}
Node.name = 'A';
Node.leftNode = 'B';
Node.rightNode = 'C';
tree[0] = Node;
// 배열을 이용하는 방법
char tree[10][2]
tree['A'-'A'][0] = 'B' // 0번 인덱스는 leftNode
tree['A'-'A'][1] = 'C' // 1번 인덱스는 rightNode
C++
주의 할 점은 이러한 방식은 이진 트리에서만 가능하다는 점이다. N개 이상의 자식을 가지는 트리 등은 인접 행렬 혹은 인접 리스트 두 자료구조를 활용해서 그린다.
이진 트리 순회
이렇게 만든 트리는 총 3가지 방법으로 모든 노드를 방문 할 수 있다.
•
전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
•
중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
•
후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
세 트리는 어떤 노드부터 방문하는가를 기준으로 전위, 중위, 후위로 나뉜다. 이 때, 서브 트리 개념을 다시 상기하는것이 이해를 도울 수 있다.
중위 순회 를 예로 들면 왼쪽 자식을 먼저 탐색하기 때문에 B 를 탐색한다. 하지만 B 를 루트로 하는 서브트리에서 왼쪽 자식은 D 이므로 결국 DBA 순으로 탐색한다.
이를 코드로 나타내면 다음과 같다.
const int NO_EDGE = -1;
void preorder(int x) {
printf("%d ", x); // 만나는 족족 (루트 노드) 처리
for(int i=0; i<2; i++) {
if(Tree[x][i] != NO_EDGE) preorder(Tree[x][i]);
}
}
void inorder(int x) {
if(Tree[x][0] != NO_EDGE) inorder(Tree[x][0]);
printf("%d ", x); // 왼쪽 노드부터 처리
if(Tree[x][1] != NO_EDGE) inorder(Tree[x][1]);
}
void postorder(int x) {
for(int i=0; i<2; i++) {
if(Tree[x][i] != NO_EDGE) postorder(Tree[x][i]);
}
printf("%d ", x); // 마지막 까지 스택에 담은 후(오른쪽 노드에 다다를때 까지) 처리
}
C++
LCA(Lowest common ancestor)
두 노드간에 가장 가까운 공통 조상 노드를 구하는 문제이다. 각 노드의 부모 노드를 저장해 두고 나서, 두 노드를 순회하면 가장 가까운 공통 조상을 찾을 수 있을 것이다. 어려운 문제는 아니니 풀어보시길 바란다.
int Parent[100010];
int idx_x = 0;
x = 타겟
while(x != root){
Parent[idx_x++] = x;
x = tree[x];
}
// 이와 같은 느낌으로 저장 가능하다.
C++
이 때, x와 y의 공통 조상을 구하려면 x의 Parent 노드와 y의 Parent 를 모두 반복해야 하기 때문에 2중 for문( )이 필요한 것처럼 보인다.
이 때, 정방향으로 찾는 것이 아니라 역방향으로 찾으면 “가장 처음으로 부모가 다른 인덱스" 의 다음 인덱스가 공통 부모임을 만에 알 수 있다.
int i = Parent_X.length - 1;
int j = Parent_Y.length - 1;
while(i >= 0 && j >= 0 && Parent_X[i] == Parent_Y[j]){
i--;
j--;
}
// Parent_X[i + 1] 와 Parent_Y[j + 1] 이 두 트리의 LCA
C++
또 하나 LCA의 특징 중에 두 노드의 LCA간의 거리의 합은 두 노드의 최단 거리와 동일하다는 특징을 가진다.
15와 12의 거리는 4와 15의 거리 + 4와 12 간의 거리와 같다. 이를 통해 두 노드간에 최단 거리를 구할 수 있다.
그래프
기업에서 코딩테스트로 가장 많이 출제되는 유형인 그래프이다. 트리와 달리 아래의 이미지와 같이 사이클(반복 구간)이 존재하는 자료구조이다.
정의는 다음과 같다.
그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.
DFS와 BFS
DFS와 BFS는 각각 깊이 우선 탐색과 너비 우선 탐색을 뜻한다.
구현의 차이DFS를 가만히 살펴보면 우리가 지금까지 연습했던 재귀 함수와 비슷하게 동작함을 알 수 있다. 현재 상태를 기준으로 계속해서 상태를 갱신하며 자식을 우선으로 탐색하는 방식이다. 실제로 DFS는 stack을 이용하는 방식이다.
반면에 BFS 는 현재 상태에 연결된 노드를 우선적으로 살핀다. 이 때 다음에 탐색할 연결 노드들은 Queue 구조에 담긴다.
메모리 공간의 사용탐색에 규칙을 보듯이 DFS 는 세로로 긴 그래프를 만날 시에 메모리 공간이 많이 필요하게 된다.
반대로 BFS 는 가로로 넓은 그래프를 만날 시에 메모리 공간이 많이 필요하게 된다.
일반적인 사용 용도기본적으로 DFS 는 구현이 간단하므로 원하는 경로가 존재하는지를 판별할 때등 간단히 처리될 수 있는 문제에 활용된다.
BFS 는 탐색 전에 연결된 노드를 먼저 한 번 처리할 수 있기 때문에 최단 경로 알고리즘, Dijkstra 등 고급 알고리즘에 더욱 많이 쓰인다. 특히 간선(edge)에 가중치가 없는 모든 BFS는 매 방문 시 출발 시점부터 최단 경로를 가진다.
즉 DFS 보단 앞으로는 BFS 를 쓰는 일이 더 많을 것이다!
보통 예제 입력은 위와 같이 주어진다. 이 때, 단방향인지 양방향인지 문제에서 꼭 확인하도록 한다.
vector<int> Graph[1005];
// const Grahp = []; 스크립트 언어에서는 2차원 배열을 선언하면 된다.
for(int i=0; i<M; i++) {
int a,b;
scanf("%d %d", &a, &b); // 입력값 a, b
v[a].push_back(b); // 양방향일 때는 서로에게 연결한다.
v[b].push_back(a); // 단방향일 때는, 해당 라인처럼 역방향 연결은 하지 않는다.
}
C++
그리고 각각의 DFS 및 BFS 템플릿은 다음처럼 주어진다.
// DFS
bool visited[GRAPH_SIZE];
void DFS(int x) {
if(visited[x]) return;
visited[x] = true;
printf("%d ", x);
for(int i=0; i<v[x].size(); i++) DFS(v[x][i]);
}
C++
DFS는 익숙한 데 비에 BFS는 큐를 통한 탐색이 처음이니 잠깐 살펴보자.
// BFS
bool visited[GRAPH_SIZE];
void BFS(int x) {
queue<int> q;
q.push(x); // 처음 방문할 노드를 큐에 담는다.
visited[x] = true;
while(!q.empty()) { // 더 이상 다음에 방문할 노드가 없을 때까지
int next = q.front(); // 가장 먼저 방문한 노드를 소비하여, 해당 노드의 인접노드를 찾는다.
q.pop();
printf("%d ", next);
for(int i=0; i<v[next].size(); i++) { // 해당 노드의 인접노드들을 반복하면서
int value = v[next][i];
if(visited[value]) continue; // 이미 방문한 노드라면 생략하고
q.push(value); // 그렇지 않다면 방문한다.
visited[value] = true;
}
}
}
C++
queue를 통한 탐색은 더 이상 연결할 요소가 없을 때 까지 계속해서 연결 요소를 추가하며 탐색한다. queue에 담겨진 노드는 “다음에 방문할 노드”이다.
BFS 는 앞으로 나올 여러 그래프 알고리즘에도 사용되니 꼭 능수능란하게 사용할 수 있어야 한다.
아래는 DFS 및 BFS 로 풀 수 있는 기본 문제들이다. 위 템플릿을 잘 이해하고 있다면 실버 상위권 골드 하위권 수준의 문제를 푸는게 이제는 어렵지 않을 것이다.
실버 1~2 난이도의 문제
골드 4~5 난이도의 문제
최단 경로 알고리즘
위에서 BFS 는 가중치가 없는 그래프에 대해서 매 방문 시 출발점에서 부터 최단 경로를 가진다고 말했다. 이것이 가능한 이유는 BFS 로 탐색할 시에 모든 “이전 노드" 들이 “최단 경로"이기 때문이다.
바꿔 말하면, 현재 위치를 최단 경로로 가기 위해서는 이전 경로로 최단 경로여야 한다.
이전까지 보았던 그래프와 달리 간선(edge) 별 가중치가 존재하는 경우에는 최단 경로를 구하기 위한 특별한 알고리즘을 사용한다.
하지만 최단 경로의 가장 기본적인 컨셉은 같다. 이전 경로가 항상 최단 경로라면 현재 경로의 최단 경로를 구할 수 있다.
그림에서와 같이 각 노드로 이동하기 위해서는 가중치(거리)만큼 걸린다고 하자.
이 때, 7까지 방문하기 위한 최단 경로를 구하려면 어떻게 해야 할까.
다시금 말하지만 모든 알고리즘에서 최단 경로는 현재 위치를 최단 경로로 가기 위해서는 이전 경로로 최단 경로여야 한다.
즉, 7 와 인접한 5, 4, 6 는 각각 이미 최단 경로이고 다음 7 로 오기 위한 가중치를 합해 셋 중 가장 짧은 최단 경로를 선택하면 된다.
최단 경로는 현재 위치를 최단 경로로 가기 위해서는 이전 경로와 현재 가중치의 합이다.
그리고 이전 경로는 항상 최단 경로이다.
다익스트라 알고리즘(Dijkstra Algorithm)
다익스트라 알고리즘은 한 점에서 모든 점까지의 최단경로를 구하는 알고리즘이다.
위 그래프에서 1 에서 출발할 때, 2 와 3 의 각각의 최단 경로를 구하려면 어떻게 해야 할까?
3 은 1에서 3 까지 이고
2 는 1 3 을 거쳐 가는 것이 최단거리 일 것이다.
위와 같이 가중치의 크기를 바꿔 생각해보자.
3 은 1 에서 3 까지 바로 가는 것이 최단거리이고
2 는 1 에서 2 까지 바로 가는 것이 더 빠를 것이다.
이 차이는 무엇일까?
매 방문시마다, 직전 최단 경로와 가중치의 합을 구해 해당 노드의 최단 경로를 갱신한다.
이 규칙을 조금 더 살펴보면 나와 연결된 노드의 직전 최단 경로(노드 3, 최단경로 2) 가 내 현재 최단 경로(노드: 2, 최단 경로 1) 보다 크다면 계산하지 않아도, 나의 현재 최단 경로 가 최단 경로임을 알 수 있다.
즉, 현재 최단 경로 중 최소값은 “나의 현재 최단 경로"가 보장되기 때문에, 해당 노드를 방문하는 것이 최단 경로임을 보장 받는다.
코드를 살펴보자.
const int INF = 9999999;
int cost[GRAPH_SIZE];
void dijkstra() {
for(int i=0; i<N; i++) cost[i] = INF;
cost[S] = 0;
C++
가장 먼저 각 노드의 비용을 담을 배열이 필요하다. 이 때, 초기 값은 표현할 수 있는 가장 큰 값 으로 설정한다. 그 이유는 위에서 보았듯이 최소값은 “나의 현재 최단 경로"가 보장되기 때문에 현재 상태의 최소 비용은 다음 방문할 노드를 선택하는 기준이 된다.
때문에 cost[S] 부분에서 시작노드의 비용을 0 으로 설정한다. 이 뜻은 시작 노드의 최단 경로는 0 이라고 확정했음을 의미한다.
// for(int i=0; i<N; i++) cost[i] = INF;
// cost[S] = 0;
for(int i=0; i<N; i++) { // 모든 노드에 대해서 반복한다.
int min = 9999999, minIndex = -1;
// 현재 상태에서 방문하지 않은 노드 중 최소 비용을 가진 노드를 찾는다.
for(int j =0; j<N; j++) {
if(!visited[j] && cost[j] < min) {
min = cost[j];
minIndex = j;
}
}
// 방문하여, 인접노드의 최소 비용 값을 갱신한다.
visited[minIndex] = true;
for(int j=0; j<v[minIndex].size(); j++) {
if(cost[minIndex] + weight[minIndex][j] < cost[v[minIndex][j]])
// 인접노드의 비용보다, 현재 노드와 그 가중치의 합이 더 작은 경우에 갱신한다.
cost[v[minIndex][j]] = cost[minIndex] + weight[minIndex][j] ;
}
}
C++
그리고 나면 모든 노드에 대해서 계속 현재 상태의 최소 비용을 가진 노드를 반복하며 값을 모두 채워넣으면 시작점부터 각각의 노드의 최소비용만이 남게 된다.
우선 순위 큐
그런데 다익스트라 알고리즘은 기본적으로 BFS 와 유사하다. 다만 BFS 달리 인접한 노드 순서가 아니라 최단경로가 작은 노드 순서 대로 처리되어야 하는 문제점을 가진다. 이를 해결하기 위해서는 큐에 입력 시 매번 정렬하여 저장하는 우선 순위 큐(힙)을 이용하면 문제가 해결 가능하다.
다만, 언어 스펙 상 지원하지 않는 경우도 많으므로 코드만 참고 삼아 간단하게만 살펴보자.
priority_queue<pair<int,int, ascending>>pq; // 큐에 가중치와 인덱스를 페어로 저장한다.
pq.push({0, 0}); // 가중치 : 0 시작 노드 : 0으로 시작한다.
cost[start]=0;
while(!pq.empty())
{
int dist = pq.top().first; // 가중치가 최소인 가중치를 가져온다.
int curr = pq.top().second; // 가중치가 최소인 인덱스를 가져온다.
pq.pop();
if(visited[curr]) continue;
visited[curr] = true;
for(int i=0; i<v[curr].size(); i++) // 반복한다.
{
if(dist + weight[curr][i] < cost[v[now][i]])
{
cost[v[now][i]]= dist + weight[curr][i];
pq.push(make_pair(cost, v[now][i]));
}
}
}
C++
이처럼 우선순위 큐를 이용하게 되면 매 삽입마다 만큼 연산하고 연결된 간선만큼 for문을 반복하기 때문에 총 만큼의 시간복잡도가 소요된다. 때문에 이전에 2중 for문을 이용한 보다 좋은 성능을 낼 수 있는 점을 확인 할 수 있다.
위의 기본이 되는 최단경로 알고리즘을 반드시 익히는 것을 추천한다.
그 외에 추천 연습 문제들이다.
9. DP(Dynamic Programming)
기업 문제에서 많이 출제되는 DP이다.
다만, 유형이 뚜렷하게 정해져 있지 않다보니(혹은 아직 발견하지 못해서) 따로 기본이 되는 템플릿이 있지 않다.
다만 DP 및 분할정복에 속한 문제들의 기본적인 패턴은 이전에 연산한 값을 참조하여 현재 값을 만드는 식을 세워 그대로 작성한다. 이러한 식을 점화식 이라고 부른다.
피보나치 수열
DP의 대표적인 예제로 피보나치 수열을 구하는 문제가 있다.
피보나치 수열은 내 이전 값과 이전 이전 값을 합한 값이 나의 값을 가지는 규칙을 의미한다.
예를 들어 5는 이전 값인 3과 이전 이전값인 2를 합하여 나온 값이다.
여기서 현재 값에 대한 식을 세울 수 있다.
이
이를 점화식이라고 부른다. 이렇게 세운 점화식은 top-down 방식과 bottom-up 으로 작성할 수 있다.
점화식을 작성할 때 가장 중요한 법칙은 부분 문제는 다 풀려 있다는 가정을 머리속에 항상 하고 있어야 한다는 점이다.
절때 정확한 점화식이 없는 채 코드를 작성해서는 안된다.
top-down 방식은 큰 값부터 차례대로 구해나가는 방식으로 다음과 같이 재귀함수로 작성할 수 있다.
int Fibonacci(i) {
if(i == 0 || i == 1) return 1;
return Fibonacci(i-1) + Fibonacci(i-2);
}
Fibonacci(5); // Fibonacci(3) 과 Fibonacci(4) 를 더한 어떤 값.
C++
이를 그림으로 표현하면 다음과 같이 호출 스택이 쌓일 것이다.
이 때 문제점이 하나 발생하는데, 바로 중복되는 호출이 존재한다는 것이다.
이러한 문제 때문에 bottom-up 방식을 통한 DP(Dynamic Programming)을 통한 해결방법이 존재한다.
top-down 과는 다르게 가장 작은 값부터 하나씩 구해가는 방식이다.
int Fibonacci[6];
Fibonacci[0] = 1; // 초기 기저 조건 설정
Fibonacci[1] = 2;
for(int i=2; i<=5; i++) {
Fibonacci[i] = Fibonacci[i-1] + Fibonacci[i-2]; // 점화식 구현
}
C++
이처럼 배열을 선언하고, 점화식으로는 구할 수 없는 기저 조건을 설정하고, 그 이후에 점화식에 맞게 구현을 하여 문제를 해결하는 방식이다. 이 방식은 이미 구해진 부분 문제를 참고해 현재 값을 구하기 때문에 중복해서 이전 값을 연산하지 않는다.
이러한 방식은 분할 정복법에서 했던 방식과도 동일하다 각각의 상태를 부분 문제로 보고 해당 문제를 해결하기 위한 식을 구한 다음 그대로 적용하는 방식이다.
다만 이 규칙을 발견하는 것은 많은 경험이 필요하다.
위 문제를 읽어보고 어떠한 점화식을 세울 수 있는지 고민 해보길 바란다.
충분히 고민해보고 모르겠다면 구글링을 통해 답을 알아보길 바란다. 답을 확인했다면 정말 쉽지 않음을 확인 할 수 있을 것이다.
접근 방법도 복습할 겸 기본적인 한 문제만 같이 풀어보자.
1.
계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2.
연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3.
마지막 도착 계단은 반드시 밟아야 한다.
맨 아래부터 시작하여 도착 지점에 도달할 때 까지 위의 규칙을 따라 “가장 높은 점수”로 올라가야 한다.
위의 예시에서는 10, 20, 25, 20 순으로 올라가면 가장 높은 점수로 올라 갈 수 있다.
단순히 보면 “DFS 기반 완전 탐색”으로 풀릴 것 처럼 보이나, 계단의 개수 300은 DFS를 처코드는 다음과 같다.리하기에는 큰 수이므로 다른 방식을 써야 한다.
이 때, 규칙을 살펴보면 N층 이전에 갈수 있는 방법은 N-1층에서 오거나 N-2층에서 오는 두 가지 방식이 있다. 근데 N-1 층에서 오는 경우 중 연속된 세 개의 계단 이 있을 수 있으니, 이에 대한 직접적인 접근은 2의 규칙을 무시하는게 된다.
N-1 층에서 올라오는 경우 중 연속된 세계의 계단 을 오르지 않으려면 N-1 이전에 N-3 에서 올라와야 함을 알 수 있다. 즉 N-1 층의 점수에 N-3에 최대 값을 더한 값과 N-2 층 까지의 최대값을 비교하면 된다.
이 규칙을 점화식으로 적용하면 다음과 같다.
코드는 다음과 같다.
int arr[301];
int F[301];
for(int i=1; i<=n; i++) {
scanf("%d", &arr[i]);
}
F[0] = 0;
F[1] = arr[1];
F[2] = arr[1];
for(int i=3; i<=n; i++) {
F[i] = arr[i] + std::max(arr[i-1] + F[i-3], F[i-2]);
}
for(int i=0; i<=n; i++) {
printf("%d\n", F[i]);
}
C++
마치며
아직 저도 알고리즘을 잘하는 수준은 아니라는 점 잘 압니다. 하지만 알고리즘을 공부하며 매일 어떤 부분이 중요하고, 어떤 순서로 공부하는 것이 가장 좋을지 고민하여 작성했습니다.
앞으로도 계속 틈틈히 알고리즘 문제를 풀다 좋은 접근 방법 및 패턴을 발견할 때마다 글을 계속 업데이트 할 예정이니 틈틈히 방문해주시면 조금 씩 더 나은 공략법이 되어있으리라 생각합니다.
마지막으로 백준에서 선정한 중요한 문제를 담은 문제집 공유하며 마무리하겠습니다. 건투를 빕니다.
