백준 1629번: 곱셈

거듭제곱과 분할 정복 알고리즘이 문제는 거듭제곱을 효율적으로 계산하기 위한 분할 정복 알고리즘을 사용하는 문제입니다. 거듭제곱 계산은 A의 B승 같은 큰 수를 다루기 때문에, 이를 단순히 반복 계산하면 비효율적입니다. 따라서 분할 정복을 활용하여 계산을 최적화합니다. 분할 정복 알고리즘이란?분할 정복은 문제를 작은 하위 문제로 나누고, 이를 재귀적으로 해결하여 결론을 도출하는 알고리즘입니다. 큰 문제를 나눔으로써 계산량을 줄이고 효율적으로 문제를 해결할 수 있습니다.분할 정복과 다이나믹 프로그래밍(DP)은 비슷하게 보일 수 있으나, 두 알고리즘은 차이가 있습니다. 분할 정복과 DP의 차이특징분할 정복다이나믹 프로그래밍문제 나누기문제를 작은 하위 문제로 나눔하위 문제를 저장하고 중복된 계산을 제거중복 계산..

• format_list_bulleted 알고리즘/백준
• · 2025. 1. 5.
• textsms

백준 2667번: 단지번호 붙이기(bfs)

2024.12.12 - [알고리즘/백준] - 백준 2667번: 단지 번호 붙이기 백준 2667번: 단지 번호 붙이기import sysinput = sys.stdin.readlinetc = int(input()) # 지도의 크기 (N x N)dx = [-1, 1, 0, 0] # 상하좌우 이동dy = [0, 0, -1, 1] # 상하좌우 이동# DFS 함수: 특정 좌표를 시작으로 연결된 집들의 크기를 구한다def dfs(graphha-vlog.tistory.com이전 글에서는 DFS로 문제를 해결했지만, 이번에는 BFS로 접근해 보았습니다.DFS와 BFS가 모두 사용 가능한 이유이 문제에서 DFS와 BFS가 모두 가능한 이유는 다음과 같습니다:탐색 범위가 제한적: 문제의 입력 크기가 작기 때문에 DFS와 B..

• format_list_bulleted 알고리즘/백준
• · 2024. 12. 14.
• textsms

백준 2667번: 단지 번호 붙이기(dfs)

import sysinput = sys.stdin.readlinetc = int(input()) # 지도의 크기 (N x N)dx = [-1, 1, 0, 0] # 상하좌우 이동dy = [0, 0, -1, 1] # 상하좌우 이동# DFS 함수: 특정 좌표를 시작으로 연결된 집들의 크기를 구한다def dfs(graph, visited, width, height): visited[height][width] = 1 # 현재 좌표 방문 처리 count = 1 # 현재 집 포함 (단지 크기 초기값) for i in range(4): # 상하좌우로 이동 rx = width + dx[i] ry = height + dy[i] # 유효 범위 내에서, 방문하지..

• format_list_bulleted 알고리즘/백준
• · 2024. 12. 12.
• textsms

백준 1285번: 숨바꼭질 2

2024.10.30 - [알고리즘/백준] - 백준 1697번- 숨바꼭질 백준 1697번- 숨바꼭질문제 요약수빈이는 현재 위치 N에 있고, 동생은 위치 K에 있다. 수빈이가 이동할 수 있는 세 가지 방법은 다음과 같다:한 칸 뒤로 가기: 현재 위치에서 -1만큼 이동 (X - 1)한 칸 앞으로 가기: 현재ha-vlog.tistory.com이전 문제에서 최소 거리로 가는 방법을 구하는 경우의 수까지 구해줘야 하는 문제이다.저번에는 도착 지점에 최소 거리로 도달하면 그 거리만 출력하면 되는거였지만 이번에는 그 최소 거리가 몇 번 가능한지 경우의 수까지 구해줘야 하는 것이다.  from collections import dequedef bfs(n, k): # 방문 시간을 기록하는 배열 (-1은 방문하지 않았..

• format_list_bulleted 알고리즘/백준
• · 2024. 12. 11.
• textsms

백준 1504번 : 특정한 최단 경로

2024.02.10 - [알고리즘] - 다익스트라 알고리즘이 문제는 다익스트라 알고리즘을 활용하여 최단 경로를 찾는 문제입니다. 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로 가는 최단 거리를 찾을 때 사용되는 알고리즘으로, 가중치가 있는 그래프에서 음수 가중치가 없을 때 효율적으로 사용할 수 있습니다.다익스트라 알고리즘의 개념다익스트라 알고리즘의 핵심은 시작 정점에서 다른 정점들로 가는 최단 경로를 점진적으로 찾는 것입니다. 최단 거리를 기록하면서, 방문하지 않은 정점 중 현재까지 가장 짧은 거리로 도달할 수 있는 정점을 선택해 이동하며 최단 경로를 찾아나갑니다.다익스트라 알고리즘의 동작 과정초기화: 시작 정점의 거리를 0으로 설정하고, 다른 모든 정점의 거리는 무한대로 초기화합니다.정점 선택:..

• format_list_bulleted 알고리즘/백준
• · 2024. 11. 1.
• textsms

백준 1697번- 숨바꼭질

문제 요약수빈이는 현재 위치 N에 있고, 동생은 위치 K에 있다. 수빈이가 이동할 수 있는 세 가지 방법은 다음과 같다:한 칸 뒤로 가기: 현재 위치에서 -1만큼 이동 (X - 1)한 칸 앞으로 가기: 현재 위치에서 +1만큼 이동 (X + 1)순간이동하기: 현재 위치에서 *2만큼 이동 (2 * X)각 이동은 1초가 걸리며, 수빈이가 동생의 위치 K에 도달하는 데 걸리는 최소 시간을 구하는 것이 목표이다.알고리즘 설명최단 시간을 구하는 문제는 BFS(너비 우선 탐색)로 해결하는 것이 적합하다. 이유는 다음과 같다:BFS는 최단 경로를 보장한다. 한 단계씩 모든 가능한 위치를 탐색하기 때문에, 목표 위치에 가장 먼저 도달한 경로가 곧 최단 경로가 된다.DFS(깊이 우선 탐색)는 한 경로를 끝까지 탐색하므로 ..

• format_list_bulleted 알고리즘/백준
• · 2024. 10. 30.
• textsms