코드 낙서장

문제 주소 : www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 문제 확인 위상 정렬 문제입니다. 위상 정렬이란 간단하게 말해서 사이클이 없는 방향 그래프에서 방향을 한쪽으로 몰아세우는 정렬 방법입니다. 자세한 설명은 다음 블로그에서 잘 해두었습니다. Topological Sort(위상 정렬) DAG에서 방향성을 거스르지 않게 정점들을 나열하는 알고리즘을 Topological sort(위상 정렬)이라 합니다. DAG란 Direc..

스케줄링 스케줄링은 보통 멀티프로그래밍을 가능하게 하는 운영 체제의 동작 기법이며 어느 프로세스를 CPU에 얼마큼 할당할지를 결정하는 기법입니다. CPU 외에 자원을 할당할 때 스케줄링 작업을 거치기도 합니다. 스케줄링 용어 멀티프로그래밍 : CPU의 활용 극대화, 많은 프로그램이 동시에 실행 시간 공유 : 프로세스들이 자원을 공유 프로세스 스케줄링 : CPU에서 실행될 프로세스를 선택 Job Queue : 실행할 프로세스들의 PCB들의 모임 Ready Qeueu : 실행을 위해 모든 준비가 완료된 프로세스들의 PCB 모임 Device Qeueu(=waiting queue) : 자원을 사용 중이거나 사용하기 위해 기다리는 프로세스들의 모임, 각 장치들이 각자 고유의 큐를 가짐 스케줄링의 종류 장기 스케줄..

문제 주소 : www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제 확인 특별한 알고리즘이 필요 없는 스택을 이용한 구현 문제입니다. 풀이 입력받은 직사각형의 높이와 i 값을 스택에 쌓으면서 기록합니다. 다음 나오는 직사각형의 높이에 따라 다음과 같이 동작합니다. 다음 직사각형의 높이에 높다면 계속해서 스택을 쌓아갑니다. 높이가 같은 경우 시작 지점인 i값을 기록해 두었으므로 스택에 넣을 필요가 없습니..

문제 주소 : www.acmicpc.net/problem/16287 16287번: Parcel 입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가 www.acmicpc.net 문제 확인 dp 문제입니다. dp를 사용하지 않고 4중 포문으로 풀면 n이 5000이기 때문에 시간 초과가 납니다. 따라서 문제를 i + j, w - (i + j) 두 파트로 나누어 문제를 풀어야 합니다. 풀이 무게를 인덱스로 활용해 만들 수 있는 무게를 기록합니다. 각 원소의 최대 크기는 200000으로 dp[400000]을 사용합니다. 2중 포문..

문제 주소 : www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 확인 dp로 풀어도 되지만 a를 둔 후 z를 분배하는 식으로 중복 조합을 이용해 풀 수 있습니다. 풀이 a를 두고 z를 분배하는 식으로 점화식을 짜봅니다. 예를 들어 a : 3, z : 4 일 경우 _a_a_a_ 로 두고 z를 분배할 수 있는 공간은 4칸이 됩니다. 따라서 총경우의 수는 a+1 H z로 35가지가 나옵니다. 문제의 조건에 따라 k가 35 보다 높은 경우 -1을 출력해 예외처리를 해 줍니다. z를 분배하는 식은 z의 개수에 ..

문제 주소 : www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제 확인 정렬 후 최선의 선택을 하는 Greedy 알고리즘으로는 예외가 있는 문제를 해결할 수 없습니다. memory : 30 10 50 cost : 2 3 4 위와 같은 경우 확보해야 할 메모리가 40인 경우 cost가 적은 2개를 선택하게 되면 잘못된 답이 될 수 있습니다. 따라서 dp로 풀어야 합니다. 풀이 cost의 크기가 작기 때문에 인덱스로 활용할 수 있어 사용할 앱 : i, cost : j..

문제 주소 : www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 확인 숫자 처리 구현 문제입니다. 주의해야 할 점은 첫 시작 페이지가 1이며 n자릿수 수에 재일 앞자리 수는 0이 될 수 없습니다. 풀이 현재 자리수의 숫자 기준으로 경우의 수를 나눌 수 있습니다. 예를 들어 1234라는 수가 있을 때 첫자리부터 경우의 수를 생각해 봅시다. XXX0 의 경우 0000은 없는 페이지 이므로 XXX에 001~123 까지 총 123의 경우의 수가 있습니다. XXX1 ~ XXX4 까지의 경우 XXX 자리에 000~123 까지 총 1..

Context Switch Context란 CPU가 해당 프로세스를 실행하기 위한 정보로 지난 시간에 배운 PCB에 저장되어 있는 프로세스의 상태 정보를 의미합니다. 우리가 사용하는 컴퓨터에서 여러가지 프로그램을 동시에 동작할 수 있도록 만들어 주기 위해 현재 Context를 저장해 두고 다른 프로세스의 Context를 불러와 실행시켜 마치 실시간으로 여러 개의 프로그램이 동작하는 것처럼 보여줍니다. 이러한 일련의 과정을 Context Switch로 부릅니다. 보통 프로세스에 주어진 CPU 시간이 다 되거나 입출력 등을 위해 스스로 인터럽트를 발생, 우선순위가 높은 프로세스가 CPU를 점유하기 위해 인터럽트 요청을 했을 경우 발생합니다. Context Switch의 과정 프로세스 상태 변화에서 ready..

문제 주소 : programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 문제 확인 투포인터 문제입니다. 트라이를 활용해서 풀 수 있지만 최악의 경우 100000개의 보석의 이름 모두 10글자이며 중복이 없고 각 단어가 하위 트라이를 계속해서 만드는 경우 메모리 사용량이 너무 커질 수 있습니다. ex) "abcdefghij", "bcdefghijk", ... "aabcdefghi" .. 풀이 2가지 풀이법이 있습니다. 배열을 탐색해서 미리 보석의 종류를 map에 기록해둔 후 투포인터..

문제 주소 : www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 문제 확인 bit dp 문제입니다. 입력받는 숫자의 개수가 15개 이므로 bit 형으로 표현할 수 있으며 나머지 값인 k 또한 100보다 작은 수 이므로 dp[1