코드 낙서장

문제 주소 : 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..

문제 주소 : 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

문제 주소 : www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 문제 확인 스위핑과 우선순위 큐를 활용하는 문제입니다. 풀이 입력받은 선들을 x기준으로 내림차순 정렬을 한 후 우선순위 큐에 y 값을 내림차순으로 넣어 비교합니다. 비교식은 ary[i].x + dist que.pop() 이며 이러한 동작으로 인해 현재 이 조건을 만족하게 된다면 다음 단계에서 의미 없는 값이 되기 때문에..

문제 주소 : www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 문제 확인 그래프 탐색 문제입니다. BFS, 다익스트라 알고리즘으로 해결할 수 있습니다. 맵에서 도달할 수 있는 각 점을 하나의 버텍스로 잡으며 탐색한 후 기록된 값을 이용해 풀 수 있는 문제입니다. 풀이 죄수 2명과 상근이가 모두 움직이면서 한 점에서 만나는 경우 탈옥을 할 수 있다는 것을 이용합니다. 이 경우 한 점에서 만나는 특성상 정점에서의 각각 문을 연 최솟값이 다른 최솟값에게 영향을 미치지 않습니다..

문제 주소 : www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제 확인 간단한 시뮬레이션 문제입니다. 주어진 상황을 그대로 구현하면 됩니다. 풀이 톱니바퀴의 왼쪽과 오른쪽을 가리키는 인덱스를 저장시켜두고 방향 전환을 하면서 맞춰 기록해갑니다. 톱니바퀴가 회전할 때 서로 맞닿은 극에 따라 옆에있는 톱니바퀴의 회전이 결정됩니다. 회전 시 맞닿은 톱니의 극이 다르다면 옆의 톱니바퀴는 반대방향으로 회전하게 됩니다. 코드 1 2 3 4 5 6 7 8 9 10 ..