'알고리즘' 카테고리의 글 목록 (3 Page)

Topological Sort (위상정렬)

2024.02.27

순서가 정해져있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 예를 들어보면, 위와 같은 커리큘럼에서 알고리즘을 수강하고자 하면 선수과목들을 수강한 후에 들어야한다고 했을 때, 이산수학 → C프로그래밍 → 객체지향프로그래밍 → 자료구조 → 알고리즘 순서로 수강신청을 하면 된다. 이 외에도 여러 개의 순서가 존재할 수 있다. 선후 관계가 명확했을 때 순서를 결정하여 정렬하는 알고리즘인 것이다. 🔹 위상 정렬 특징 사이클이 발생하지 않는 방향성 그래프에서의 정렬 👉 사이클이 있다면 위상 정렬 수행 X (시작점을 찾을 수 없으므로) 큐 또는 스택 사용 진입차수 고려 🕹️ 알고리즘 과정 진입 차수는 정점에 들어오는 간선 수이고, 빨간색 숫자는 진입차수를 나타낸 것이다. 진입차수..

알고리즘/BOJ

[BOJ] 21609 상어 중학교 - Java

2024.02.26

✨ 구현 & BFS https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 📍 고려해야할 점 그룹에 속하는 블록의 조건 일반 블록이 적어도 하나 이상 일반 블록의 색은 모두 같아야함 검은색 블록 포함 X 무지개색 블록은 몇개든 상관 X 블록의 개수는 2개 이상 블록 그룹의 기준 블록 = 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록. 그러한 블록이 여러 개이면 열의 번호가 가장 작은 블록 .. 오토플레이 기능 ➔ 블록 그룹이 없을 때..

알고리즘/🗂️ 정리

Simulation - 2차원 달팽이 배열 🐌

2024.02.08

2차원 배열에서 달팽이로 이동하는 방법을 정리한다. 🐌 시작하는 곳에서 상하좌우 방향 (반시계 또는 시계방향)에 따라 달팽이 배열의 형태가 달라진다. 배열 중앙 (N/2, N/2) 에서부터 시작 중앙(N/2, N/2)에서부터 시작해야하므로 N이 홀수이어야 한다. ←, ↓일 때는 1, 3, 5, 7 .... 만큼 이동하는 칸이 증가한다. →, ↑일 때는 2, 4, 6, 8 .... 만큼 이동하는 칸이 증가한다. 2번 방향을 바꿀 때마다 이동하는 칸을 증가시킨다. 👉 moveCnt++ 현재는 중앙에서 왼쪽방향으로 시작해서 반시계방향으로 돌고 있지만, 왼쪽 외에 상, 하, 우 방향으로 시작해서 반시계 또는 시계방향으로 가는 것도 동일한 방법으로 진행하면 된다. 방향을 두 개씩 짝만 지어주면 가능 ! impor..

알고리즘/🗂️ 정리

DP - Knapsack (배낭문제)

2024.02.05

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 🕹️ Knapsack 알고리즘 과정 DP 문제 중 하나로, 배낭의 크기 k와 n개의 물건의 무게(w)와 가치(v)가 주어졌을 때, 가방에 물건을 k에 넘지 않도록 넣고 최대 가치의 합을 구하는 문제이다. ex) 배낭의 크기는 k이고, 5개의 물건의 무게와 가치가 다음과 같이 주어졌을 때, 최대 가치의 합을 구하기 물건 1 : w =..

알고리즘/🗂️ 정리

LIS (최장증가부분수열)

2023.12.07

LIS(Longest Increasing Subsequence)는 원소가 n개인 배열에서 일부 원소를 골라내어 만든 부분 수열 중에서 모든 원소들이 이전 원소보다 크다는 조건을 만족하고 그 길이가 최대인 부분 수열이다. 예시를 들어보자. A = {10, 20, 10, 30, 20, 50}인 수열에서 원소가 증가하는 부분 수열은 {10, 20}, {20, 30, 50}, {10, 30, 50} 등이 있는데, 그 중 길이가 최대인 부분 수열은 길이가 4인 {10, 20, 30, 50}이다. 대표 문제는 아래와 같다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오..

알고리즘/BOJ

[BOJ] 1018 체스판 다시 칠하기 - Java

2023.12.05

✨ 브루트포스 ➔ 완전탐색 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 📍 고려해야할 점 주어진 체스판을 8x8 크기의 체스판으로 만들어야 한다. 흰색과 검은색이 번갈아서 칠해져있어야 한다. (0, 0)이 검은색인 경우와 흰색인 경우를 나누어서 구한다. 가로, 세로 인덱스 값의 합이 짝수, 홀수에 따라 흰색인지 검은색인지 구분해서 구한다. 🕹️ 풀이 과정 1️⃣ 주어진 체스판을 8x8 크기로 다시 만들어야 하기 때문에 copy배열을 ..

알고리즘/BOJ

[BOJ] 1504 특정한 최단 경로 - Java

2023.12.05

✨ 다익스트라 ➔ 최단경로 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 📍 고려해야할 점 방향이 없는 그래프이다. 1번 정점에서 N번 정점으로 최단거리로 이동한다. 주어진 두 정점을 반드시 거쳐야 한다. 두 정점이 v1, v2라면 1 ➔ v1 ➔ v2 ➔ N 또는 1 ➔ v2 ➔ v1 ➔ N 두가지 방법으로 이동할 수 있다. 🕹️ 풀이 방법 1️⃣ 노드에 대한 정보 (이동해야하는 노드 = v, 해..

알고리즘/BOJ

[BOJ] 18352 특정 거리의 도시 찾기 - Java

2023.12.04

✨ 그래프 탐색 ✨ BFS, 다익스트라 ➔ 최단 경로 찾기 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 📍 고려해야할 점 출발 도시에 대한 정보가 존재한다. 최단 거리에 대한 정보가 존재한다. ➔ 해당하는 최단 거리인 도시를 찾으면 된다. 하나의 도시에서 다른 모든 도시까지의 최단거리를 구해야하기 때문에 다익스트라 알고리즘을 사용한다. 도시간의 거리가 모두 1이기 때문..

티스토리툴바