복습노트 복습노트

문제 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 두개의 문자열이 주어지면 공통 부분 문자열이 가장 긴 길이를 출력하면 되는 문제입니다. 예를 들어 ABRACADABRA ECADADABRBCRDARA 두개의 문자열이 주어지면 가장 긴 공통 부분 문자열은 ABRACADABRA ECADADABRBCRDARA 이므로 5를 출력해주면 됩니다. 해당 문제는 최장 공통 부분 수열(Longest Common Subsequence)문제입니다. 하지만 다른 점은 기본적인 lcs는 굳이 문자열이 연속 되지 않아도..

문제 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 현재 사용하고 있는 n개의 메모리 공간과 메모리 제거 비용이 주어지고, 최소 필요한 메모리 공간인 m이 주어지면 n개의 메모리에서 m만큼 제거하면서 최소 비용이 나오게끔 하는 문제입니다. 예를 들어 n = 5이고 n개의 메모리 공간은 {30, 10, 20, 35, 40} 이고, 각각의 메모리 제거 비용은 {3, 0, 3, 5, 4} 라고 하고 m = 60이라 하면, n개의 메모리 중 {30, 10, 20}을 제거하면 제거 비용은 {3, 0, 3} 이므로 총 6이 ..

문제 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 건물의 갯수인 n이 주어지고, n개의 줄만큼 1~n 번 건물의 정보가 주어집니다. 건물의 정보는 [건물을 짓는 시간, 건물을 짓기 위해 먼저 지엉야하는 건물 번호, -1] 이렇게 주어집니다. -1이 나오면 정보가 다 주어졌다는 의미입니다. 각 건물을 짓기 위해 최소 시간을 구하는 문제입니다. 각 건물은 먼저 지어져야 하는 건물이 존재합니다. 물론 없는것도 있습니다. 따라서 이러한 정보를 바탕으로 위상정렬을 사용할 수 있습니다. 또한 "최소 시간"..

문제 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net n명의 사람을 입력받고 m개의 키 순서 정보가 주어집니다. 예를 들어 1 2가 주어지면 1번 보다 2번이 크다는 의미입니다. 키가 작은 순서대로 n명의 사람을 출력하면 됩니다. 만약 키가 비교할 수 없다면 아무거나 출력해주면 됩니다. 위 문제는 위상정렬의 기본형 문제입니다. 위상정렬은 각 정점을 우선순위에 따라 배치한것입니다. 일반적으로 위상정렬의 결과는 유일하지 않습니다. 1번 정점이 진입 차수가 0이기 때문에 ..

문제 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net n개의 노드가 주어지고, m개의 노드 간선 정보가 주어집니다. 간선 정보는 a, b, c 형태로 주어지고 a는 출발점, b는 도착점, c는 비용입니다. c는 음수도 가능합니다. 1번 노드에서 시작해서 2~n번 노드까지의 최소 비용을 차례대로 출력하면 되는 문제입니다. 만약 1번 노드에서 도달할 수 없는 노드는 -1을 출려하고, 최솟값을 정할 수 없으면 -1을 출력합니다. 비용이 음수이기 때문에 음의..

문제 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 내가 접근한 방식 : 투 포인터, 재귀함수로 구현한 트리 내가 놓친 부분 : 부배열(연속된 배열의 합) 나는 연속되지않은 배열의 합도 고려함 배열이 두개 주어지면 두 배열의 부배열(연속된 배열의 합)의 합이 t와 같은 개수를 구하면 되는 문제입니다. 배열의 크기가 최대 1000이므로 배열의 부배열들을 구하는데 1000 * 1000 = 1000000이므로 무난합니다. vector..

문제 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net n개의 사람과 m개의 키 순서가 주어지면 자신의 키 순서를 정확히 알 수 있는 사람의 수를 세는 문제 입니다. 예를 들어 입력이 3 4가 나오면 3번 사람이 4번 사람보다 작다는 의미입니다. 키 순서를 바탕으로 그래프를 만들면 다음과 같이 만들어 집니다. 여기서 4번만 자신의 키 순서를 정확히 알 수 있습니다. 처음에 생각한 방법은 dfs입니다. 1번 노드부터 n번 노드까지 차례로 dfs를 진행하면서 모든 노드를 방문하면 그 노드는 자신의 키 순서를 정확히 ..

AMPS(Advanced Mobile Phone System) using FDMA GSM(Global System for Mobile Communication) TDMA와 FDMA를 사용 이중 통신을 위한 2개의 band(대역) 사용 복잡한 오류 수정 메커니즘 때문에 GSM을 3만큼 낮은 reuse factor를 허용한다. CDMA Design Consideration Soft Handoff : base station 한 개 이상의 연결이 공존하는 것 2개의 연결이 공존하다가 1개를 끊으면 통화가 끊기지 않고 계속 유지 됨 낭비가 일어나지만 통화품질은 향상 Universal Frequency Reuse Cell and Sector cell은 BS가 커버하는 범위이다. sector는 방향성 안테나에 의해 ..