poArlim poArlim

1. 탐욕적 기법(Greedy Algorithm)이란? 탐욕적 기법, 혹은 욕심쟁이 기법이라고 불리는 이 알고리즘은 말 그대로 욕심쟁이처럼 항상 눈앞의 가장 큰 이익만을 좇는 방법이다. 대부분의 알고리즘은 큰 문제를 작은 문제로 쪼개어 해결하는 과정을 거치는데, 탐욕적 기법은 작은 문제들을 해결하는 과정에서 전체 결과를 생각하지 않고 당장 작은 문제의 최적해를 찾고 이를 모두 더하여 최종 결과를 도출하게 된다. 이러한 기법은 생각보다 잘 통하는 경우가 많지 않다. 아래 그림을 보자. 서울에서 부산까지 최단거리로 가는 방법은 서울->대전->부산의 경로로 4.5km 이지만, 이 상황에 탐욕적 기법을 적용하면 알고리즘은 각 단계에서 최적해, 즉 가장 가까이 있는 도시로 이동하여 서울->인천->대전->부산의 경..

https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 접근 우선 문제의 접근법부터 생각해야 한다. 이 문제를 이분탐색으로 풀게 된 이유는 문제의 범위를 보면 간단히 알 수 있다. 입국 심사를 기다리는 사람이 최대 1,000,000,000 명, 한 명을 심사하는 데 걸리는 시간이 최대 1,000,000,000 분이므로 O(n) 의 시간복잡도 마저 부담스러운 값이 나온다. 이러한 매우 큰 범위가 주어지면, O(logn)..

이분 탐색이란 주어진 데이터 중에서 원하는 데이터를 찾는 탐색 기법 중 하나로, 전체 범위를 두 부분으로 나누는 과정을 반복하여 목표값을 찾아내는 기법이다. 간단하게 예를 들면, 레크레이션 등에서 많이 하는 업다운(Up, Down) 게임을 생각하면 된다. 1~100 숫자 중 사회자가 생각한 숫자를 맞출 때 중간값인 50을 처음 부르고 이후 사회자의 Up, Down 대답에 따라 75, 25 등 나머지 범위의 중간값을 계속 부르는 방식으로 진행된다. 진행 순서 초기 설정 (left = 최소 index 값, right = 최대 index 값) mid 값 설정 (left : 최소 index 값, right : 최대 index 값, mid = (left+right)/2 ) 이분 탐색을 적용하기 위해서는 데이터가 ..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 대표적인 DP 문제이다. 우선 문제를 보는 순간 점화식으로 표현될 것 같다는 생각이 든다. 2*n 크기의 직사각형을 1*2, 2*1 두 종류의 타일로 채울 때, 모든 경우는 2가지로 나눌 수 있다. 가장 왼쪽 타일이 2*1 타일로 시작하는 경우 가장 왼쪽 타일이 1*2 타일로 시작하는 경우 -> 1*2 타일은 위아래로 붙어서 2*2 형태로만 존재할 수 있다. 타일의 종류는 2종류만 존재하므로 가장 왼쪽 타일은 2*1타..

동적 계획법(Dynamic Programming) 짧게 줄여서 DP 라고 부르는 이 알고리즘은 분할정복(Divide and Conquer) 알고리즘과 마찬가지로 복잡한 문제를 여러 개의 부분 문제들(Sub-problem) 으로 나누어 푼 후, 그 결과를 이용하여 복잡한 문제를 푸는 알고리즘이다. 다만 분할정복 알고리즘과의 차이는 DP 에서는 각 부분 문제들간에 겹치는 부분이 존재한다는 것인데, DP 는 이러한 겹치는 부분들을 메모이제이션(Memoization) 이라는 기법을 사용하여 단 한 번만 계산하도록 함으로써 알고리즘의 작동 시간을 줄이는 게 핵심입니다. 그렇다면 메모이제이션이라는 것은 무엇인지 알아봅시다. 피보나치 수열을 예로 들면, 아래와 같이 Fib(0) ~ Fib(3) 은 동일한 값을 구하는..

하노이의 탑은 3개의 기둥과 서로 크기가 다른 여러개의 원판들이 있을 때 이 원판들을 한 기둥으로부터 다른 기둥으로 옮기는 일종의 게임입니다. 게임을 시작하기 전 초기 상태는 3개의 기둥 중 하나의 기둥에 모든 원판들이 아래에서부터 크기가 큰 순으로 놓여져 있으며, 최종 목표는 이 원판들을 하나씩 옮겨서 순서 그대로 다른 기둥에 쌓는 것입니다. 이 때 2가지 규칙이 있습니다. 원판은 한 번에 한 개씩만, 기둥에서 기둥으로만 움직일 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 하노이탑은 재귀함수를 사용하여 해결할 수 있는 대표적인 문제입니다. 1, 2, 3번 기둥이 있고, n 개의 서로 다른 크기의 원판들이 있다고 할 때 1번 기둥에 쌓여져 있는 n 개의 원판들을 모두 3번 기..