hail2y.log

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다.  다익스트라(Dijkstra) 알고리즘출발 노드와 모든 노드 간의 최단 거리 탐색 (출발 노드와 도착 노드, 두 노드만이 아님)에지(가중치)는 모두 양수여야 한다시간 복잡도는 O(E * logV)그리디 알고리즘- 접근 방법그래프를 인접 행렬, 인접 리스트로 구현할 수 있지만 일반적인 경우에서 인접 리스트가 더 빠름, 하지만 상황에 따라 달라짐- 인접 행렬 O(V^2) - 밀집 그래프에 유리, 연결 노드 확인하는 데 O(1)- 인접 리스트 O(E * log V) - 희소 그래프에 유리, 연결 노드 확인하는 데 O(연결된 간선의 수)최단 거리 배열을 초기화 (최댓값으로 모두 채우기)거리 배열에 출발 노드 인덱스에 0..

(학교 수업 자료를 참고하여 작성하였습니다.) DFS, BFS는 탐색 알고리즘으로 브루트포스에 포함된다. 주로 그래프와 트리를 순회할 때 사용되고, 탐색 방법과 목적에는 약간의 차이가 있다. 그치만 코딩테스트 문제들에서 DFS, BFS를 따지지 않고 탐색만 하는 것으로 해결되는 경우도 많다고 한다. 그래프: 연결되어 있는 객체 간의 관계를 표현하는 자료구조트리: 그래프의 한 종류로, 사이클이 없는 N개 노드, (N-1)개 간선을 가진 연결된 그래프그래프는 인접 행렬(O(N^2)), 인접 리스트(O(N+E)) 형태로 구현한다. 깊이 우선 탐색, DFSDFS: Depth-First Search의 약자로 깊이 우선 탐색을 말한다한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림..

책 [Do it! 알고리즘 코딩 테스트 - 자바 편;김종관 지음]을 참고하여 작성하였습니다.  분할 정복(divide and conquer) 방식: 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘가장 작은 데이터 집합(크기 1)으로 나눈 후 2개의 그룹을 합치면서 정렬2개의 그룹을 합칠 때는 투 포인터를 이용하여 둘 중 더 작은 수를 결과 배열에 먼저 저장그런 다음 포인터를 1씩 증가시키는데, 어느 한 포인터가 배열의 끝에 먼저 도달하면 나머지 배열의 값들도 옮겨 붙임   시간 복잡도는 평균 O(nlogN)- 크게 보면 row 하나 당 n번의 데이터 접근- 병합 과정에서 logN번만큼 정렬버블 정렬(swap)과 연관지은 핵심 아이디어- 버블 정렬에서는 swap이 몇 번 일어날까- 첫째 줄에서 5..

책 [파이썬으로 쉽게 풀어쓴 자료구조; 최영규, 천인국 지음]을 참고하여 작성하였습니다.  QuickSort; 퀵 정렬평균적으로 매우 빠른 수행 속도병합 정렬과 같이 분할-정복법 사용하지만 병합 정렬과는 다르게 균등 분할할 필요 없다리스트 안의 한 요소를 피벗(pivot), 즉 기준점으로 삼고 이 값을 기준으로 작은 숫자는 왼쪽으로, 큰 숫자는 오른쪽으로 옮긴다(오름차순일 경우)그런 다음 순환 호출하여 부분 리스트들을 정렬한다불안정정렬, 별도의 메모리 공간 필요하지 않는다cf. 안정성: 입력 데이터에 동일한 킷값을 갖는 레코드가 여러 개 존재할 경우 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 것- 시간 복잡도최선의 경우: 리스트 분할이 가운데에서 이루어져 k번(log_2 n)의 분할 * 평균 n번의..

조합 (Combination)서로 다른 n개의 수 중 순서를 생각하지 않고 r개를 선택; nCr로 표현그에 반해 순열 nPr은 순서를 고려조합의 성질이항계수와 파스칼의 삼각형과 관련이항계수: 이항정리에서 각 항의 계수인 조합 nCr → 쉽게 말해, 이항정리에서는 각 항의 계수가 조합으로 나타난다.이항정리: 두 항의 합의 거듭제곱인 (a+b)^n을 전개한 결과를 정리한 것파스칼의 삼각형: 이항계수들을 삼각형 피라미드 형태로 배열한 것  이를 토대로 코드를 짜면 다음과 같다. 아래쪽에 combi() 함수를 보면 위 성질을 적용하여 재귀 호출한 것을 알 수 있다. import java.util.Scanner;public class Combination { public static void main(Str..

int ans = 0;while(left  1보다 mid까지의 합이 S 값보다 크지 않으면서 가장 큰 mid의 값을 찾는 과정 등차수열의 합 공식((첫항 + 마지막항) / 2) * 개수는 즉, mid * 개수인데, 여기에서처럼 1부터 mid까지는 개수가 (mid+1)이 되어 (mid*(mid+1))/2로 표현된다. 공식으로 접근할 생각을 못 했어서 저런 수식이 있길래 한참을 들여다 봤는데 등차수열의 합이었다. 어이는 없었지만 덕분에 1~mid의 합을 이진 탐색으로도 생각해 볼 수 있어서 좋았다. 그리고 아래는 똑같이 등차수열의 합 공식을 다루지만 접근법이 새로워서 한번 참고해 보면 좋을 것 같다. 수들을 도형으로 표현해 넓이 구하는 공식으로 구하였다. 결론적으로는 이 공식으로 귀결된다.   [참고: h..

브루트(brute); 무식한, 야만적인, 맹목적인 + 포스(force); 힘=> 발생할 수 있는 모든 경우를 다 따지며 해를 찾는다 = 완전 탐색 (ex. 비밀번호를 4자리로 설정한다고 할 때, 0000~9999를 다 탐색하여 암호를 해독한다.)사용하는 경우- 문제의 입력 크기가 작을 때 신속하게 결과 얻을 수 있다.- 최적해를 찾을 때 모든 경우를 다 따져보므로 정확도는 굿(but 경우의 수가 너무 많을 경우 실행시간이 너무 오래 걸리거나 메모리 효율 면에서 매우 비효율적일 수 있다.)- 문제의 구조가 간단하고 직관적일 때 유용하다. 다시 정리하자면,완전탐색의 장단점장점 - 알고리즘을 구현하는 것이 상대적으로 쉽다.- 복잡한 알고리즘 없이 빠르게 구현이 가능하다.단점- 알고리즘의 실행시간이 상대적으로 ..