Total

가장 높은 탑 쌓기

분석 최대 부분 증가수열 분석 [12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 karla.tistory.com 풀이 """ 밑면이 정사각형인 직육면체 벽돌들을 사용하여 탑을 쌓고자 한다. 탑은 벽돌을 한 개씩 아래 에서 위로 쌓으면서 만들어 간다. 아래의 조건을 만족하면서 가장 높은 탑을 쌓을 수 있는 프 로그램을 작성하시오. (조건1) 벽돌은 회전시킬 수 없다. 즉, 옆면을 밑면으로 사용할 수 없다. (조건2) 밑면의 넓이가 같은 벽돌은 없으며, 또한 무게가 같은 벽돌도 없다. (조건3) 벽돌들의 높이는 같을 ..

최대 부분 증가수열

분석 [12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net LIS Longest Increasing karla.tistory.com [14003번] 가장 긴 증가하는 부분 수열5 (LIS, 이분탐색) 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,..

[2579] 계단오르기

2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net """ 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다. 각 계..

계단오르기 (Top-Down : 메모이제이션)

분석 0: return d[len] if len == 1 or len == 2: return len else: d[len] = dfs(len-1) + dfs(len-2) return d[len] print(dfs(n))

돌다리 건너기(Bottom-Up)

분석 개울을 완전히 건너려면 n번째 돌에 도착하는 것이 아니라 n번째 돌 다음에 나오는 땅에 도착해야 함 ⇢ n+2 풀이 """ 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철 수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지 """ n=int(input()) d=[0]*(n+2) d[1]=1 d[2]=2 for i in range(3, n+2): d[i]=d[i-1]+d[i-2] print(d[n+1])

네트워크 선자르기 (Bottom-Up, Top-Down)

bottom up """ 현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면 5가지 방법을 생각할 수 있습니다 1) 1m+1m+1m+1m 2) 2m+1m+1m 3) 1m+2m+1m 4) 1m+1m+2m 5) 2m+2m 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법? 첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다. """ # Bottom-Up n=int(input()) d=[0]*(n+1) d[1]=1 d[2]=2 for i in range(3,n+1): d[i]=d[i-1]+d[i-2] print(d) print(d[n]) top down n=int(input()) d=[0]*(n+1) d[1]=1 d[2]..

[Memory] segmentation

Segmentation이란? Segmentation은 Paging과 달리 프로세스가 할당 받은 메모리 공간을 논리적 의미 단위인 Segment로 나눠서 연속되지 않은 물리 메모리 공간에 할당될 수 있도록 하는 메모리 관리 기법이다. Paging 기법은 사전에 미리 메모리를 나누어 두는 기법이라고 한다면 Segementation은 프로세스가 할당 받은 메모리 공간 만큼 메모리를 나누어 주는 기법이라고 보면 된다. 즉, 프로세스가 필요로 하는 메모리 작업 공간 만큼의 크기를 제공한다. 맞춤형 이라고 보면 된다. Segmentation은 코드, 데이터, 힙, 스택 등의 기능 단위로 segment(단위)를 정의하는 경우가 많으며 주소 바인딩을 위해 모든 프로세스가 각각의 주소 변환을 위한 segment tabl..

[Memory] paging (메모리 관리 기법, 메모리 단편화)

페이징 설명에 필요한 용어 논리적 주소, Logical Address : 프로세스가 메모리에 적재되기 생성되는 독자적인 주소 공간이다. 논리적 주소는 각 프로세스마다 독립적으로 0번째 주소부터 할당이 된다. 물리적 주소, Physical Address : 실제로 메모리에 적재되는 위치 주소를 말한다. 주소 바인딩, Address Binding : CPU가 기계어 명령을 수행하기 위해 프로세스의 논리적 주소가 실제 물리적 메모리의 어느 위치에 매핑되는지 확인하는 과정을 말한다. Paging이란? 프로세스가 할당 받은 메모리 공간을 일정한 크기의 페이지 단위로 나눠 물리 메모리에서 연속되지 않는 서로 다른 위치에 저장하는 메모리 관리 방법이다. 먼저, 논리적 메모리 상으로는 붙어서 저장이 되어 있다고 하지..

[Process & Thread] 교착상태(Deadlock)

1. 교착 상태 두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 중단된 상태, 둘 이상의 스레드가 다른 스레드가 점유하고 있는 자원을 서로 기다릴때 무한대기에 빠지는 상황입니다.스레드일수도 있고 프로세스일 수도 있습니다. 2. 교착상태의 원인 (4가지 모두 성립) 상호 배제 : 한 프로세스가 자원을 독점하고 있으며 다른 프로세스들은 접근 불가능 점유 대기 : 특정 프로세스가 점유한 자원을 다른 프로세스가 요청하는 상태 비선점 : 다른 프로세스가 점유중인 프로세스의 자원을 강제로 선점 불가 순환 대기: 대기중인 프로세스들이 사이클을 이룸, 서로가 서로의 자원을 요구하는 상황 3. 해결방법 4가지 1) 무시 : 아무조치 안함 2) 예방 : 4가지중 하나가 성립되지 않도록 미리 예방. 비용이 커서 비추..

[Process & Thread] Multi Process, Multi Thread 동기화 (Mutex, Semaphore)

1. 임계영역 임계영역은 둘 이상의 프로세스나 쓰레드가 동시에 동일한 자원에 접근하게 되는 프로그램 코드 부분을 의미하는데 각 프로세스나 쓰레드가 임계구역에서 일을 수행하는 동안 다른 프로세스나 쓰레드가 그 임계영역에 들어갈 수 없어야 한다. 즉, 임계영역 내의 코드는 원자적 실행이 되야 하는 것이다. 이렇듯, 원자적으로 실행되기 위해 임계영역으로 들어갈 때 entry section을 통해 진입 허가를 요청하게 되고 허가 요청이 수락되면 임계영역을 실행하게 된다. 임계영역에서 수행이 끝나면 exit section으로 퇴출하게 된다. 임계영역의 원자성을 보장함으로써 프로세스나 쓰레드들이 동기화 되도록 할 수 있고 이러한 방법 중 대표적인 방법이 뮤텍스와 세마포어인 것이다. 2. 동기화 멀티 쓰레드인 경우 ..