thumbnail

동적 계획법 테크닉 정수 이외의 입력에 대한 메모이제이션 문제 2 - 실험 데이터 복구

문제 풀이 1. k개의 문자열들의 앞뒤로 겹치는 범위 파악하기 2. 현재 사용한 문자열, 마지막으로 사용한 문자열을 파라미터, 캐쉬 인덱스로 사용 3. 모든 문자열을 사용한 경우 기저사례 4. 겹치는 범위(overlap)가 최대가 되게끔 재귀 함수 호출 5. 재귀 함...

2019년 7월 31일0개의 댓글

동적 계획법 테크닉 정수 이외의 입력에 대한 메모이제이션 문제 1 - 웨브바짐

image.png 문제 풀이 가격을 구성하는 숫자들을 재배열 하는데, 이전 가격 e이하이면서 m으로 나누어 떨어지는 숫자를 찾는 문제이다. 가격의 최대 자릿수가 14자리까지 가능하므로 단순한 완전 탐색으로는 풀 수 없는 문제이다. 가격이 될 수 있는 몇조개...

2019년 7월 31일0개의 댓글

동적 계획법 테크닉 - 정수 이외의 입력에 대한 메모이제이션

필요성 일반적으로 DP를 사용할 때 저장된 값의 인덱스는 정수이다. 그러나 저장하려는 값이 정수가 아니라 배열일 경우 캐쉬에 해당 값을 저장하고 불러오는 게 매우 불편하다. 이 때 map자료구조를 사용할 수 있는데 , map자료구조는 비교와 연산에 시간이 오래걸리기 ...

2019년 7월 30일0개의 댓글

동적 계획법 테크닉 문제 2 드래곤 커브

image.png 문제 파악 처음 문제를 봤을 때는 세대 별 규칙을 파악해서 그 세대에 해당하는 문자열부터 시작해서 아래 세대로 쪼개서 내려가면서 해당 위치에 있는 문자열들을 찾는 방식일 것이라고 어렴풋이 생각했다. 세대 별 문자열들 간의 규칙 까지는 찾았는...

2019년 7월 30일0개의 댓글

동적 계획법 테크닉 문제 1 - KLIS

image.png 문제 파악 DP를 통해 일반적으로 해결하는 문제의 답은 총 개수나 최종적인 확률을 구하는 문제이다. k번째 해당하는 답의 실제 값을 구하는 것은 추가적인 처리가 필요하다. DP가 동작하는 과정에서 총 개수를 기록해놓고 k번째 값을 찾아나가는데...

2019년 7월 30일0개의 댓글

DP 테크닉 실제 답 계산하게 문제1 여행 짐 싸기

image.png 문제 풀이 대표적인 가방 채우기 문제, 탑 다운 방식으로 해결하려고 했으나 캐쉬를 잘못 저장해 시간이 많이 소요 되었다. 실제 답을 계산하는 방식은 갱신될 때 기록하는 방법이 있는데 이 문제의 경우 필요 없는 아이템은 캐쉬값을 비교함으로서 ...

2019년 7월 26일0개의 댓글

그래프 최소 스패닝 트리 문제 1 여행 경로 정하기

image.png 문제 파악 일반적인 최소 스패닝 트리는 트리의 가중치 합이 최소가 되어야 한다. 그러나 이 문제의 요구 조건은 스패닝 트리를 이루는 가중치의 최대값과 최소값의 차이가 최소가 되어야 하는 것이다. 생각한 방식은 min값과 max값을 계속 갱신해 ...

2019년 7월 25일1개의 댓글

그래프 최소 스패닝 트리

크루스칼 알고리즘 크루스칼 알고리즘이란 크루스칼 알고리즘과 프림 알고리즘은 최소 스패닝 트리를 만들기 위해 자주 쓰이는 알고리즘이다. 크루스칼 알고리즘의 원리는 매우 간단하다. 그래프의 간선들을 가중치 순으로 정렬해 가장 작은 가중치부터 그리디 알고리즘과 같이 선택...

2019년 7월 25일0개의 댓글

그래프 - 최단거리 알고리즘3 플로이드 워셜 알고리즘

플로이드 워셜 알고리즘이란 다익스트라 알고리즘과 벨만 포드 알고리즘은 특정 시작 정점을 기준으로 다른 정점들까지 가는 최단 거리를 구할 때 사용하는 알고리즘이다. 플로이드 워셜 알고리즘은 모든 정점들간의 최단 거리를 구할 때 사용하는 알고리즘이다. 그 구현 방식...

2019년 7월 23일0개의 댓글

그래프 - 최단거리 알고리즘 2 벨만 포드 알고리즘

image.png 벨만 포드 알고리즘이란 한 정점을 기준으로 다른 정점과의 최단 거리를 찾아주는 알고리즘이다. 다익스트라 알고리즘과의 차이는 다익스트라 알고리즘의 경우 음수 사이클이 존재하는 경우 제 기능을 하지 못한다. 그러나 벨만 포드 알고리즘의 경우 음수...

