Python
-
백준 12015 : 가장 긴 증가하는 부분 수열 2개발/알고리즘 문제풀이 2022. 12. 16. 17:08
문제는 아래 링크에 : https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이 알고리즘의 원리는 다음과 같다. 가장 긴 증가하는 부분 수열을 저장할 리스트를 하나 만든다. 그리고 주어진 입력값을 순차적으로 순회하며 리스트를 갱신하는데, 아래 과정에 따른다. 현재 값 n이 리스트의 최댓값보다 크면, 수열이 증가함이 보장된다. 그러므로 리스트의 마지막에 n을 append 해준다. 현재 값 n이 리스트의 최댓값과 같거나 작다면, 수열이 증가하지 않는다...
-
[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)을 해야 하지만 우선순위 큐는 내가 매긴 우선순위에..
-
[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/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 ..