youngseo's TECH blog

0. 문제 설명 우체국 2285번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. 모든 A[i]를 www.acmicpc.net 1. 문제 생각 처음에는 맨허튼 거리와 같은 알고리즘을 생각했다. 각 마을에 포함되는 사람들의 수를 가중치처럼 여긴 후 ∑각 마을의 index * 사람들의 수/ ∑사람들의 수 로 해결하려고 했는데 한 번 틀렸다 😥 아래 데이터를 조금 더 생각해보면 이 아이디어가 통하지 않음을 알 수 있는데 아래 데이터로 한번 생각해보면 좋다! 6 1 8 8 ..

0. 문제 우수 마을 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 1. 문제 생각 트리에서의 DP 문제이다. 트리란 사이클이 없이 모든 정점이 연결되어있는 그래프로, 사이클이 없는 그래프이므로 정점의 개수가 V개이면 간선의 개수는 V-1개라는 특징을 갖는다. DFS+DP 로 트리에서의 DP를 해결할 수 있고 아래처럼 DP 테이블을 채우기 위해 계속해서 인접한 노드를 탐색하는 점에서 DFS가 강력하다! 2. 문제 구현 import sys sys.setrecursionlimit(10**6) def d..

제 3회 한국항공대학교 프로그래밍 경진대회 제3회 한국항공대학교 프로그래밍 경진대회프로그래밍에 관심이 있다면, 지금 바로 도전해보세요.kaupc2023.netlify.app대회 개최우리 학교는 경인지역 6개 대학 소속으로 매년 SHAKE! 대회에 참여하고 있으며 이 대회에 참여하기 위한 10명의 인원을 교내에서 자체적으로 선발하고 있다. 자체 선발 대회인 KAUPC는 매년 KOALA 동아리에서 주최하고 있으며 이번 년도는 내가 동아리를 운영하고 있어 책임감을 가지고 대회를 주최하게 되었다. 문제 출제를 위해 급하게 500문제를 3달동안 풀었다.대회는 3월부터 미리미리 준비했고 출제진은 gojib2022, hello70825, soo7652, 20wjsdudtj(나) 로 진행되었다. 다들 학교를 떠나 있음..

0. 문제 같이 눈사람 만들래? 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 1. 문제 생각 4개를 뽑아서 대조하는 것으로 먼저 생각해볼 수 있다. 하지만 600C4(5억)는 2초 안에 못 들어오기 때문에 X 일단 N은 600이기 때문에 2초 안에 들어오려면 적어도 N^3까지는 가능하다. 우리가 4개를 뽑아 한 세트를 만든다고 하면 예를 들어 2 3 5 5 일 때 세트는 (1️⃣4️⃣, 2️⃣3️⃣)으로 1번째와 4번째 것이 하나의 세트가 되고 2번째와 3번째 것이 하나의 세트..

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) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후..