즐겁게, 코드

[백준 온라인 저지 링크] 16469번: 소년 점프 첫째 줄에 미로의 행과 열의 크기를 나타내는 자연수 R과 C가 주어진다. (2 ≤ R, C ≤ 100) 다음 R줄에 걸 쳐 길이 C로 이루어진 각 줄의 미로의 정보가 공백 없이 주어진다. 숫자 0은 이동 가능한 www.acmicpc.net BFS에 약간의 잡기술을 얹은 문제입니다. 풀이가 복잡하지는 않은데, 이걸 설명하려 하니 뭔가 복잡해질 것 같아 적당히 "이렇게 푼 사람도 있구나" 하시고 봐주셔도 될 것 같습니다. [정답 코드 - Python] import sys from collections import deque input = sys.stdin.readline R, C = map(int, input().split()) visitedA = [[-1..

[백준 온라인 저지 링크] 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net 간단한 브루트 포스 문제처럼 보일 수 있지만, N과 M 유형의 백트래킹 문제입니다. 주어진 수와 동일한 구성이면서 해당 수보다 처음으로 큰 숫자를 찾아야 하는데요, 여기서 동일한 구성의 수라 함은 각 자리수를 구성하는 수를 재배열해 만들 수 있는 수를 의미합니다. 즉, 주어진 수가 176이라면 671이 167과 "구성이 같은 수" 이자 첫 번째로 큰 수가 됩니다. 입력값이 1 ~ 999,999라고 해서 브루트 포스로 ..

[문제 링크] 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 1,000보다 작거나 www.acmicpc.net 시뮬레이션으로 분류되어 있지만, 우선순위 큐를 활용해 풀 수 있는 문제였습니다. 풀이 우선순위 큐는 pop 동작 시 언제나 가장 작거나 큰 값을 내보낸다는 특징이 있습니다. 따라서, 이 속성을 이용해 다음과 같은 시퀀스를 구성합니다. 우선순위 큐 가장 위의 득표수를 1 뺀다. 다솜이의 득표수를 1 올린다. 1번에서 뺀 득표수를 다시 우선순위 큐에 삽입한다. 만약 다솜이의 득표수가 큐의 가장 위의 원소보다 크다면 중단한다. [정답 코드 ..

때때로 프로그래밍 문제를 풀다보면 우선순위 큐를 활용해야 하는 경우가 종종 있습니다. 다만 우선순위 큐는 일반적인 큐나 배열이 아닌 힙을 기반으로 구현되었기 때문에 이를 직접 구현해서 사용하기에는 시간이 조금 걸릴수도 있는데요, 다행히 파이썬에서는 우선순위 큐를 내장 라이브러리로 제공합니다. ⏰ 들어가기 전에 우선순위 큐를 구현한 PriorityQueue 라는 라이브러리도 존재하지만, heapq 보다 훨씬 느리게 동작하므로 코딩 테스트용으로는 적합하지 않습니다. 따라서 이번 글에서는 heapq 를 사용한 방법을 소개하도록 하겠습니다. import heapq # 일반적인 리스트를 선언합니다. pq = [] 우선순위 큐는 원소를 삽입할 때는 일반적인 큐와 유사하지만, 원소를 큐에서 뺄 때는 언제나 작은 값을..

[문제 링크] - https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 백트래킹 문제입니다. 한 가지 주의할 점이 있다면, 만약 부분수열의 누적합을 갖는 변수를 0으로 초기화하고, 만들어야 하는 정수가 0일 때 다음과 같이 로직을 작성할 수 있습니다. def backtrack(idx, numberSum): global count if idx == N: return if numberSum == S: count += ..

[문제 링크] - https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net N과 M 유형의 백트래킹 문제입니다. 단, 중복된 수를 뽑아서는 안되며 로또번호를 오름차순으로 나열해야 한다는 점만 유의하시면 되는 문제입니다. 정답 코드 (Python) S = [] lottery = [0] * 13 visited = [] def backTrack(depth): global S if depth == 6: for i in range(6): print(l..

[백준 온라인 저지 링크] 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 로마자 조합의 순서를 따지지 않는다는 조건을 통해 중복조합을 구하는 문제임을 알 수 있는데요, 따라서 N과 M 4번과 형태가 매우 유사하지만 같은 코드로 풀면 N=6 부터 답이 달라지기 시작합니다. 왜냐하면 바로 "조합의 합이 같은 경우" 가 생기기 때문인데요, 한번 예시를 들어보겠습니다. // N(뽑아야 하는 수)이 2일 때 (N과 M) => (로마자) 1 1 I I (2) 1 2 I V (6) 1 3 I X (11) 1 4 I L (51) 2 2 V V (20) 2 3 V X (15) 2 4 V L (55) 3 3 X X (20)..