SW Jungle/TIL (Today I Learned)
-
[WEEK04/DAY02] 백준 9084번: 동전SW Jungle/TIL (Today I Learned) 2022. 10. 15. 01:47
https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net DP (다이나믹 프로그래밍)의 대표 문제같은 느낌이다. 문제 해석 : T번의 테스트 케이스가 주어지고, N가지 동전으로 금액 M을 만드는 모든 방법의 수를 출력해야 한다. $N(1 \leq N \leq 20)$개의 동전 종류가 주어진다. 동전은 개수 제한 없이 쓸 수 있다. 동전들의 가치 $N_i (1 \leq N_i \leq 10000)$는 오름차순으로 정렬되어 주어진다. 만들어..
-
[WEEK03/DAY04] 백준 21606번 : 아침 산책SW Jungle/TIL (Today I Learned) 2022. 10. 10. 02:58
https://www.acmicpc.net/problem/21606 21606번: 아침 산책 1번 정점에서 시작하고 3, 4번 정점에서 끝나는 경로, 3번 정점에서 시작하고 1, 4번 정점에서 끝나는 경로, 4번 정점에서 시작하고 1, 3, 5번 정점에서 끝나는 경로, 5번 정점에서 시작하고 4번 정점 www.acmicpc.net 매일 다른 경로로 아침 산책을 하고 싶어? 문제 해석 : '서울과학고의 N개의 장소를 N-1개의 길이 잇는 트리 형태로 단순화했다'라는 말은, 모든 장소가 이어져 있으며 임의의 장소 U와 V 사이를 직접 잇는 간선은 단 하나만 존재한다는 뜻이다. 그리고 문제의 주요 조건을 보면 시작점과 끝점은 반드시 실내여야 하고 경로 중간에 실내가 있어서는 안된다. 이 말인즉슨 경로의 모습은..
-
[WEEK02/DAY06] 백준 문제 : 뱀SW Jungle/TIL (Today I Learned) 2022. 10. 5. 03:14
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제를 푸는 내내 이 노래가 머릿속에 맴돌았다. 나만 당할 순 없지. 문제 해석 : N*N 크기의 정사각형 행렬에서 '뱀 게임'을 구현하는 문제이다. 규칙은 다음과 같다. 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇..
-
[WEEK02/DAY03] 백준 문제 : 최대 힙SW Jungle/TIL (Today I Learned) 2022. 10. 2. 02:26
https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 문제 해석 : 자료구조 '최대 힙'을 이용하여 다음과 같은 기능을 하는 프로그램을 만드는 문제다. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. 접근 : 우선순위 큐를 사용하는 문제이다. 우선순위 큐가 일반 큐와 다른 점은, 일반 큐의 경우 선입선출(First In First Out)을 해야 하지만 우선순위 큐는 내가 매긴 우선순위에..
-
[WEEK02/DAY02] 백준 문제 : 공유기 설치SW Jungle/TIL (Today I Learned) 2022. 10. 1. 03:14
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 해석 : 일직선 상에 놓여 있는 집 N개에 C개의 공유기를 설치할 때, 인접한 두 공유기 사이의 최대 거리를 구하는 문제이다. 즉 주어진 개수의 공유기를 모두 설치하면서도 공유기끼리 최대한 붙어있지 않게... 최대한 사이가 멀어지도록 해야 하는 것이다. 일일히 모든 집에 하나씩 놓아보면서 완전 탐색을 하다가는 시간 초과가 날 것이 뻔하다. ..
-
[WEEK01/DAY06] 백준 문제 : Moo 게임SW Jungle/TIL (Today I Learned) 2022. 9. 29. 03:03
https://www.acmicpc.net/problem/5904 5904번: Moo 게임 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o www.acmicpc.net 즐겁게 할 수 있는 술게임이라는 말에 혹해서 골랐다가, 생각보다 어려워서 애를 먹었다. 문제 설명 : m o o가 특정 규칙에 따라 나열된다. S(0) = "m o o" S(1) = "m o o m o o o m o o" S(2) = "m o o m o o o m o o m o o o o m o o m o o o m o o" 위와 같이 S(0)은 길이가 3인 수..
-
[WEEK01/DAY05] 백준 문제 : 연산자 끼워넣기SW Jungle/TIL (Today I Learned) 2022. 9. 28. 01:56
https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 설명 : 100 이하의 자연수로 이루어진 수열 A[n](2 ≤ n ≤ 11) 이 주어진다. 그리고 그 수열 사이에 들어갈 연산자들이 주어진다. 주어진 수열과 연산자들을 가지고 만들어낼 수 있는 최댓값과 최솟값을 구하는 문제이다. 주어진 조건들이 몇개 더 있는데, 궁금하다면 위 링크에 들어가서 확인할 수 있다. 풀이 : 1. 가능한 연산자..
-
[WEEK01/DAY04] 백준 문제 : 수 정렬하기 3SW Jungle/TIL (Today I Learned) 2022. 9. 27. 01:44
https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 문제의 제한사항을 잘 확인해야 하는 문제였다. 파이썬에서는 길이가 1억(100,000,000)인 리스트를 사용할 때, 약 381MB의 메모리를 사용한다고 한다. 이 문제에 주어진 제한사항을 보면, 시간 제한 5초에 메모리 제한이 8MB 이다. 그러므로 최악의 상황인 천만 개의 수가 주어진다고 할 때, 이들을 정렬하기 위해 배열에 저장하면 메모리 초과가 나게 된다. 그래서 다른 방법을 찾아보았다. 문제의 ..