http://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net # 조건 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 입력 트리가 입력으로 주어진다. 첫 줄 -> 트리 정점 개수 V ( 2

백준 1149_RGB 거리 조건 집이 N개가 있고, 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각 집을 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하라. 1번 집의 색은 2번 집의 색과 같지 않아야한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i (2

http://www.acmicpc.net/problem/3425 3425번: 고스택 각각의 입력값에 대해서, 해당하는 프로그램을 수행한 뒤, 출력값을 출력하면 된다. 출력값이란 스택에 저장되어 있는 숫자이다. 만약, 프로그램 에러가 발생하거나, 모든 수행이 종료됐을 때 www.acmicpc.net # 조건 창영이는 스택을 조금 변형해서 고스택을 만듦 숫자만 저장 가능하며 아래 10가지 연산을 수행할 수 있다 편의상 스택의 가장 위에 저장된 수 첫 번째 NUM X: X를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109) POP: 스택 가장 위의 숫자를 제거한다. INV: 첫 번째 수의 부호를 바꾼다. (42 -> -42) DUP: 첫 번째 숫자를 하나 더 스택의 가장 위에 저장한다. SWP: 첫 번째 ..

http://www.acmicpc.net/problem/1484 1484번: 다이어트 성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. www.acmicpc.net # 조건 다이어트 중인 성원이가 저울을 부셨다. 새로운 저울위에 올라간 성원이가 안돼!!!!! G킬로그램이나 더 쪘다고 말을 했을 때, 여기서 G킬로그램은 성원이 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것 이다. 성원이의 현재 몸무게로 가능한 것을 모두 출력하라. # 접근 방법 각 자연수의 제곱을 기록해준다. 이 때, 50,000의 제곱 - 49,999의 제곱이 99,999가 되므로 5..

투 포인터란? 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 시작점과 끝점 - 2개의 점으로 접근할 데이터의 범위를 표현 할 수 있다. 동작 과정 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다. 현재 부분 합이 M과 같다면 카운트 한다. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다. 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다. 예제 # 데이터의 개수 N n = 5 # 찾고자 하는 부분합 M m = 5 # 전체 수열 data = [1, 2, 3, 2, 5] count = 0 interval_sum = 0 end = 0 # start를 차..

http://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net # 조건 방향성 없는 그래프가 주어진다. 세준이는 1번에서 N번 정점으로 최단 거리 이동하는데 아래 두 가지 조건 만족해야된다. 임의로 주어진 두 정점은 반드시 통과 한번 이동했던 정점 및 간선도 이동가능하지만 반드시 최단 경로로 이동하여야 한다. 이 때, 조건을 만족하는 경로가 없을 경우 -1 출력 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주..

http://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 단순 정렬을 이용하여 풀릴 것 같지만, 시간초과에 빠지는 문제이다. # 조건 보석점을 털기로 결심한 상덕이 보석이 총 N개 존재하며, Mi와 Vi의 무게와 가격을 가지고 있다. 가방을 K개 가지고 있으며, 각 가방의 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석 훔칠 수 있는 보석의 최대 가격을 구하라 # 입력 첫째 줄에 N과 K가 ..

http://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net # 조건 지민이는 썰을 풀 때, 있는 그대로 또는 엄청나게 과장해서 말한다. 되도록이면 과장해서 이야기하려고 하는데 거짓말쟁이는 싫다. 몇몇 사람들은 그 이야기의 진실을 알기 때문에 이 사람들이 파티에 온다면 진실만을 이야기 해야 한다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 다른 파티에서는 과장된 이야기를 들었을 때도, 지민이는 거짓말쟁이가 된다. 사람의 수 N이 주어지고 그 이야기의 진실을 아..

http://www.acmicpc.net/problem/14500 # 조건 폴리오미노란 크기가 1 x 1인 정사각형을 여러 개 이어서 붙인 도형이며 아래 조건을 만족해야 된다. 정사각형은 서로 겹치면 안됨 도형은 모두 연결 정사각형의 변끼리 연결되어 있어야 한다. 정사각형 4개를 이어 붙인 폴리오미노를 '테트로미노' 라고 하며, 아래 5가지가 있다. N x M 인 종이 위에 테트로미노 하나를 놓으려고 한다. 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하여라 회전이나 대칭 시켜도 된다. # 접근 방법 및 Solution 각 도형을 돌렸을 때 포함 가능한 모양을 모두 구해준다. 이후 그 도형이 가지는 칸 수에 대해 조건을 달아주며 최댓값을 구한다. 모든 칸을 모든 ..