즐겁게, 코드

[백준 온라인 저지 링크] 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라고 해서 브루트 포스로 ..

[문제 링크] - 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)..

[백준 온라인 저지 링크] 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 아, 이 문제는 다른 탐색 문제들보다 조금 더 특별합니다. 바로 제 손으로 처음 푼 골드 문제인데요, 정말 상쾌하네요! 🤣 [정답 코드 - Python] from collections import deque N = int(input()) board = [] visited = [[False] * N for _ in range(N)] dy = [-1, 0, 1, 0] dx = [0, 1, 0, -1] countNormal = 0 co..

[백준 온라인 저지 링크] 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 특별한 점은 없는 탐색 문제입니다! 다만, 섬을 사방이 아니라 대각선까지 탐색해야 한다는 점에만 유의하세요! [정답 코드 - Python] from collections import deque dy = [-1, 0, 1, 0, -1, 1, 1, -1] dx = [0, 1, 0, -1, 1, 1, -1, -1] def BFS(node): q = deque() q.append(node) global visited visited[nod..