종식당

병합 정렬 주어진 배열을 더 이상 쪼갤 수 없을 때까지 데이터 크기의 절반으로 계속 나누어, 재귀적으로 정렬을 수행하면서 통합하는 정렬 알고리즘 이 알고리즘 총 3단계로 나눌 수 있다. Divide 주어진 배열을 데이터 크기의 절반으로 나누어 2개의 부분 배열로 분할한다. 이를 더 이상 쪼갤 수 없을 때까지 분할한다. Conquer 나누어진 부분 배열에 대해서 재귀적으로 합병 정렬을 한다. Combine 정렬한 2개의 부분 배열을 통합하여 원래 크기의 정렬된 배열로 만든다. Merge sort의 슈도 코드 Merge sort의 수행 과정 Merge sort의 시간 복잡도 먼저 전체 리스트를 반으로 나누어 가면서 리스트를 분할한다. 만약 길이가 8인 리스트라면 이를 총 3번 나눌 것이고, 길이가 16인 리..

프로세스란? 프로세스는 현재 실행 중인 프로그램이라고 할 수 있다. 프로그램은 디스크에 저장되어 있는 실행 가능한 것이다. 컴퓨터는 CPU를 통해 프로그램을 메모리에 load 하고 이를 처리한다. 보통 우리는 컴퓨터를 통해 여러가지 프로세스를 동시에 이용하지 한 대의 컴퓨터로 하나의 프로세스만을 실행시키지는 않는다. 그럼 여러 개의 프로세스를 동시에 동작하는 방법에 대해서 알아보겠다. Multiple processes OS는 여러개의 프로그램을 동시에 실행시키기 위해 CPU를 가상화하는 방법을 이용한다. 이를 Virtualization이라고 부른다. 실제로 물리적인 CPU는 1개이지만 이를 프로그램들에게는 여러 개의 CPU가 있는 것처럼 가상화시켜 여러 개의 프로그램을 동시에 실행시킬 수 있게 됩니다. ..

삽입 정렬 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 어떠한 리스트가 있다고 가정했을 때 두 번째 위치의 값부터 정렬을 시작할 것이다. 이를 key값이라고 부를것이다. 해당 key값의 앞에 있는 데이터부터 비교하여 key값이 더 작다면, 데이터를 key값 뒤 인덱스로 복사 이를 key값이 더 큰 데이터를 만날 때까지 반복 큰 데이터를 만난 위치 바로 뒤에 key값을 이동 말로 풀어쓰면 정확하게 이해가 되지 않아 이를 그림을 보며 설명하겠다. 위 사진을 참고하면 먼저 리스트의 두 번째 값을 key값으로 정하고 이를 이전의 값과 크기를 비교하며 정렬해 주는 모습을 확인할 수 있다. 정렬이 완료되면 key값을 ..

문제 설명 N을 입력받고 2xN 크기의 바닥을 위 3가지 종류의 덮개로 채워야 할 때의 경우의 수를 출력하면 된다. 위를 참고하여 점화식을 유도해낸다음 코드에 적용시키면 된다. 문제 코드 N = int(input()) dp = [0]*(N+1) dp[1] = 1 #2x1 짜리 하나 총 1가지 dp[2] = 3 #2x1 짜리 두개,1x2 짜리 두개, 2x2 짜리 하나 총 3가지 for i in range(3,N+1): dp[i] = (dp[i-1] + 2*dp[i-2]) % 796796 print(dp[N]) 점화식만 문제를 보고 뽑을 줄 알고 초기 설정만 잘해주면 어렵지 않게 dp문제를 풀 수 있을 것 같다. 관련 문제 https://www.acmicpc.net/problem/11726 11726번: 2..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 설명 m과 n 두 수를 입력받고 두 수 사이의 소수를 모두 출력하면 되는 간단한 문제이다. 시간초과 제출 코드 m, n = map(int,input().split()) for i in range(m,n+1): k = 2 cnt = 0 while k