반응형 boj27 [백준 7576] 토마토 - C++ (BFS풀이) 토마토문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.토마토를 창고에 보관하는 격자모양의 상자들.. 2024. 5. 15. C++ 다익스트라 개념과 예제-백준 1753번 다익스트라 알고리즘다익스트라 알고리즘은 그래프에서 최단거리를 구하는 알고리즘으로, 가중치 그래프에서 한 정점에서 다른 정점과의 최단거리를 구하는 알고리즘 입니다.다음과 같이 주어진 그래프를 인접리스트로 구현합니다. 한 노드에 대해 인접한 정점을 (노드번호, 거리) 튜플로 저장합니다.1 -> (2,8) (3,3)2 -> (4,4) (5,15)3 -> (4,13)4 -> (5,2)5위와 같이 인접리스트를 만든후, 최단 거리리스트를 초기화하고 탐색을 시작합니다.정점 1부터 출발한다고 가정하겠습니다. (INF는 무한대 입니다.)123450INFINFINFINF그 중 거리가 가장 짧은 1을 채택해서 탐색합니다.12345083INFINF1은 이제 탐색했으므로 방문여부 체크하고 다시 탐색하지 않습니다. 1을 제외한 .. 2024. 5. 15. [백준 2098] 외판원 순회(TSP) - 비트필드를 이용한 DP (파이썬 Python) 외판원 순회문제외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 .. 2024. 5. 10. [백준 1562] 계단 수 - 비트필드를 이용한 DP (파이썬 Python) 계단 수 문제 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력 10 예제 출력 1 '그냥' 계단수 구하기 이 문제와 유사한 쉬운 계단 문제가 있는데 여기 방식에서 0~9까지의 숫자가 들어가있는지만 체크하면됩니다. 쉬운 계단 문제에서는 그냥 n자리가 나왔을때, 그냥 계단 수만 구하면 되므로, 다이나믹프로그래밍.. 2024. 1. 1. [백준 2448] 별 찍기 - 11 (파이썬 Python) 별 찍기 - 11 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 예제 입력 24 예제 출력 * * * ***** * * * * * * ***** ***** * * * * * * ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * * * * * * * * * ***** ***** ***** ***** * * * * .. 2023. 9. 25. [백준 16236] 아기 상어 - 파이썬(Python) BFS풀이 시간 복잡도를 잘 줄인 코드 입니다!아기 상어문제N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.더 이상 먹을 수 있는 물고.. 2023. 9. 24. [백준 10830] 분할정복을 이용한 행렬 제곱 - 파이썬(Python) 행렬 제곱 문제 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. 입력 첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000) 둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다. 출력 첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다. 예제 입력 2 5 1 2 3 4 예제 출력 69 558 337 406 행렬의 거듭제곱 행렬의 제곱은 아래와 같이 똑같은 정사각행렬을 내적시키는 것을 행렬의 제곱이라고 합니다. 그럴려면 벡터/행렬의 내적을 알아야.. 2023. 9. 24. 이전 1 2 3 4 다음
