user-thumbnail
@doontagi
안녕하세요.
SERIES

알고리즘

Brute force

2019년 6월 25일

재귀호출 단순히 중첩문을 반복하는 것에 비해 코드 수정이 용이해서 재활용 가능성이 높다. 재귀 함수의 종료를 위해 기저 사례를 선택해야한다. 재귀 함수가 가장 깊숙한 곳으로 들어간 경우, 재귀 함수의 목적을 달성한 경우, 반드시 지켜야 하는 특정 조건을 위배한 경우 더 이상 함수가 호출될 필요가 없기 때문에 함수가 반환되도록 해주는 것이다. 재귀 ...

Brute force 문제3 - 시계 맞추기

2019년 6월 26일

image.png 문제 풀이 과정 brute force를 통한 문제임을 알고 봤음에도 풀이 방법이 명확히 떠오르지 않았는데, 가장 큰 이유는 해결 가능한 문제로 바꿔주는 조건인 각 시계는 최대 세 번까지 밖에 조작하지 못한다는 조건을 깨닫지 못했기 때문이다. 시계는 세 시간씩 움직이므로 네 번 조작하게 되면 다시 처음의 시간으로 돌아가게 되고...

분할 정복 문제1- 쿼드 트리

2019년 6월 26일

문제 파악 분할 정복 유형이라는 것을 알고 접근했는데도 어떤 식으로 문제를 나눌 수 있는지 전혀 감이 오지 않았다. 분할 정복과 이전에 배운 단순한 재귀 호출을 통한 분할과의 차이점을 아직 완벽히 파악하지 못한 상태에서 문제에 접근하게 된것 같다. 압축을 먼저 전부 풀고 다시 압축을 하는 방식으로 생각해 봤는데 어떤 식으로든 중간 과정이 너무 복잡해져서...

분할 정복 문제2 - 울타리 잘라내기

2019년 6월 27일

image.png 문제 파악 이 문제가 분할 정복을 통해 해결될 수 있는 문제라는 느낌은 바로 들었다. 내가 생각한 방식은 높이 1부터 한 칸씩 올라가면서 가장 낮은 높이를 가진 판자를 만나면 분할시키는 방식이었다. 시간복잡도는 바로 생각하지 못하고 우선 구현했는데, 구현 과정에서는 가장 낮은 높이를 가진 판자가 여러 개 들어있거나, 붙어있는 경...

Brute force 문제2 - 게임판 덮기

2019년 6월 25일

image.png 2019-06-25 19:06 작성됨 문제 풀이 과정 문제 파악 과 .으로 이루어진 게임판에서 ㄱ자 모양의 블럭을 퍼즐처럼 채우는 경우의 수를 찾는 문제이다. 그래프와 기하 문제에 약해서 이런 문제는 보기보다 어렵게 느껴졌다. Brute force를 활용하는 문제이기 때문에 한 블록을 빈칸에 넣을 때마다 새로운 문제로 나뉘...

Brute force 문제1 PICNIC

2019년 6월 25일

image.png 문제 풀이 과정 문제 파악 정해진 조건에서 총 몇개의 경우의 수가 나올 수 있는지 구하는 문제이다. 문제의 입력도 크지 않아서 시간 제한은 고려할 필요가 없으며 한 쌍의 짝을 구하면 나머지 인원들에 대한 접근은 원래 문제의 부분 문제이므로 재귀함수를 통해 접근하는 문제임도 명확하다. 아마 가장 많은 고민을 필요로 하는 ...

동적 계획법(Dynamic Programming) - Memoization

2019년 6월 27일

동적 계획법을 사용하는 이유 동적 계획법은 부분 문제를 통해 큰 문제를 재귀적으로 해결하려고 할 때 중복되는 부분 문제들이 많이 발생하여 불필요하게 같은 계산이 반복될 때 사용된다. 이항 계수를 계산하는 공식은 아래와 같은 공식이 성립한다. bino(n, r) = bino(n-1, r-1) + bino(n, r-1) 위 식에 대해 생각해보면 ...

동적 계획법(Dynamic Programming) - 최적 부분 구조

2019년 6월 28일

