문제풀이

[문제] https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] 그래프 최단 거리 문제 다익스트라 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 플로이드 와샬 거쳐가는 정점을 하나씩 다 설정을 하여 해당 정점을 기준으로 최단 거리를 구하도록 구성 → 모든 쌍 간의 최단 거리를 구할 수 있음 모든 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘  [코드] import sys N = int(sys.stdin.readline()) graph = ..

[문제] https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net [풀이] 우와 탐욕법인가 했는데.. 이게··· BFS 문제라니.. 충격과 공포 그자체였음 그렇지만!.... 탐색 문제인걸 알기만 하면 문제 푸는건 쉽다 하하 사다리와 뱀 dictionary를 만들어 key와 value로 저장한다. deque로 선언한 큐에 처음 출발지인 1을 넣는다. 주사위 숫자인 1부터 6까지 반복문을 돈다. 이동할 칸이 1..

[문제] https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net [풀이] 딱봐도 탐색문제..~ 내가 계속 BFS로 풀어서 DFS로도 한번 풀어봤다 계속 까먹어서 적어두는데 BFS는 deque를 이용해 풀고 DFS는 재귀 호출을 이용해 푼다. 공통점은 둘 다 visited를 이용해서 해당 칸 방문 여부를 검사했다. [BFS 코드] import sys from collections import deque n = int(sys.stdin.readli..

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