문제 소개 https://www.acmicpc.net/problem/2376 2376번: 단말 정점들의 거리 첫째 줄에 단말 정점의 개수 n(2≤n≤1,000)이 주어진다. 다음 n-1개의 줄에는 차례로 1, 2번 단말 정점 사이의 거리, 2, 3번 단말 정점 사이의 거리, …, n-1, n번 단말 정점 사이의 거리가 주어진다. 다 www.acmicpc.net 이진트리와 인오더의 개념을 이용한 단순 구현 문제입니다. 규칙을 찾는다는 점에서 구성적 문제이기도 합니다. 문제를 어떻게 풀어야 할지는 알겠는데, 구현을 어떻게 할 지 감이 안잡히는 느낌으로 풀었던 문제입니다. 풀이 아이디어 풀이 아이디어는 생각보다 간단합니다. 문제에서 주어진 조건들을 하나씩 살펴보겠습니다. 1. n개의 단말 정점을 갖는 루트가 ..
문제 소개 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 가장 긴 증가하는 부분 수열의 응용문제이다. 가장 긴 증가하는 부분 수열의 풀이 과정을 정확하게 이해하고 있다면, 이 문제 역시 어렵지 않게 풀 수 있다. (골드3 난이도길래 특별한 코너케이스가 숨어있는 줄 알았는데, 다행히 그런 건 없었다.) 11053 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 9465 스티커 https://www.acmicpc.ne..
https://www.acmicpc.net/problem/14653 14653번: 너의 이름은 첫째 줄에 OAKAK TALK방에 있는 사람 수 N과 총 메시지의 개수 K, 정보를 알고 싶은 메시지의 번호 Q가 주어진다. (1 ≤ N ≤ 26, 1 ≤ K ≤ 10,000, 1 ≤ Q ≤ K) 둘째 줄부터 K개의 줄에 걸쳐 메시지를 읽지 www.acmicpc.net 알고리즘 분류는 문자열, 구현으로 되어있다. 구현 문제가 맞기는 한데, 개인적으로 실버5 난이도보다는 살짝 높은 난이도의 구현이라고 생각했다. 풀이 아이디어 이 문제는 메세지를 보낸 사람과 그 메세지를 읽지 않은 사람의 숫자가 주어질 때, 임의로 선택한 메세지를 읽지 않은 가능성이 있는 사람을 모두 찾는 문제이다. 처음 이 문제를 봤을 때는 풀이..
https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net DP 유형의 '스티커' 문제이다. 데이터가 추가되면서 옛날에 맞았던 코드가 틀리자 다시 풀어보게 되었다. 기본적인 DP의 문제풀이 방식은 문제를 단계별로 쪼개어 이전단계에 푼 문제를 이번 단계 풀이에 활용하는 것이다. 이 문제는 이전 단계에 어떻게 문제를 풀었는지에 따라 이번 단계에 문제 풀이 방식이 달라진다는 점이 특징인 문제였다. 피보나치 수열, 정수삼각형과 같은 단순 메모이제이션 ..
https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 알고리즘 스터디에서 '정렬' 연습문제로 풀게된 문제였다. 풀이 아이디어 내가 떠올린 기본적인 알고리즘은 다음과 같다. 1. 입력받은 추를 무게순으로 오름차순 정렬한다. 2. 추를 앞에서 하나 가져와서 "추 그룹"에 추가한다. 3. 추 그룹의 무게 합과 다음 추의 무게를 비교한다. 만약 다음 추의 무게가 '추 그룹의 무게합 + 1' 보다 크면, 어떤 방법을 써도 '추 그룹의 무게합 + 1' 의 무게는 잴 수 ..
https://www.acmicpc.net/problem/15815 15815번: 천재 수학자 성필 길이가 100이 넘지 않는 수식이 예제 입력과 같이 공백 없이 입력된다. 수식은 0부터 9까지의 숫자와 연산자 '+', '-', '*', '/' 로만 이루어져 있다. 또한, 수식의 계산 중간 과정의 모든 결과는 항상 2 www.acmicpc.net 동아리 알고리즘 스터디의 멘토로서, 스택 연습문제 추천을 위해 스택 문제를 찾던 중 후위연산식 문제와 유사한 문제를 발견하여 풀어보았다. 후위연산식 문제가 중위연산식 문제를 후위연산식으로 고치는 문제라면 이 문제는 후위연산식을 보고 그 값을 계산한 결과를 출력하는 문제이다. 처음에는 소수점 부분에 이상하게 얽메여서 삽질을 좀 했지만, 중간 계산 결과가 항상 정수..
https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net solved.ac의 class5 문제를 보던 중 시도해보게 된 DP 문제 Dance Dance Revolution의 풀이과정을 정리한다. 매우 비효율적으로 풀게 되었지만, 우선은 3차원 DP테이블로 DP문제를 푸는 경험을 해봤다는 것으로 만족하고자 한다. 이 문제를 보고 제일 먼저 떠오른 풀이는 그리디하게 매 순간 가장 가까운 위치의 버튼을 누르는 것이었지만, 지..
https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 문자열처리 문제처럼 보였지만, 의외로 자료구조 문제였다. 아이디어를 구상하고 구체화, 테스트하는데 30분, 코드로 구현하는데 30분 정도 걸린 것 같다. 문제를 이해하는데 큰 어려움은 없었다. 풀이 아이디어 이 문제를 푸는데 중요한 것은 아래 2가지를 떠올리는 것이다. 1. '우선 순위가 높은 연산자를 먼저 처리한다' 2. 괄호 내부의 연산은 괄호 외부와 문제 풀이 구조가 동일하다 = 재..
https://www.acmicpc.net/problem/3709 3709번: 레이저빔은 어디로 레이저박스라는 게임은 정사각형 모양의 n x n 보드에서 진행한다. (체스판을 상상하면 된다) 레이저박스의 임의의 칸마다 우향우 거울이라는 장치가 설치되어 있고, 마지막으로 레이저 한개가 www.acmicpc.net 그래프 연습문제를 찾다가 오늘은 적당한 난이도로 해보고자 solved.ac 기준 골드 5인 문제를 골랐다. 번역은 오역이 난무해서 문제 이해조차 제대로 안되고, 난이도는 또 너무 쉬워서 좋은 기억은 없었던 문제.. 이 정도 난이도면 실버5~4 수준으로 넣어도 아무 상관 없을 것 같다.. 번역에서 행과 열을 거꾸로 쓰는 바람에 매우 헷갈렸다. 행인데 어떻게 맨 밑에서 위로 쏘는건지... 이 문제는 ..
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 분리집합 (유니온-파인드)를 사용하여 푸는 문제이다. 문제 분류를 보면 그래프 탐색으로도 분류가 되어있는데, 우선은 분리집합으로 풀어보았다. 이 문제는 시간제한도 2초로 넉넉한데, 파티당 인원수, 파티수, 총 사람 수가 매우 작다. 그래서 시간복잡도는 거의 신경쓰지 않고.. 그냥 최대한 되는 대로 풀어보았다. 풀이 아이디어 1. 분리집합 자료구조만 이해했다면 문제 해결 아이디어를 떠올리는 것은 어렵지 않다...
