youngseo's TECH blog

0. 문제 양팔저울 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 1. 문제 해석 추의 종류와 구슬의 종류가 주어졌을 때 추들로 구슬들의 무게를 판단할 수 있는가 없는가를 물어보는 문제이다. 예를 들어 예제 2를 보면 추 1,4kg으로 알 수 있는 구슬의 무게는 1,4,3,5 kg에 해당한다. 양팔 저울의 양쪽에 놓을 수 있다는 것을 주의하자! 따라서 Knapsack으로 DP를 채워나간다. DP[추의 종류][구슬 무게] = 가능?불가능? 으로 나타낼 수 있고 DP table을 채우는 것은 for문 추의 무게로..

0. 문제 K번째 수 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 1. 문제 생각 일단 "정렬"에 대한 직접적인 언급이 있으나 정렬할 수 없다. N이 최대 10**5인데 NlogN을 수행할 수 없으므로! 그리고 나서는 A에 대한 B를 직접 만들어보았다. B=[1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 10, 10, ...] 여기에서 규칙을 찾을 수 있다! 바로 각 숫자가 자신의 "약..

0. 문제 데이터 체커 22942번: 데이터 체커 데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다. www.acmicpc.net 1. 문제 생각 기하 골드 문제로, 처음부터 괄호 문제랑 연관해서 떠올리지는 못했다..🤦 힌트도 오히려 수학 문제처럼 줘서 더 헷갈릴 수 밖에 없었는데, 역시 백준에서 수학 문제가 나오면 자료구조나 알고리즘적 접근을 더 의심해보는 게 좋은 방향인 것 같다. 이 문제는 괄호 문제와 비슷하게 해결할 수 있다. ( ( ) ) 괄호들이 색깔들로 주어진다고 응용해서 생각하면 되고, 주어지는 상황 속에서 같은 모양의 '('이 들어갔다면 같은 모양의 ')'가 들어가 '('를 상쇄시켜주면 된다는 점에서 stack이라는 구조를 사용한다는 걸 떠올릴 수 있다. 2. 문..

0. 문제 공항 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 1. 문제 생각 공항 도킹에 대한 한국어 풀이가 생각보다 이해가 잘 되지 않아 예제를 계속 읽고서야 이해가 되었다. 차라리 밑에 예제를 예제 2 : [2][1][3][?] 로 풀이 방법을 줬으면 더 이해가 잘 되었을텐데 😥 아무튼 이 문제의 핵심은 "i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후..

0. 문제 문자열 화폐 17828번: 문자열 화폐 첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다. www.acmicpc.net 1. 문제 생각 어떤 문자열을 채워나가는 과정이다. 간단하게 증명하여 AAA 특정 문자열 ZZZ로 그리디 과정을 거친다는 것을 알 수 있다. 아래 테스트케이스를 생각하면서 풀면 도움이 되었다. 6 50 AAAAZZ 6 55 AAAAYZ 6 156 ZZZZZZ 2. 문제 구현 import sys input=sys.stdin.readline N,X=map(int,input().split()) if N*26X: print("!") else: List=['A' fo..

0. 문제 두 로봇 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 www.acmicpc.net 1. 문제 생각 한점 -> 여러 점의 최단거리를 구현할 수 있는 다익스트라를 사용했다. 다만 다익스트라 q에 넣을 때 (cost, 노드, 지금까지 나온 경로 중 최댓값)으로 가져가면서 풀었다. 입력값으로 받은 start부터 -> 모든 다른 점까지의 최단거리를 구한 후 이렇게 진행하면서 거쳐가게 되는 간선 중 가장 큰 가중치를 가지는 것들을 함께 가져갔다. 이후 start로부터 end까지의 거리인 distance[end]에서 max_di..

0. 문제 트리 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 1. 문제 생각 전위순회, 중위순회, 후위순회의 핵심은 규칙과 재귀이다. 재귀에서도 사실상 어디에서 재귀로 진입하는가(반환하는가) 가 가장 중요하다. -> 기초 설명 위 문제에서도 전위, 중위 순회일 떄 규칙적으로 왼쪽/오른쪽으로 빠지는 것이 규칙적으로 진행됨을 알 수 있다. 따라서 recursion을 전위, 중위 순회에 따라 root 노드 -> left 노드 -> right 노드로 들어가도록 구현하고 if (currentNode){ ..

0. 문제 후보 추천하기 1713번: 후보 추천하기 첫째 줄에는 사진틀의 개수 N이 주어진다. (1 ≤ N ≤ 20) 둘째 줄에는 전체 학생의 총 추천 횟수가 주어지고, 셋째 줄에는 추천받은 학생을 나타내는 번호가 빈 칸을 사이에 두고 추천받은 순서대 www.acmicpc.net 1. 문제 생각 1