최적 부분 구조란 앞서 살펴 보았던 동적 계획법 문제는 어떠한 값을 계산하거나, 경로가 존재하는 지에 대한 문제에 사용되었던 방식이다. 최적화 문제는 그러한 계산값이나 경로 중 어떤 것이 최적인지를 계산하는 문제인데, 이 때 설계하는 재귀 함수의 파라미터로 가장 필수적인 값만 넘겨주는 부분 문제의 구조가 최적 부분 구조이다. 이 때 불필요한 값까지 넘겨...

동적 계획법(Dynamic Programming) - 최적 부분 분석 문제1 - JLIS

2019년 6월 28일

문제 정의 지금까지 배워왔던 브루트 포스, 분할 정복, 일반 DP, 최적화 DP 모두 문제 해결 과정에서 가장 어려우면서 핵심적인 부분이 큰 문제를 적절한 부분 문제로 나누는 작업이다. 단순 LIS 문제는 수열이 한 개만 주어져서 부분 문제와 상위 문제들 사이의 관계가 비교적 명확하게 드러났는데, JLIS의 경우 수열이 두 개이기 때문에 그 과정이 ...

동적 계획법(Dynamic Programming) - 최적 부분 분석 문제2 - 원주율 외우기(PI)

2019년 6월 28일

image.png 문제 파악 나열된 숫자들에 대해 일정한 규칙을 가지고 적절하게 구간을 나누는 문제이다. 구간을 나눠가면서, 난이도의 최소값을 구하는 문제기 때문에 부분 문제로 나뉘는 문제임은 어렵지 않게 파악되었다. 끊을 수 있는 구간 역시 3,4,5 세 구간 밖에 없었기 때문에 복잡하게 느껴지지 않아서 대략적인 설계는 간단히 마칠 수 있었다...

동적 계획법(Dynamic Programming) - 경우의 수와 확률

2019년 7월 1일

오버플로 문제를 푸는 과정, 또는 정답에서 경우의 수를 구해야 하는 경우 구하고자 하는 정수의 수가 너무 커져서 int형의 size 4바이트를 초과해서 오버헤드가 발생할 수 있다. 이 경우 재귀 함수의 반환값에 모듈로 연산을 처리해 주면, 수의 크기가 훨씬 줄어들어 오버헤드를 방지할 수 있다. 예제 - 삼각형 위의 최대 경로 수 이 전에 풀었...

동적 계획법(Dynamic Programming) 경우의 수 문제 1 - 비대칭 타일링

2019년 7월 1일

문제 파악 원래 타일 개수에서 대칭되는 타일의 개수만 빼면 되는 것이므로, 대칭 타일의 수를 계산하는 DP알고리즘에 비대칭 타일의 개수만 계산해서 빼주면된다. 비대칭 타일의 개수는 짝수일 경우 홀수일 경우를 나눠서 생각하면 원래 칸의 숫자 N을 2로 나눠서 간단히 계산할 수 있다. 이 문제는 경우의 수가 매우 커서 모듈로 연산자가 반드시 필요한데,...

동적 계획법(Dynamic Programming) 최적 부분 분석 문제3 - 양자화

2019년 7월 1일

문제 풀이 직관적인 접근 양자화란 넓은 범위로 이루어진 자료를 더 좁은 범위로 표현하는 것이다. 문제의 양자화는 수열의 수 종류를 요구하는 범위까지 좁히는 것이다. 이 때 좁히는 조건은 각 수의 오차 제곱의 합이 최소가 되어야한다. 이 문제는 앞의 선택이 뒤의 선택에 계속해서 영향을 미치므로, 직관적으로 최적 부분 구조를 설계하는것이 쉽지 않다....

동적 계획법 - 경우의 수 문제2 - 폴리오미노

2019년 7월 3일

image.png 문제 파악 DP를 사용하기에 앞서 완전 탐색으로 접근하기 위해서 폴리오미노의 경우의 수를 따질 수 있는 방법을 생각해 보았다. 각 도형을 한 줄씩 나눠 개수를 더하는 방식을 생각해 보았는데, 이 과정에서 발생하는 중복과 개수별로 조합했을 때 발생하는 합친 도형의 개수가 달라져서 이 부분에서 처리를 어떻게 할지 생각해 낼 수가 없었...

