저번에 배웠던 버블, 선택 정렬은 비교와 교환에 기반한 정렬 방식이었고 카운팅 정렬은 비교환 방식이었다. 이번엔 분할 정복 알고리즘에 기반한 퀵 정렬과 합병 정렬에 대해서 알아보자. # 합병 정렬 컴퓨터에 관해 일을 한다면 꼭 알아야 되는 '존 폰 노이만'이 제안한 방법 일반적으로 구현 시 중복된 값을 입력 순서와 동일하게 정렬하는 '안정 정렬' 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법 과정 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 보고 그렇지 않다면 리스트를 절반으로 자른다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬하고 다시 하나의 정렬된 리스트로 합병 추가적인..

지난 시간의 배열도 그렇고 오늘 배울 정렬은 대체 어떤 것을 위해 배우는 것일까? 그걸 알기 위해 '인덱스'에 대해 조금 알아보고 가자. 인덱스 인덱스라는 용어는 데이터베이스에서 유래했으며, 테이블에 대한 동작 속도를 높여주는 자료 구조이다. Database 분야가 아닌 곳에서는 Look up table 등의 용어를 사용하기도 한다. 인덱스를 저장하는데 필요한 디스크 공간은 보통 테이블을 저장하는데 필요한 디스크 공간보다 작다. 왜냐하면 인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목들은 갖고 있지 않기 때문이다. 배열을 사용한 인덱스 대량의 데이터를 매번 정렬하면, 프로그램의 반응은 느려질 수 밖에 없다. 이러한 대량 데이터의 성능 저하 문제를 해결하기 위해 배열 인덱스를 사용 정렬 2개 이상..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net # 조건 자연수 N이 주어진다. 다음 줄에는 N개의 정수 A[1] ---- A[N]이 주어지고 다음 줄에는 M 그 다음 줄에는 M개의 수들이 주어지는데, M개의 수들이 A안에 존재한다면 1, 아니면 0 출력 # 접근 방법 처음엔 리스트로 받아서 contain method in을 이용하여 제출 시간초과가 나서 이분탐색으로 접근하였다. 정렬을 해준 후,..

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 10828 스택문제와 마찬가지로 Queue의 기본 기능을 구현하는 문제였다. # 조건 push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 ..

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net # 조건 push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 ..

DP 문제를 풀다보니 자주 등장하는 유형이 있어 구글링을 해보니 '최장 증가 부분 수열'이라는 유형이였다. # 최장 증가 부분 수열 (Longest Increasing Subsequence) DP 문제로 자주 나오는 유형 O(N^2)의 시간 복잡도 아니면 O(NlogN)의 시간 복잡도를 가진다. 어려운 문제의 경우 당연히 후자.. 개념 단어 그대로 가장 긴 증가하는 부분 수열을 구하는 것 어떤 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 '오름 차순을 유지하면 증가하는 부분 수열' 즉, 만들 수 있는 부분 수열 중 가장 길면서 오름차순을 유지하는 수열이 LIS 위의 여러 수열 중 가장 길이가 긴 수열은 [2,3,5,6,7] 뿐만 아니라 [1..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net # 조건 - 트리에서 리프노드란, 자식의 개수가 0인 노드 - 트리가 주어질 때, 노드 하나를 지울 것인데, 그 때 남은 트리에서 리프 노드의 개수를 구하여라 # 접근 방법 - 노드 하나를 지웠다면 아래 자식 노드들 또한 함께 지워지는 것이 규칙 - 따라서 지워지는 노드 기준, 아래로 연결되어 있는 노드들을 -2로 변경해준다. - -2인 경우는 나올 수 없는 수 이기도 하며 False로 설정..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net # 조건 - 토마토를 보관하는 창고가 있는데 익힌 토마토는 1, 비어있는 경우 -1, 그냥 토마토는 0으로 표시 - 익힌 토마토의 좌우상하 토마토는 다음날 익어있다. - 이 때, 모든 토마토를 다 익히는 경우, 최소 일 수를 구하여라 - 만약, 익히지 못한다면 -1 출력 # 접근 방법 - 좌우상하 탐색이 필요하므로 델타 함수를 이용하여 접근해준다. - 또한 바로 내 주변에 토마토가..

https://www.acmicpc.net/problem/1325 B 컴퓨터를 신뢰하는 관계라면, B 컴퓨터만 해킹하여도 A는 자동으로 해킹된다. 이 때, 한 컴퓨터를 해킹해서 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터 번호를 출력하여라! 여러 대가 있다면, 오름차순 출력 # 접근 방법 자식 노드만 확인하는 것이 아닌 그 컴퓨터를 '신뢰하는' 또 다른 컴퓨터까지 확인해 주어야한다. 따라서 BFS를 확인하여 각 컴퓨터마다 해킹가능한 컴퓨터 수를 기록해주고 가장 많이 해킹하는 컴퓨터를 출력한다. BFS 기본 예제 문제와 비슷해보이지만, 1번이 아닌 모든 컴퓨터를 체킹한다는 것이 다르다. 그러다보니 많은 메모리, 시간을 사용하게 되고 PyPy로 제출하지 않는 이상 통과가 힘들었다.. ```python # N개..