Programming/알고리즘 (13) 썸네일형 리스트형 [merge sort] 머지소트 개념 및 구현 merge sort 개념 퀵소트처럼 대표적인 divide & conquer 알고리즘 중 하나. merge sort는 퀵소트와 비교했을 때, 안정적으로 nlogn의 시간복잡도를 내는 알고리즘이다. 퀵소트, 힙정렬에 비해서 메모리사용량이 더 많다. 평균적으로는 퀵소트보다 더 오래걸린다. 따라서 특수한 케이스가 아니라면 머지소트보다는 퀵소트를 더 많이 사용한다. 머지소트개념은 나누어서 정리해서 합친다는 개념이다. 여기서는 더 이상의 개념설명은 하지 않겠다. merge sort 구현 머지소트를 구현함에 있어서 나는 두가지 방법으로 접근했다.(결과는 같다) 1. 직관적, 순차적인 접근 : divide를 최소단위가 될 때 까지 시행하고서 conquer하는 접근 2. 재귀적인 접근 : divide를 해서 두 개의 p.. [퀵소트 구현] 퀵소트 구현, 최악의 케이스 직접 확인 퀵소트는 평균 시간복잡도가 nlogn인 알고리즘이지만 최악의 경우의는 n^2 의 시간복잡도를 가진다고 한다. 최악의 케이스를 가지는 경우는 배열이 이미 정렬되어있는 경우이다. 이 때, 배열이 오름차순으로 정렬되어있든, 내림차순으로 정렬되어있든 상관없다. 마찬가지로 배열이 모두 같은 값을 가진다고 해도 적용이 된다. 만약 모두 10이라는 값을 가지고 있는 배열도 이미 정렬되어있는 배열이나 마찬가지이기 때문이다. 1. 시간복잡도 계산법 간단하게 생각해서 n개의 데이터에 대해 divde&conquer를 몇번 수행하느냐만 알면 된다. 평균적으로 divide&conquer가 log(n)번 수행되기 때문에 퀵소트의 평균 시간복잡도가 nlog(n)인 것이다. 그런데 최악의 경우에는 divide&conquer가 log.. [백준 경로찾기] DFS 문제, 2차원 벡터 활용 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 경로찾기 문제로 문제를 푸는 알고리즘은 다음과 같다. 1) q.pop() 나온 노드를 현재노드로 지정 2) 현재노드에서 주변노드에 방문 안했으면 방문처리후, q.push() 이 문제는 매우 간단하나 시간초과를 막기위해 문제를 풀기위한 시스템을 마련하는 방법이 중요하다. 현재노드에서 주변노드를 탐색할 때, for문으로 주변 노드를 모두 다 확인하면서 연결되있는 여부를 검사한다면 노드가 100개존재할 때, 요구되는 시간이 매우 많아질것이다. .. [다익스트라] 개념 정리 다익스트라 알고리즘은 그래프로된 맵에서 최소 경로를 찾는 가장 유명한 알고리즘중 하나이다. 간단한 의사코드를 적어놓는다. while( 방문 안한 노드가 있을 때) { 방문 안한 노드중 최소경로비용 노드 방문 방문 한 노드에서 주변 Link보고 경로 업데이트 } 0 10 3 - - 0 1 2 3 4 위 그래프와 의사코드를 보고 표를 완성해보자. [백준 ACM craft] 위상정렬 문제 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D가 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건 www.acmicpc.net ACM craft라고 starcraft 문제를 비유한 듯한 문제다. 위상정렬문제이지만 단순 위상정렬문제가 아니라 각각의 건물이 지어.. [백준 A/B] double 출력 자릿수 문제 https://www.acmicpc.net/problem/1008 1008번: A/B 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 브론즈 문제이지만 이런 문제일 수록 어이없게 틀릴 수가 있다. 문제 조건에는 "실제 정답과 출력값의 절대오차 또는 상대오차가 10-9 이하이면 정답이다." 라는 말이 있다. 즉, 정답과 상관없이 출력되는 값이 10의-9승 까지는 나오는 것이 오차를 줄일 수 있는 방법이다. 문제는 매우 단순하지만 문제의 정답처리 방식때문에 다음과 같이 소스코드를 작성하면 오답이나온다. #include using namespace std; int main() { double a, b,c; scanf("%lf %lf", &a, &b); .. [백준 알파벳] DFS, BackTracking 문제 https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net 배운점 1. 중복검사는 visited[i]로 하고, backtraking 해서 올라올 때, visited가 제대로 업데이트 되는지 확인. 2.. [백준 N과 M(1)] 백트래킹 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 배운점 : 1. BackTracking 문제는 깊어진 depth 에서 다시 빠져나올 때도 생각해야한다. 2. 중복검사는 visited[i]로 하는게 빠르다. ( 다이나믹 프로그래밍) for문으로 일일이 중복되는지 확인하지 말자. 3. 코딩하면서 변수가 코드로써 뭘 의미하는지도 적어놓고 하면 생각이 편하다. ex) depth는 tree의 깊이(개념)이자 arr의 인덱스 역할(코드로써의 의.. 이전 1 2 다음
