본문 바로가기

Computer195

[알고스팟] 쿼드 트리 뒤집기 문제: 쿼드 트리 뒤집기언어: Java 난이도가 중하 정도 되는 듯하다. 4개의 값과 링크를 가질 수 있는 QuadTree를 구성하고 구성된 QuadTree의 원소 순서를 바꿔 주면 된다. 이때 navigation 하는 코드 작성에 주의가 필요하다. (디버깅이 어려움) 예를 들어 xbwxwbbwb 입력 값은 다음과 같이 QuadTree로 표현된다. 이 그림을 상하로 뒤집기 위해서는 위2개와 아래 2개의 위치를 바꾸면 된다. 이떄 x 로 세분화된 픽셀은 그 내부도 바꿔 줘야 한다. 즉 다음과 같이 되는데, QuadTree를 보면 4개의 픽셀 표현 0,1,2,3 원소를 2,3,0,1 로 순서를 바꿔 주면 된다. 다음은 구현 코드이다. 2016. 9. 14.
[알고스팟] 최대 연속 부분합 찾기 문제: 최대 연속 부분합 찾기 언어: 자바 이 문제는 여러 방법으로 풀 수 있다. 아주 쉽게(무식하게) 풀고자 한다면 주어진 배열 {A1, A2, ..., An} 의 모든 서브배열을 구하고 이중 가장 큰 값을 찾는 것이다. 하지만 전체 탐색 시간은 n의 세제곱이 된다. 가능한 시간 내에 풀기 위해서는 Greedy 하게 풀거나 Dynamic 하게 풀 수 있다. [Greedy 방법] Wiki에 Maximum Subarray Problem 에서 kadane's algorithm 이 나와 있다. Kadane's algorithm 은 1) 현재의 조회하는 숫자를 해에 추가 하였을 때 0보다 작게 되면 현재까지의 해를 0으로 설정 2) 지금까지 최대 SubArray의 값보다 1)의 값이 크면 지금까지의 최대 Sub.. 2016. 9. 13.
[알고스팟] 출전 순서 정하기 문제: 출전 순서 정하기 언어: 자바 이 문제는 난이도가 "하"에 해당하는 문제이다. 출전 선수를 Rating 으로 정렬하고, 러시아의 Rating이 낮은 선수부터 한국의 Rating이 낮은 선수들을 비교하는데, 이길수 있는 최소한을 찾아서 승수에 더하면 된다. 2016. 9. 10.
Greedy Algorithm 과 크루스칼의 최소 신장 트리 & 다익스트라 최단 경로 1. Greedy Algorithm 과 크루스칼 최소 신장 트리 최소 신장 트리(Minimum Spanning Tree)는 그래프 내의 모든 정점을 최소의 비용으로 연결하는 트리이다. 최소 신장 트리를 구축하는데 한 가지 중요한 제약은 최소 신장 트리 내에 사이클이 형성되어서는 안된다는 것이다. 프림과 크루스칼 알고리즘 두 가지가 있는데, 크루스칼 알고리즘은 다음과 같이 동작 한다. 1) 그래프 내의 모든 간선의 가중치에 대한 오름차순 목록을 만든다. 2) 1)의 간선을 차례대로 순회하면서 간선을 최소 신장 트리에 추가한다. 단 추가된 간선으로 사이클리 생성되서는 안된다. 탐욕 알고리즘(Greedy Algorithm) 은 (해선택 -> 실행 가능성 검사 -> 해 검사) 가 반복되는 알고리즘이다. (Gre.. 2016. 9. 10.
동적 계획법과 거스름돈 예제 동적 계획법에 대해서는 오래전 포스팅을 한적이 있다. Dynamic programming 당시에 거스름돈에을 주는 방법에 대해서 로직을 설명하였는데, 이번 포스팅은 실제 예제를 구현해 보겠다. 동적 프로그래밍은 탐욕프로그래밍과는 달리 최적화된 솔루션을 다 찾는 알고리즘이다. 이전 포스팅(Greedy Algorithm 과 거스름돈 예제) 에서 설명했던 것처럼 거스름돈 예제에 있어서 탐욕 프로그래밍은 완벽한 해를 찾지 못한다. 물론 성능은 탐욕프로그래밍이 훨씬 좋다. 거스름돈 M원에 대해서 동전 C1,...Cn 으로 최소의 동전 개수로 주는 것을 생각해 보면 다음의 Sub 해법들이 존재하는데.. (M-C1) 원에 대해서 최소한의 동전 개수 +1 (M-C2) 원에 대해서 최소한의 동전 개수 +1 ... (M-.. 2016. 9. 10.
Greedy Algorithm 과 거스름돈 예제 탐욕 알고리즘은 각 단계의 부분 문제를 풀때 근시안적으로 최적해를 구한다고 해서 붙여진 것이다. 동적 계획법은 최적의 해를 구하긴 하지만 탐욕 알고리즘보다는 더 많은 연산을 요구한다. 탐욕 알고리즘은 동적 계획법과는 달리 최적의 해를 구해준다는 보장을 하지 못한다. 탐욕 알고리즘은 동적 계획법처럼 대상 문제가 최적 부분 구조를 갖고 있어야 한다. 탐욕 알고리즘은 다음과 같이 동작한다. 1) 해 선택: 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합에 추가한다. 2) 실행 가능성 검사: 새로운 부분해 집합이 실행가능한지 확인한다. (문제의 제약 조건을 위반하는지 검사한다) 3) 해 검사: 새로운 부분해 집합이 문제의 해가 되는지를 확인한다. 전체 문제의 해가 완성되지 않았다면 1) 부터 다.. 2016. 9. 9.

티스토리툴바