즐겁게, 코드

[백준 온라인 저지 링크] 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2178번 미로 탐색과 비슷하게 BFS 탐색을 최소화하는 경로를 찾아야 했습니다. 다만 가장 머리아팠던게 바로 세 번째 케이스로, 출발지점이 둘 이상일 경우에는 아래처럼 토마토를 발견할 때 탐색을 시작하도록 하면 절대 최솟값을 찾을 수 없습니다. for row in range(N): for col in range(M): if tomatoes[row][col] == 1 and visited[row][col] == Fals..

[백준 온라인 저지 링크] 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 시작하기 전, 후위 표기식이란 피연산자 뒤에 연산자가 오는 방식을 의미합니다. 다음은 테스트케이스로 주어진 예시의 계산 순서입니다. 대충 후위 표기식에 대해서는 이해가 되셨다면, 눈썰미가 빠른 분들은 한가지 눈치채신게 있으실 겁니다. 이 문제는 스택에 수를 하나씩 넣으면서(push) 연산자를 만나면 이전 두 수를 빼고(pop), 연산을 수행한 값을 다시 스택에 넣으면 됩니다. 그럼 남은 문제는 후위 표기식 문자열의 알파벳을 ..

[백준 온라인 저지 링크] 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 다른 분들 코드를 보니 한번의 탐색만으로 답을 구하는 분들이 많았는데, 저는 두 번의 탐색을 활용하는 코드를 작성했습니다. 테스트케이스로 주어진 배열과 함께 빗물의 높이가 3인 경우를 예로 들겠습니다. 첫 번째 BFS 탐색에서는 원본 배열을 탐색해 안전 여부를 판단하는 배열을 만들어냅니다. 두 번째 BFS 탐색에서는 이렇게 만들어진 안전 영역의 수를 세 줍니다. 다만 한 가지 조심할 점은 "비가 오지 않는 경우 (= 높이가 0일때)" 가 마지..

[백준 온라인 저지 링크] 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net BOJ 2667번: 단지번호붙이기 와 유사한 문제다. 입력받을 때만 조심하면 크게 꼬인 트릭은 없는 문제! [정답 코드 - Python] from collections import deque N, M = map(int, input().split()) picture = [] visited = [[False] * M for _ in range(N)] dy = [1, 0, -1, 0] dx = [0, 1, 0, -1] picture_cnt = 0..

[백준 온라인 저지 링크] 17206번: 준석이의 수학 숙제 10 이하의 3 또는 7의 배수는 3, 6, 7, 9가 있다. 21 이하의 3 또는 7의 배수는 3, 6, 7, 9, 12, 14, 15, 18, 21이 있다. www.acmicpc.net 주어진 N 이하의 3 또는 7의 배수의 합을 구하는 문제입니다. [이렇게 풀면 안돼요] T = int(input()) a = list(map(int, input().split())) for elem in a: ans = 0 for i in range(elem + 1): if i % 3 == 0 or i % 7 == 0: ans += i print(ans) 이렇게 코드를 짜면 (최대 10만개의 케이스) * (for문 루프 80000개) 의 제약에 걸리게 되어 ..

[백준 온라인 저지 링크] 9047번: 6174 입력은 표준입력(standard input)을 통해 받아들인다. 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스마다 한 줄에 네 자리 수(1000~9999)가 하나씩 주어진다. 단, www.acmicpc.net 기초 테스트 문제로 올라와 풀어본 문제였는데, 생각보다 까다로운 문제였습니다. 숫자 문자열의 (내림차순 정렬 결과) - (오름차순 정렬 결과)를 계속 구해주면 간단하게 답을 찾을 것 같지만... 아무 생각 없이 덤비면 피로 얼룩진 결과창을 보게 됩니다. 시간 초과의 이유는 바로 1000과 9998 두 개의 케이스 때문으로, 두 케이스는 다음 결과를 얻게 됩니다. (+ 이 둘은 제가 발견한 일부로, 찾지 ..

[백준 온라인 저지 링크] 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 분류가 BFS로 되어있어 별 생각없이 BFS로 탐색을 구현했지만, DFS를 사용하면 시간 초과가 난다고 한다. DFS를 사용하는 코드는 약간 백트래킹? 하듯이 분기별로 값을 저장해둔 뒤 저장한 값들 중 최솟값을 구하면 될 듯 한데... 나보다 잘 짜는 사람들이 안된다는 데에는 이유가 있을 것이다. (_ _) 아무튼 최단거리를 구하는 문제는 BFS 방식을 사용하는 것이 정석이라고 한다. 앞으로 비슷한 유형은 BFS를 열심히 우려먹자. (예전에 얼핏 어떤 문제 유형..