prefer2 Log

문제 스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하며, 엄지손가락을 사용하는 규칙은 다음과 같습니다. 엄지손가락은 상하좌우 4가지 방향으로만 이동할 수 있으며 키패드 이동 한 칸은 거리로 1에 해당합니다. 왼쪽 열의 3개의 숫자 1, 4, 7을 입력할 때는 왼손 엄지손가락을 사용합니다. 오른쪽 열의 3개의 숫자 3, 6, 9를 입력할 때는 오른손 엄지손가락을 사용합니다. 가운데 열의 4개의 숫자 2, 5, 8, 0을 입력할 때는 두 엄지손가락의 현재 키패드의 위치에서 더 가까운 엄지손가락을 사용합니다. 4-1...

문제 현재 N개의 앱, \(A_1\), ..., \(A_N\)이 활성화 되어 있다고 가정하자. 이들 앱 \(A_i\)는 각각 \(m_i\) 바이트만큼의 메모리를 사용하고 있다. 또한, 앱 \(A_i\)를 비활성화한 후에 다시 실행하고자 할 경우, 추가적으로 들어가는 비용(시간 등)을 수치화 한 것을 \(c_i\) 라고 하자. 이러한 상황에서 사용자가 새로운 앱 B를 실행하고자 하여, 추가로 M 바이트의 메모리가 필요하다고 하자. 즉, 현재 활성화 되어 있는 앱 \(A_1\), ..., \(A_N\) 중에서 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 추가로 확보해야 하는 것이다. 여러분은 그 중에서 비활성화 했을 경우의 비용 \(c_i\)의 합을 최소화하여 필요한 메모리 M 바이트를 확보하는 방법을..

문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오. 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제조건 1 ≤ N, K ≤ 300,000 0 ≤..

문제 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다. 그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의..

문제 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다. 낚시왕이 오른쪽으로 한 칸 이동한다. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다. 상어가 이동한다. 상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는..

문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다. 예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으..

문제 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자. S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다. S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다. S = 3, E = 3인 경우 1은 팰린드롬이다. S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다. 자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오...

그래프 자료구조의 일종 정점(Node, Vertex)과 간선(Edge)로 이루어져 있음 G = (V, E)로 나타낸다 차수(Degree): 정점과 연결되어 있는 간선의 개수 방향 그래프이 경우에는 In-degree, Out-degree로 나누어서 차수를 계산한다 그래프의 표현 인접 행렬 정점의 개수를 V라고 했을 때 V*V 크기의 이차원 배열을 이용 A[i][j] =1 (i→j 간선이 있을 때, 가중치가 있을 경우 가중치), 0 (없을 때) 공간 복잡도: O(\(V^2\)) 인접 리스트 A[i] : i와 연결된 정정을 리스트로 포함 리스트의 크기는 동적으로 변경할 수 있어야(원칙적으로는 링크드 리스트, c++에서는 vector 사용) 공간 복잡도: O(E) 대체적으로 인접 리스트가 효율적 그래프의 탐색 ..

다이나믹 프로그래밍(동적 계획법) 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 DP → 중복⭕ 분할정복(Divid & Conquer) → 중복❌ 정답을 한 번 구했으면, 정답을 어딘가에 메모해놓는다(memorization) Overlapping Subproblem(중복되는 부분 문제): 문제를 작은 문제로 쪼갤 수 있다. 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다 Optimal Substructure(최적 부분 구조): 문제의 정답을 작은 문제의 정답에서 구할 수 있다 int memo[100]; int fibonacci(int n){ if( n 0){ return memo[n]; } memo[n] =fibonacci(n-1) + fibonaccai(n-2); return memo[n]; } } /..

나머지 연산 (A+B) mod M = ((A mod M) + (B mod M)) mod M (A*B) mod M = ((A mod M) * (B mod M)) mod M (A-B) mod M = ((A mod M) - (B mod M) +M) mod M (음수가 나올 수 있기 때문에) 나눗셈의 경우는 성립하지 않는다 최대 공약수(GCD) 유클리드 호제법(Euclidean algorithm) a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a, b) == GCD(b, r) //재귀함수 사용 int gcd(int a, int b){ if( b == 0){ return a; } else { return gcd(b, a%b); } } //재귀함수를 사용하지 않고 int gcd(int a, int b){ wh..