본문 바로가기

Algorithm705

[분할정복/DQ] 백준 1074 Z - Python [ Contents ] 1. 문제 (링크 참조) 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 2. 문제 풀이 위와 같이 Z 모양으로 이동하는 규칙이 있습니다. 이 때, 2^N * 2^N크기의 r행 c열의 순서를 구하는 문제입니다. 2022.01.29 - [Algorithm] - [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 [Algorithm] 분할정복(DQ, Divide-and-Conquer), 각개격파 알고리즘 각개격파(各個擊破): 적을 하나하나 .. 2022. 2. 25.
[탐색/BFS] 백준 7576 토마토 - Python [ Contents ] 1. 문제 (링크 참조) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 2. 문제 풀이 모든 토마토가 다 익는 데 걸리는 시간을 구하는 문제입니다. 익은 토마토의 상하좌우에 안 익은 토마토가 있으면, 하루 뒤에 익게 됩니다. 2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용.. 2022. 2. 24.
[탐색/BFS] 백준 1697 숨바꼭질 - Python [ Contents ] 1. 문제 (링크 참조) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 문제 풀이 출발 지점 N에서 도착 지점 K까지 가장 빠르게 가는 방법을 찾는 문제입니다. 1) X - 1 2) X + 1 3) 2 * X 3가지 방법으로 움직일 수 있고 최대한 적게 이동해서 도착해야 합니다. 1차원 그래프이기 때문에, 처음에는 DP문제인 줄 알았습니다. 하지만 DP처럼 모든 경우를 탐색할 순 없으며, 그럴 이유도 없습니다. 2022.02.23 - [Algorithm.. 2022. 2. 24.
[탐색/BFS] 백준 1012 유기농 배추 - Python [ Contents ] 1. 문제 (링크 참조) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 2. 문제 풀이 인접한 유기농 배추의 연결 요소 개수를 세는 문제입니다. 2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. BFS(Breath First Sea.. 2022. 2. 23.
[탐색/DFS] 백준 11724 연결 요소의 개수 - Python [ Contents ] 1. 문제 (링크 참조) 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 2. 문제 풀이 연결 요소의 개수를 구하는 문제입니다. 2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 DFS는 인접노드가 없을 때까지, 끝까지 탐색하는 알고리즘입니다. 스택을 이용한 DFS 구현방법과 코드를 알아보겠.. 2022. 2. 23.
[Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 DFS는 인접노드가 없을 때까지, 끝까지 탐색하는 알고리즘입니다. 스택을 이용한 DFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. DFS(Depth First Search) 깊이 우선 탐색(DFS): 방문하지 않은 인접 노드가 없을 때까지 탐색하여 한 곳씩 마무리하는 방식 그래프에서 '노드(Node)'는 원으로 표현된 데이터이며, 노드끼리 연결된 선을 '간선(Edge)'이라고 합니다. 시작 노드를 1번이라고 할 때, DFS는 하나하나 끝까지 탐색합니다. [ 1 -> 2 -> 4 -> 5 -> 6 -> 3 ] (같은 거리 내 인접한 노드는 작은 노드부터 탐색한다고 가정) 2. 스택(Stack)을 이용한 탐색 방식 2022.02.10 - [Algorithm] - [Algorithm] 스택.. 2022. 2. 23.
[탐색/BFS] 백준 2606 바이러스 - Python [ Contents ] 1. 문제 (링크 참조) 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 2. 문제 풀이 1번 컴퓨터와 연결되어 있는 컴퓨터의 수를 구하는 문제입니다. 2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. BFS(Breath Fi.. 2022. 2. 23.
[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. BFS(Breath First Search) 너비 우선 탐색(BFS): 가까운 주변 노드부터 탐색하며 점점 넓혀가는 방식 그래프에서는 원 안의 데이터를 '노드(Node)', 노드끼리 연결된 선을 '간선(Edge)'이라고 합니다. 1을 시작으로 할 때, BFS는 주변 노드부터 탐색합니다. [ 1 -> 2 -> 3 -> 4 -> 5 -> 6 ] (같은 거리 내 인접한 노드는 숫자가 작은 노드부터 탐색한다고 가정) 2. 큐(Queue)를 이용한 탐색 방식 2022.02.10 - [Algorithm] - [Algorithm] 큐(Queue), 선입선출 줄서기 자료구조 [Algori.. 2022. 2. 23.
[정렬/탐색] 백준 18870 좌표 압축 - Python [ Contents ] 1. 문제 (링크 참조) 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 2. 문제 풀이 오름차순으로 정렬한 뒤 최솟값부터 0, 1, 2 ... 매칭하는 문제입니다. 2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학 [Algorithm] 단골 1번 문제, 구현 / 수학 [ Contents ] 1. 구현 단순히 '구현'만 하면 되는 문제 유형입니다. 문제를 이해하고 입력에 맞춰 적절한 출력.. 2022. 2. 22.

티스토리툴바