'알고리즘/🗂️ 정리' 카테고리의 글 목록

😺 범위를 벗어날 경우 반대방향으로 이동하는 알고리즘 😺

2024.04.09

알고리즘을 풀면서 기억해두면 좋을만한 코드를 기록한다. 😺 상황 설명 고양이가 상하좌우로 L만큼 이동할 때 범위 밖으로 이동한다면 이동방향을 반대로 바꾼 후 이동을 계속 진행한다. 만약 L의 값이 10억일 때 for문을 10억 번 돌려 고양이가 이동하게 되는 위치를 정하는 것은 비효율적이며 시간초과가 발생한다. 고양이의 위치를 반복문이 아닌 식을 이용해서 구해보자. 🕹️ 구현 방법 🔹 오른쪽으로 이동할 때 4x6의 판에서 현재 고양이는 (2, 2)에 위치해 있다. 고양이가 만약 3칸 이동하면 범위에 벗어나지 않는다. 하지만 오른쪽으로 7칸 이동할 때 범위를 벗어나게 된다. 다음 이동하려는 칸이 범위에 벗어난다면 방향을 반대로 바꿔 이동하고, 최종적으로 (2, 1)에 위치하게 된다. 12칸 이동하면 동일한..

알고리즘/🗂️ 정리

🐌 달팽이 이동 효율적인 코드 🐌

2024.03.30

달팽이 이동을 효율적으로 작성한 코드가 있어서 기록한다. 우선 격자의 한 변은 무조건 홀수다. 안 -> 밖으로 이동하는 방향과 밖 -> 안으로 이동하는 방향을 한 번에 저장하는 로직이다. 규칙 찾기 달팽이 이동하는 규칙을 찾아보면 현재 방향이 만약 위 또는 아래일 때마다 이동하는 횟수가 1씩 증가한다. 안 ➔ 밖으로 이동하는 경우를 보면, ⬆︎ ➡︎ 로 이동할 때는 1, 3, 5 ... 칸씩 이동하고, ⬇︎ ⬅︎ 로 이동할 때는 2, 4, 6 ... 칸씩 이동한다. (0, 0)칸으로 향해 가는 마지막 ⬆︎는 짝수 칸만큼 이동하지만 어차피 (0, 0)에서 끝나기 때문에 break하면 된다. 밖 ➔ 안으로 이동하는 달팽이 모양은 위와 반대로 생각하면 되기 때문에 방향만 바꿔주면 된다. 코드 public st..

알고리즘/🗂️ 정리

LCS (최장 공통 부분 수열)

2024.03.11

코테 보다가 나온 것이기에 정리한다... LCS (Longest Common Subsequence)는 주어진 여러 개의 수열 중에서 모두의 부분수열이 되는 수열들 중 가장 긴 것을 찾는 것이다. 예시를 보자면, ACAYKP의 부분수열은 {A}, {C}, {A}, {Y}, {K}, {P}, {A, C}, {A, A}, {A, Y}, ... {A, C, A, Y, K, P} 이고, CAPCAK의 부분수열은 {C}, {A}, {P}, {C}, {A}, {K}, {C, A}, {C, P}, {C, C}, ... {C, A, P, C, A, K}이 있는데 각각의 부분수열 중에서 서로 같은 부분수열이 있을 것이다. 그중 가장 긴 것을 찾으면 되는데 위의 예시의 답은 길이가 4인 {A, C, A, K} 이다. 대표적..

알고리즘/🗂️ 정리

Topological Sort (위상정렬)

2024.02.27

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

알고리즘/🗂️ 정리

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가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오..

알고리즘/🗂️ 정리

MST(최소신장트리) - 크루스칼 & 프림 알고리즘

2023.10.23

최소신장트리(MST / Minimum Spanning Tree)는 방향성이 없는 가중 그래프에서 간선의 가중치의 합이 최소인 신장 트리이다. 🕹️ 크루스칼 알고리즘 & 프림 알고리즘 과정 🔹 크루스칼 알고리즘 : 간선 중심으로 최소 신장 트리 구하기 (간선의 개수가 적다면 프림보다 효율적 !) 간선들의 가중치를 오름차순으로 정렬한 후 가중치가 낮은 간선부터 선택한다. 선택한 간선으로 인해 사이클이 형성된다면 다음 간선으로 넘어가고, 사이클이 형성되지 않는다면 해당 간선을 선택한다. ➔ 사이클이 형성되는지 파악하기 위해 Union-Find 연산을 진행한다. 정점이 N개인 그래프일 때, N-1개의 간선을 선택했다면 반복문을 종료한다. 🔹 프림 알고리즘 : 정점 중심으로 최소 신장 트리 구하기 (정점의 개수가..

티스토리툴바