Algorithm

[문제] 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 함수를 부를 때 상자에 저장된 토마토들..

[문제] https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net [풀이] 입력되는 내용을 딕셔너리 타입의 book에 key : value 값을 각각 {번호 : 이름}, {이름 : 번호} 로 저장한 뒤 key 값을 이용해 value 를 찾아 출력한다. [코드] import sys if __name__ == '__main__': input = sys.stdin.readline n, m = map(int, input().spli..

[문제] https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net [풀이] 누적 합 누적 합은 구간의 누적 합을 구하는 문제이다. 일반적으로 리스트에 값을 저장하고, 인덱스로 한개씩 더하는 방식은 최악의 경우 O(n^2)의 시간복잡도를 갖기 때문에 입력의 범위가 클 때는 사용할 수 없다. 하지만 Prefix sum 방식을 사용하면 O(n)의 시간복잡도로 해결할 수 있다. 누적합은 문제에서 수열이 주어지고 어떤 구간의 값의 합을 구..