동적 계획법 경우의 수와 확률 문제 3 - 두니발 박사의 탈출

2019년 7월 3일

image.png 문제 파악 문제를 이해하고, 각 days에 노드들의 확률이 서로 어떤 연관이 있음을 명확히 알 수 있었다. 각 노드들의 해당 날짜의 확률은 그 전 날 인접 노드의 확률로부터 얻어질 수 있음을 느낄 수 있었다. 따라서 이러한 직관을 바탕으로 days에 따른 노드들의 관계를 정의해 보았다. 해당 날짜에서 특정 노드의 확률은 그 전날...

그래프 문제1 - 고대어 사전

2019년 7월 4일

문제 정의 특정 개수의 문자열을 받고, 그 정보를 바탕으로 알파벳 사전 순서를 결정하는 문제이다. 그래프와는 관련이 없어 보이는 문제이지만, 위상 정렬의 특성을 확인하면 문제를 해결할 수 있다. 위상 정렬은 의존성을 가진 그래프, 즉 순서를 가진 그래프를 순서에 모순이 생기지 않도록 정렬해 주는 특성을 가지고 있다. 알파벳 사전 순서를 예로 들면 d...

그래프 - 오일러 서킷과 트레일

2019년 7월 4일

오일러 서킷이란 오일러 서킷은 그래프의 각 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 말한다. 대표적인 오일러 서킷의 사례는 한 붓 그리기이다. 오일러 서킷이 존재하려면 각 간선이 모두 한 컴포넌트 안에 있어야 하고 ( 서로 연결될 수 없는 위치에 간선이 존재해서는 안된다) 각 vertex에 연결된 엣지의 수 가 짝수여야 한다. 만약 홀수...

그래프 오일러 서킷 문제1 - 단어 제한 끝말 잇기

2019년 7월 4일

image.png 문제 파악 내가 생각한 접근법은 단어를 vertex로 보는 것이었다. 그러나 이렇게 그래프를 만든 뒤 오일러 서킷을 찾는 알고리즘을 실행시키면, 같은 단어를 두 번 사용하는 경우까지 따지게 되어 문제의 조건을 만족하지 못한다는 문제점이 생긴다. 그래서 해밀턴 경로를 찾는 알고리즘을 생각해 보았지만 해밀턴 경로를 찾는 알고리즘은 ...

그래프 - DFS와 그래프 간선의 분류

2019년 7월 5일

DFS를 통한 간선의 분류 DFS 스패닝 트리 깊이 우선 탐색을 수행하면 그 과정에서 그래프의 모든 간선을 최소 한 번씩은 만나게 된다. 그 중 처음 만나는 정점과 연결되는 간선은 따라가게 되는데, 이러한 간선들을 모아서 보면 트리 형태를 띠게 된다. 이러한 트리는 당연히, 모든 정점을 지나치므로 스패닝 트리가 되고 이를 DFS 스패닝 트리라고 ...

그래프 - DFS와 강결합 컴포넌트

2019년 7월 5일

강결합 컴포넌트란 강연결 요소라고도 불리는 강결합 컴포넌트는 유향 그래프 내에서 정의되는 개념이다. 유향 그래프에서 두 정점 사이에서 양 쪽 모두 이동할 수 있는 경로가 존재하면 두 정점은 같은 강결합 컴포넌트(SCC)에 속해 있다고 말한다. 만약 같은 SCC에 속한 두 정점 중 한 정점이 또 다른 정점과 같은 SCC에 속해 있으면 세 정점간 오고 가는 ...

그래프 DFS - 문제1 감시 카메라

2019년 7월 8일

문제 파악 image.png 그래프의 한 정점에서 인접한 정점끼리는 감시 카메라를 공유하는데, 이 때 모든 갤러리를 감시하는 감시 카메라의 최소 대수를 구하는 문제이다. 직관적으로 생각했을 때는 정점 별로 감시 카메라를 둔다고 가정했을 때 인접 정점들을 확인하면서 감시 카메라가 설치 되었는지 안되었는지를 체크 하면서 하나씩 늘려나가야 되는데 그 시작...