BOJ

[문제] https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net [풀이] 우선 이 문제는 풀이 방식이 두 가지가 있다. 동적 프로그래밍을 이용해 풀기 조합을 이용해 풀기 동적 프로그래밍 풀이 1 2 3 4 5 1 1 2 3 4 5 2 X 1 3 6 10 3 X X 1 4 10 행이 n, 열이 m을 나타낼 때 1. n이 1인 경우 만들어지는 경우의 수는 m과 같다. 2. n이 2이상인 경우 num[n][m] = num[n][m - 1] + num[n -..

[문제] https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net [풀이] 재귀 문제.. 분할 정복법 문제 2021.08.11 - [문제풀이/BOJ] - [Python] BOJ/백준 2630번 색종이 만들기 [Python] BOJ/백준 2630번 색종이 만들기 [문제] https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, ..

[문제] https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net [풀이] 🔥 DFS vs BFS ✨ DFS, BFS 모두 적합한 유형 단순히 모든 정점을 방문하는 것이 중요한 문제인 경우 ✨ DFS가 적합한 유형 검색 대상 그래프가 큰 경우 (정점과 간선의 개수가 많음) 경로의 특징을 저장해둬야 하는 문제 ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제 BFS는 경로의 특징을 가지지 못함 ..

[문제] https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [풀이] 🔥 DFS vs BFS ✨ DFS, BFS 모두 적합한 유형 단순히 모든 정점을 방문하는 것이 중요한 문제인 경우 ✨ DFS가 적합한 유형 검색 대상 그래프가 큰 경우 (정점과 간선의 개수가 많음) 경로의 특징을 저장해둬야 하는 문제 ex) 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는 데 경로에 같은 숫자가 있으면 안된다는 문제 BFS는 경로의 특징을 가지지 못함 ✨ BFS가 적합한 유형 미로찾..

[문제] https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net [풀이] 이전에 풀었던 7662번 이중 우선순위 큐와 유사하다. 2022.06.24 - [문제풀이/BOJ] - [Python] BOJ/백준 7662번 이중 우선순위 큐 [Python] BOJ/백준 7662번 이중 우선순위 큐 [문제] https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입..

[문제] https://www.acmicpc.net/problem/23037 23037번: 5의 수난 키파는 문득 3과 4의 견고한 벽에 가로막혀 스포트라이트를 받지 못하는 5를 떠올렸다. '세상에 얼마나 많은 것들이 5와 관련이 있는데!' 키파는 5가 쓰이는 곳을 떠올리기 시작했다. 사람의 손가 www.acmicpc.net [풀이] readline 시 "\n" 도 n에 포함되기 때문에 슬라이싱으로 잘라준다. 문자열 n을 한글자씩 int로 형변환을 해주어 5제곱을 한 후 더해준다. [코드] import sys n = sys.stdin.readline()[:-1] result = 0 for c in n: result += int(c) ** 5 print(result)

[문제] https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net [풀이] 이 문제는.. 지문에 나와있는 `최소 일수`, `인접한 여섯 방향의 토마토가 익음` 키워드로 bfs 문제임을 알 수 있다. 최소 일수를 구하는 문제는 bfs를 이용한다. 이전에 풀었던 7576 토마토 문제 + 2차원 의 문제이다. 해당 문제가 어렵고 7576번을 아직 풀지 않았다면 .. 7576번부터 먼저 풀면 도움이 될 것 같다. 2022.06.22 - ..

[문제] https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net [풀이] 가장 간단한 방법인 max, min 으로 찾는 방법은 시간초과가 나온다 (당연함) 파이썬의 우선순위 큐 문제는 heapq, PriorityQueue 두 가지 라이브러리를 사용할 수 있다. https://stackoverflow.com/questions/36991716/whats-the-difference-between-heapq-and-priorityqueue-in-pytho..

[문제] https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net [풀이] 이 문제는 지문에 나와있는 `최소 일수`, `인접한 네 방향의 토마토가 익음` 키워드를 통해 bfs문제임을 알 수 있다. 최소 일수를 구하는 문제는 bfs를 이용한다. 나름의? 주의해야할 점은 첫 번째 날에 토마토 박스에 1이 여러 위치에 있을 경우 동시다발적으로 각 위치 주위의 토마토가 익어야하기 때문에 main에서 bfs 함수를 부를 때 상자에 저장된 토마토들..