본문 바로가기

분류 전체보기

 (83)
빠른 정렬 - 분할 정복, 시간 복잡도 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 빠른 정렬 병합 정렬과 반대로 분할하는 과정에서 정렬된다. 배열의 원소 중 하나를 기준으로 하여 다른 원소들과 비교해 자리를 교환하며 정렬한다. 시간 복잡도 수행시간은 문제를 두 개의 부분 문제로 나누는 과정에 의해 지배된다. 병합 과정과 달리 분할된 부분 문제가 비슷한 크기로 나눠진다는 보장이 없다. 기준 원소가 최소값 혹은 최대값인 경우에 부분 문제의 크기가 하나씩만 줄어들 수도 있다. 이런 최악의 경우 O(n^2)의 시간 복잡도를 가진다. 평균적으로 부분 문제가 절반에 가깝게 나눠질 때 병합 정렬과 같은 O(nlgn)의 시간 복잡도를 가진다. 이런 경우는 단지 나눌 때 정렬하는지, 합칠 때 정렬하는지의 차이라고 볼 수 있다. C++ 코드..
[알고스팟] 시계 맞추기 - 완전 탐색, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 시계 맞추기(링크) 접근 방법 TSP 문제처럼 스위치 10개를 순차적으로 누르며 각 스위치를 3번 누를 때까지 (4번 누르는 것은 안 누르는 것과 같다.) 재귀 호출했다. 실패 원인 이 문제는 TSP처럼 도시의 (스위치의) 방문 순서 (누르는 순서)가 중요하지 않다. (1번 누르고 4번 누르는 것과 4번 누르고 1번 누르는 것은 완전히 동일하므로.) 핵심은 각 스위치당 얼마나 누르는지를 중점으로 재귀호출해야 한다. C++ 코드 #include using namespace std; const int INF = 9999, SWITCHES =10, CLOCKS = 16; const char linked[SWITCHES][CLOCKS+1] = { "..
병합 정렬 - 분할 정복, 시간 복잡도 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 병합 정렬 주어진 배열을 크기가 1 이 될 때까지 절반씩 나눈다. 길이 1짜리 수열들을 서로 합치는 과정에서 크기를 비교해 정렬한다. 실제로 배열을 나누는 과정은 인덱스의 위치를 조정하는 것으로 O(1) 에 수행되고 나뉜 배열을 합치는 과정에서 각 원소 모두를 비교해 정렬한다. 즉, n 개 배열에 대해 O(n) 의 비교 과정을 거친다. 나눠진 배열을 합치는 과정을 원본 배열이 나눠진 횟수만큼 반복해야 한다. 길이가 n 인 원본 배열을 항상 거의 절반으로 나누므로 나눠진 횟수는 로그 n 이다. 따라서, 병합 정렬의 시간 복잡도는 O(n * lgn). 자세한 구현은 코드의 주석으로 확인해보자. vector v, tmp; void mergeSort..
분할 정복 알고리즘에 대해서, 수열의 빠른 합 문제 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 분할 정복 문제를 거의 같은 크기인 둘 이상의 부분 문제로 나눈 뒤 각 문제의 답을 재귀적으로 계산하고, 각 문제의 답으로부터 전체 문제의 답을 계산한다. 문제를 더 이상 나눠지지 않는 매우 작은 단위 (기저 사례) 까지 나누고 (Divide), 나눠서 해결한 문제의 답을 원래 문제의 답으로 합친다. (Merge) 수열의 빠른 합을 구하는 과정을 분할 정복으로 생각해보자. fastSum(n) 은 1 부터 n (자연수) 까지의 합을 구하는 함수이다. 먼저, n 까지의 합을 구하는 과정을 거의 같은 크기의 부분 문제로 나눈다. n 까지의 합을 구하는 과정을 절반으로 나누었다. fastSum(n) = 1 + 2 + ... + n = (1 + 2 +..
[iOS] Architecture patterns(MVC,MVP,MVVM) 1.설계를 생각해야 하는 이유. -큰 규모의 소프트웨어를 제작할때, 설계 구조를 생각하지 않으면 관리가 어렵다.(버그를 찾기 힘들다..) → 즉, 소프트웨어를 이해하기 좋고, 분리되어 있어 테스트가 용이하며, 각각을 재사용할 가능성이 생긴다. 2.좋은 설계란? -기능의 책임이 균형있게 분산된 설계. -테스트가 용이한 설계. -사용이 쉽고, 유지 비용이 적은 설계. 3.Model? View? Controller(Presenter,ViewModel)? -Model: data에 접근,수정하는 계층. Domain data에 대한 책임이 있다. -View: 표현 계층에 대한 책임.(ios 개발 시 'UI'로 시작하는 것들!) -Controller(Presenter,ViewModel): View와 Model 사이를..
[알고스팟] 여행하는 외판원 문제 - 완전 탐색, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 여행하는 외판원 문제(링크) 도시들과 도시들 사이의 거리가 주어지면 모든 도시를 한 번씩 방문한 뒤 출발지로 돌아오는 가장 짧은 순환을 구한다. 문제에 따라 출발한 도시로 돌아오지 않고 모든 도시를 한 번씩 방문하기만 하도록 요구할 수도 있다. 이 경우는 최소 가중치 합의 해밀턴 경로를 구하는 것이라 할 수 있다. 최적화 문제 이전의 문제들은 하나의 답을 찾지만 외판원 문제와 같은 경우 여러 개의 답 중 어떤 기준에 따라 가장 좋은 답을 찾아내는 최적화 문제이다. 이런 특성에 따라 이전 재귀 함수의 형태와 다른 점들에 유의하자. 반환해야 하는 값이 문제에서 정한 기준에 따라 다르므로 단순히 대입이나 합산으로 반환값을 결정하지 않는다. 재귀적으..
[알고스팟] 게임판 덮기 - 완전 탐색, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 게임판 덮기(링크) 빈 곳이 있는 게임판이 주어질 때 L 모양의 블럭을 한 개씩 덮어 모든 칸을 채우는 방법의 가짓수를 계산한다. 재귀적으로 생각하기 게임판에 L 모양의 블럭을 한 개 덮는 것을 하나의 작업 조각으로 생각한다. 재귀 함수는 빈 곳이 있는 게임판이 주어질 때 4 가지 모양의 L 블럭을 각각 덮을 수 있는지 검사해보는 작업을 반복한다. 중복으로 세는 문제 블록을 놓는 순서에 상관없이 같은 블록들로 덮었다면 한 가지 경우이다. 블록을 놓는 순서를 강제하면 놓는 순서에 따라 별개의 경우로 세는 문제를 막을 수 있다. 가장 왼쪽 위의 빈 칸부터 덮어 나가는 것으로 순서를 강제하자. 무식하게 풀 수 있을까? 빈 칸의 수는 50개를 넘지 ..
[알고스팟] 소풍 - 완전 탐색, 재귀 ※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장. 소풍(링크) 재귀적으로 생각하기 학생의 명단이 주어지면 둘 씩 짝 짓는 경우의 수를 계산한다. 두 학생을 짝 짓는 작업을 하나의 작업 조각으로 보면 재귀 함수는 아직 짝을 찾지 못한 학생의 명단이 주어질 때 두 학생을 짝 지어주는 작업을 반복한다. 중복으로 세는 문제 1번 3번을 짝 짓는 것과 3번 1번을 짝 짓는 것은 별개의 경우로 세면 안 된다. 이처럼 중복으로 세는 문제를 다루는 한가지 방법은 항상 특정 형태의 답만을 세는 것이다. (조합을 구할 때 동일한 원소들이 순서가 다르게 선택되어 별개의 경우가 되지 않도록 고르는 순서를 강제하는 것과 같다.) 무식하게 풀 수 있을까? 이 문제가 가장 많은 답을 가지는 입력은 열 명의 학생이 모두..

티스토리툴바