2019년 7월 23일0개의 댓글

그래프 - 최단거리 알고리즘 1 다익스트라 알고리즘 문제 3 철인 N종 경기

image.png 문제 파악 두 선수의 기록 시간이 동일하면서 최소 시간으로 운동 종목을 선택하는 문제이다. 종목을 선택하는 것을 간선으로 보는 것을 제외하고선, 그래프로 보는 사고가 생각나지 않아 해결하지 못했다. 문제 풀이 문제 풀이의 핵심은 이 전에 ...

2019년 7월 23일0개의 댓글

그래프 - 최단거리 알고리즘 1 다익스트라 알고리즘 문제2 - 소방차

image.png 문제 파악 최단 거리를 구하는 문제지만 특이한 조건들로 인해 간단히 접근할 수 없다. 먼저 정점들이 소방서, 불난 곳, 불나지 않은 곳으로 나뉘어져 있다. 불난 곳들과 소방서 사이의 최단 거리를 구해야 한다. 따라서 정점마다 가장 가까운 소방서...

2019년 7월 22일0개의 댓글

그래프 - 최단거리 알고리즘 1 다익스트라 알고리즘 문제1 ROUTING

image.png 문제 풀이 다익스트라 알고리즘의 새로운 간선의 가중치를 더하는 부분을 곱하기로 바꿔주면 된다. 이 때 우선순위 큐의 초기값으로 0이 아닌 1 또는 -1을 넣어줘야 하는 것을 주의 해야 한다. 초기값이 0이 아니라 노이즈가 없는 경우 1이기 때문...

2019년 7월 22일0개의 댓글

그래프 - 최단거리 알고리즘 1 다익스트라 알고리즘

다익스트라 알고리즘이란 다익스트라 알고리즘은 그래프의 정점들 사이에 가중치가 주어졌을 때 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라를 비롯한 대부분의 최단 거리 알고리즘은 음수 가중치를 갖는 간선이 있는 경우 음수 싸이클을 돌면서...

2019년 7월 22일0개의 댓글

그래프 BFS 문제2 - 어린이날

image.png 문제 파악 답이 될 수 있는 숫자를 구성하는 숫자가 정해져 있으므로, 답을 구성할 수 있는 숫자들을 그래프의 노드로 보고 BFS로 탐색하면서 최소가 되는 답을 찾을 수 있지 않을까 생각했다. 그러나 문제점은 이런 방식으로 탐색할 경우 답이 존재...

2019년 7월 18일0개의 댓글

그래프 - BFS 문제1 Sorting game

image.png 문제 파악 배열의 원소를 최소 횟수로 뒤집어 정렬된 배열을 만드는 문제이다. 배열의 최대 크기가 8이고 배열이 한 번 뒤집힐 때마다 다른 상태가 되며 정렬된 상태로 나아가야 된다는 점에서 착안해 배열의 현재 순서를 string으로 나타내 그래프...

2019년 7월 17일0개의 댓글

그래프 - BFS

BFS란 BFS 너비 우선 탐색이란 그래프의 탐색 알고리즘 중 한 가지이다. 너비 우선 탐색은 깊이 우선 탐색과 그래프 탐색 방식의 두 축을 이루는데, 깊이 우선 탐색이 더 이상 경로가 없을 때 까지 계속 한 방향으로 들어가는 것과 달리 시작점과 가까운 노드부터 탐...

2019년 7월 17일0개의 댓글

펜윅트리 문제1 삽입정렬 시간 재기

문제 풀이 이 문제에는 세 가지 풀이가 있다. 1. 펜윅 트리 활용 펜윅 트리는 구간합을 간단하고 빠르게 구할 수 있는 자료 구조이다. 구간합을 활용해서 이 문제를 푸는 방법은 펜윅 트리의 크기를 문제에서 주어진 정수 범위로 하는 것이다. 모든 정수에 대해여 펜윅...

2019년 7월 16일0개의 댓글

이진수 마지막 비트와 and연산

마지막 비트 제거 and 연산자를 활용하면 이진수의 마지막 비트를제거할 수 있다. 10의 이진수 표현은 1010이다. 10에서 1을 뺀 9의 이진수 표현은 10의 마지막 비트를 뺀 1000이다. 따라서 10의 마지막 비트를제거하는 방법은 10에서 1을 뺀 값과 an...

2019년 7월 16일0개의 댓글

펜윅트리

펜윅트리 배열의 구간합을 구하는 데는, 구간 트리를 활용할 수 도 있지만 그 구현이 복잡해 조금 더 단순한 형태인 펜윅트리를 사용하는 것이 더 좋다. 펜윅트리란 배열의 첫 몇 개의 원소인 부분합을 활용하면 구간합도 빠르게 계산할 수 있다는 원리에서 출발한 구조이다....

2019년 7월 16일0개의 댓글