본문 바로가기

Algorithm

 (143)
23. Backtracking 퇴각 검색(백트래킹, Backtracking)은 문제의 답이 될 수 있는 경우를 단계별로 확인하면서 가능한 답이나 최적해를 구하는 방법이다. 만약 어떤 단계에서 답이 될 수 없다는 것이 확인되었다면 이전 단계로 돌아간다. 이렇게 이전 단계로 돌아가는 것을 가지치기(Pruning)라고 한다. 백트래킹 역시 명확하게 설명하기 쉬운 개념은 아니기 때문에 예제를 보면서 이해하는 것이 도움이 될 것이다. BOJ 15649. N과 M (1) (Silver III) 기본적인 백트래킹 문제이다. 함수 $f(k)$가 $k$개의 수를 고른 상태에서 호출된다고 하면, 남아 있는 $(n-k)$개의 수 중 하나를 고르고 $f(k+1)$을 호출한다. 만약 $k = m$일 경우 지금까지 고른 $m$개의 수들을 출력하고 이전 단계로..
22. Recursion 재귀(Recursion)는 재귀호출을 이용하여 문제를 해결하는 것이다. 재귀호출은 함수 내에서 자신을 다시 호출하는 것이며, 이러한 함수를 재귀함수라고 한다. 이것은 보통 문제에 주어진 상황으로부터 점화식을 유도할 수 있는 경우에 사용되는 방법이다. 물론 DFS같이 재귀함수가 등장하지만 이 유형으로 보기 어려운 것들도 있다. 재귀 문제를 풀 때는 먼저 주어진 상황을 어떻게 점화식으로 나타낼 수 있는지 구성하고, 그것을 바탕으로 재귀함수를 작성한다. 반복문 안에서 재귀호출이 발생할 수도 있다. 재귀함수에는 기저 사례(Base Case)를 처리하는 부분이 있어야 한다. 기저 사례는 재귀함수에서 나타날 수 있는 가장 기본적인 경우로 더이상 재귀호출을 할 수 없거나 재귀호출 없이 바로 처리할 수 있는 경우를 의..
21. Greedy 그리디(Greedy)는 각각의 상황에서 나중을 고려하지 않고 최선의 선택을 반복하는 방법으로 문제를 해결하는 것이다. 개념은 매우 간단하지만 적용하기가 만만치 않은 분야이기도 하다. 그리디로 문제를 해결하기 위해서는 각각의 상황에서 최선의 선택을 한 이후에 그 선택을 하기 전과 동일한 성질이 성립해야 한다. 그렇기 때문에 이후에도 같은 전략을 계속 사용할 수 있는 것이다. 또한 그리디는 보통 '가장 ~한 것'부터 처리하는 식으로 많이 구현되기 때문에 주어지는 값, 객체를 정렬해야 하는 경우가 많다. 그리디로 풀 수 있는 대표적인 문제 $2$개를 살펴보면 이해하기에 더 좋다. BOJ 5585. 거스름돈 (Bronze II)모든 잔돈에 대해 큰 잔돈의 가치가 작은 잔돈의 가치이 배수라는 것을 알 수 있다. ..
20. Simulation 시뮬레이션(Simulation)은 문제에 주어진 상황이 시간에 따라 변화하는 것을 직접 구현해서 문제를 해결하는 구현의 한 가지 방법이다. 시뮬레이션이 복잡한 문제들이 코딩 테스트(대회에는 별로 나오지 않는다)에 나오는 경우도 있는데, 이런 유형의 문제의 경우 헷갈리지 않게 구현하는 것이 중요하다. [연습문제] BOJ 14920. 3n+1 수열 (Bronze III) 더보기 유명한 문제다. 각각의 항을 직접 구하면서 $1$이 처음으로 나타나는 항을 찾으면 된다. BOJ 1966. 프린터 큐 (SIlver III) 더보기 프린터 큐의 작동을 시뮬레이션하면서 각각의 문서가 인쇄되는 순서를 찾는다. BOJ 17144. 미세먼지 안녕! (Gold V) 더보기 마찬가지로 공기청정기의 작동을 시뮬레이션하면 된다. ..
19. Brute Force 완전 탐색(Brute Force)은 가능한 모든 경우를 확인하면서 문제를 해결하는 방법이다. 이렇게 하면 당연히 실행 시간이 늘어나 성능이 좋지 않게 되는 경우가 많지만, 문제에서 주어지는 입력의 제한이 작은 경우 이 방법으로 문제를 풀 수 있는 경우도 많다. 온라인 프로그래밍 대회의 경우 입력의 제한을 작게 한 완전 탐색 문제를 쉬운 난이도의 문제로 내는 경우도 많으므로 초보자의 경우 문제를 풀기 위해 이 방법을 쓸 수 있는지를 판단하는 훈련을 하는 것이 중요하다. 일반적으로 입력의 크기와 시간복잡도를 통해서 계산한 최대 연산 횟수$(n)$가 얼마나 되는지에 따라 문제를 제한시간 내에 해결할 수 있는지의 여부를 판별할 수 있다. 제한시간은 $1$초를 기준으로 한다.$n \le 10^7$: 웬만하면 풀 ..
18. Implementation 구현(Implementation)은 문제의 상황에 맞게 코드를 짜는 가장 기본적인 문제 해결 방법이다. 엄밀히 말하면 거의 모든 문제(구현 없이 풀 수 없는 극소수의 문제가 존재하지만, 정답이 항상 정해져 있거나 넌센스 문제인 경우 말고는 사실상 가능성이 없다)에는 구현이 필요하지만, 보통 구현 문제라고 하면 문제를 풀기 위한 알고리즘에 비해 구현 자체가 문제 해결의 주를 이루는 문제를 말한다. 구현에 대한 설명은 사실 이것밖에 없다. 구현 연습은 직접 문제를 풀어 보면서 하는 것이 가장 효과적이다. [연습문제] BOJ 2438. 별 찍기 - 1 (Bronze III) 더보기 유명한 구현 문제이다. 중첩 반복문을 이용해서 별을 출력하면 된다. BOJ 10818. 최소, 최대 (Bronze III) 더보기..
17. Basic Algorithms Intro 코딩 문제를 풀 때 사용되는 다양한 알고리즘을 배우기 위해서는 기본적인 문제 해결 방법에 대해 알아야 한다. 기본적인 문제 해결 방법으로 다음과 같은 것들을 생각할 수 있다. 구현(Implementation)은 문제에서 요구하는 것을 직접 실행하는 것이다. 보통 구현 문제라고 하면 코딩이 문제 해결의 대부분을 차지하는 문제를 의미한다. 완전 탐색(Brute Force)은 문제의 조건에 맞는 가능한 모든 경우를 다 확인하면서 답을 구하는 것이다. 입력의 범위가 작은 경우 이 방법으로 문제를 풀 수 있는 경우가 많이 존재한다. 시뮬레이션(Simulation)은 문제의 상황이 시간에 따라 변하는 경우 이 변화를 직접 구현해서 문제를 해결하는 데 이용하는 것이다. 구현의 한 종류로 볼 수도 있다. 그리디(Gre..
16. Span span은 C++20에 추가된 컨테이너로 연속된 수열의 형태로 저장되는 객체(정적 배열, std::array, std::vector, std::string 등; std::deque은 할당되는 메모리가 연속되지 않을 수 있기 때문에 제외된다)를 나타낼 수 있다. 헤더파일 을 인클루드하면 span을 사용할 수 있다. span 클래스도 이 헤더파일에 정의되어 있다. span의 선언은 일반적인 시퀀스 컨테이너와 비슷한데, 복사 생성자를 이용하여 선언할 때 원본이 span이 아닐 수도 있다.#importusing namespace std;int main(){ int a[5] = {1, 2, 3, 4, 5}; array b({1, 2, 3, 4, 5}); vector c({1, 2, 3, 4, 5}..

티스토리툴바