Algorithm/B. Basic Algorithms (10) 썸네일형 리스트형 26. Bitmasks 비트마스크(Bitmasks)(비트마스킹(Bitmasking)으로 불리는 경우도 있음)는 Bool 값으로 표현할 수 있는 대상이 여러 개 존재할 때 이를 정수의 비트를 이용해서 표현하는 기법이다. Bool 값으로 표현할 수 있는 대상은 대비되는 두 개의 속성만을 가지고 있어야 한다. 예를 들어 참(True)과 거짓(False), 켜진 상태(ON)와 꺼진 상태(OFF), 선택한 상태와 선택하지 않은 상태 등이 있다. 일반적으로 $8$바이트 정수 자료형으로 $64$개의 비트를 한번에 표현할 수 있고 그보다 큰 정수 자료형이 잘 쓰이지 않기 때문에 이보다 적은 비트만을 사용해서 문제를 풀 수 있는 경우에 주로 사용되지만 정수 배열을 이용해서 더 많은 비트를 사용하고 메모리와 실행 시간의 측면에서 더 성능이 좋은.. 25. Divide and Conquer 분할 정복(Divide and Conquer)은 큰 문제를 여러 개의 작은 부분 문제로 분할한 다음 각각의 부분 문제를 해결하고, 그 결과를 바탕으로 큰 문제의 답을 구하는 문제 해결 방법이다. 동적 계획법과 설명이 비슷하지만 동적 계획법에서는 중복되는 부분 문제가 있었다. 분할 정복의 부분 문제들은 서로 중복되지 않는다. 분할 정복에도 기저 사례가 존재하며, 기저 사례는 더 작은 부분 문제로 분할하지 않고 바로 해결할 수 있다. 분할 정복 자체가 재귀함수를 이용하여 구현하는 경우가 많기 때문에 코드에 자연스럽게 추가되기도 한다. BOJ 1629. 곱셈 (Silver I) 지수가 큰 경우의 거듭제곱을 구하는 문제가 분할 정복을 사용하는 대표적인 예시이다. 지수가 크기 때문에 $B$번 반복되는 반복문을 쓰.. 24. Dynamic Programming & Memoization 재귀를 설명한 글의 끝부분에서 입력값이 조금만 커져도 재귀호출 횟수가 급격하게 늘어나는 문제점에 대해서 언급했는데, 이렇게 되는 이유는 중복되는 부분 문제를 계산하는 횟수가 너무 많기 때문이다. 이 문제를 풀어 보면 알 수 있지만 피보나치 수를 구하기 위해서 이 글에 나온 것처럼 코드를 짜면 함수 호출의 횟수 자체가 피보나치 수만큼 증가하기 때문에 이렇게 해서는 빠른 코드를 짤 수 없다. 하지만 중복되는 부분 문제를 살펴보면 중복되는 부분 문제에 대한 답이 항상 같기 때문에, 만약 어떤 부분 문제의 답을 계산했다면 그 계산 결과를 저장한 뒤 나중에 같은 부분 문제를 풀 때 기존에 계산한 답을 사용하면 되므로 성능을 크게 향상시킬 수 있다. 이러한 방법을 메모이제이션(Memoization)이라고 한다. (.. 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^6$: 웬만하면 풀.. 이전 1 2 다음
