백준
-
[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/DAY05] 백준 문제 : 행렬 제곱카테고리 없음 2022. 10. 4. 02:50
https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 제법 어려운 문제들이 출현하고 있다. 다른 사람들의 정답 코드를 많이 참고하게 되는 것 같다. 문제 해석 : N*N 크기의 정사각형 행렬 A가 주어지는데, A행렬을 B제곱 한 결과를 출력해야 한다. 그런데 그대로 출력하는 것이 아니라 각 원소를 1000으로 나눈 나머지를 출력해야 한다. 접근 : 이 문제를 해결하기 위해 필요한 과정을 다음과 같이 나눠 보았다. 1. 행렬간의 곱셈을 구현하는 것 2. 행렬을 큰 ..
-
[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/DAY02] python : 배열의 복사본을 삭제했는데 원본이 삭제될 때SW Jungle/TIL (Today I Learned) 2022. 9. 25. 02:48
python으로 재귀호출 알고리즘 문제를 풀던 중, 원본 배열이 필요해서 남겨두기 위해 복사본을 만들고 복사본의 일부를 del 명령어를 이용해 삭제했는데 원본이 같이 삭제되어 버리는 현상이 발생했다. 예를 들면, a = [1, 2, 3, 4, 5, 6] b = a# [1, 2, 3, 4, 5, 6] del b[0]# b배열의 0번째를 삭제했으므로 b배열은 [2, 3, 4, 5, 6]이 된다. # 나는 b배열의 일부분을 삭제했으니, a배열은 남아있어야 하는데... print(a)# [2, 3, 4, 5, 6] print(b)# [2, 3, 4, 5, 6] # ?????? 이렇게 되는 것이다. 왜 그런가 하니, 이것은 python의 객체 개념을 이해하지 못한 나의 잘못이었다. python에는 mutable ..
-
[WEEK01/DAY01] 백준 문제 : 소수 찾기SW Jungle/TIL (Today I Learned) 2022. 9. 24. 02:24
https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 오늘 풀었던 알고리즘 중에 제일 어려웠던 문제다. 소수는 약수가 1과 자기 자신밖에 없는 1보다 큰 자연수를 말한다. 그래서 1보다 큰 자연수 n이 주어졌을 때 n이 소수인지를 판별하는 가장 간단한 방법은 2에서 n-1 까지의 모든 자연수로 나누어 보는 것이다. 만약 한 경우에라도 나누어 떨어진다면, n은 소수가 아닌 것이다. 위 방법으로 풀이하면 시간 복잡도가 O(N)이 된다. 좀 더 빠른 방법이 있는데, 굳이 2에서 n-1까지 반복하지 않고 √n 까지만 반복해도..