[Kotlin] 코딩 테스트 대비 주요 알고리즘 & 함수 정리

코틀린 코테를 대비한 주요 알고리즘 & 함수를 정리합니다. 입출력빠른 입력을 위해서 System.`in`.bufferdReader()를 활용합니다.StringBuilder 와 bufferedWriter를 활용해서 빠른 출력을 사용할 수 있습니다.fun main() = with(System.`in`.bufferedReader()) { val integer = readLine().toInt() // 공백 기준으로 분리 val nums = readLine() .split(" ") .map { it.toInt() } print(integer) print(nums) val sb = StringBuilder() sb.append(5) sb.appe..

• format_list_bulleted Algorithm
• · 2024. 8. 25.
• textsms

투 포인터(Two Pointer) 알고리즘

투 포인터두 개의 포인터를 사용하여 문자열이나 정렬 된 배열에서 원하는 값을 찾거나 구간 합을 구할 때 사용하는 알고리즘입니다.병합정렬(merge sort)의 counquer 영역(인접한 부분배열끼리 정렬하여 합침) 기초가 되는 알고리즘입니다.리스트에 순차적으로 접근해야 할 때, 두 개의 점의 위치를 기록하면서 처리합니다.슬라이딩 윈도우와 유사하나, 고정 된 구간이 아닌 가변적인 구간을 탐색한다는 차이가 있습니다. c.f> 슬라이딩 윈도우?투 포인터처럼 구간을 흝으면서 지나간다는 공통점이 있으나, 슬라이딩 윈도우는 어느 순간에도 구간의 넓이가 동일하다는 차이가 있습니다. 투 포인터 적용하기두 수의 합이 target을 만족하는 두 수를 찾는 문제가 주어졌을 때를 가정하여 투 포인터를 적용해 보겠습니다.ta..

• format_list_bulleted Algorithm
• · 2024. 6. 9.
• textsms

최소 신장 트리(MST)

Minimum Spanning Tree : 최소 신장 트리사용된 간선들의 가중치 합이 최소인 트리를 뜻합니다.그래프 내의 모든 정점을 포함하는 트리입니다.최소 신장 트리라고 하며, 그래프의 최소 연결 부분 그래프입니다.간선의 수가 가장 적음n개의 정점을 가지는 그래프는 (n-1)개의 간선으로 연결 됨그래프에서 일부 간선을 선택해서 만드는 트리입니다.최소 신장 트리의 특징DFS, BFS를 사용하여 그래프에서 신장 트리를 탐색할 수 있습니다.하나의 그래프에는 많은 신장 트리가 존재하며, 그 중 가장 작은 가중치의 트리가 최소 신장 트리입니다.사이클이 포함되어서는 안됩니다.이전의 신장 트리와는 상관없이 무조건 최소 간선만을 선택합니다.최소 신장 트리의 사용 사례도로 건설, 전기 회로, 통신, 배관 등 최소의 ..

• format_list_bulleted Algorithm
• · 2024. 5. 12.
• textsms

다익스트라 알고리즘

다익스트라 알고리즘다익스트라 알고리즘은 최단거리를 구하는 알고리즘입니다.다익스트라 알고리즘을 사용하면, 하나의 노드로부터 최단 거리에 있는 다른 노드를 탐색할 수 있습니다.목적지와 가중치를 저장하여 가장 적은 가중치의 경로를 탐색할 수 있으며, 지하철 노선 탐색을 예로 들 수 있습니다.최단 거리를 구할 노드로부터 거리가 입력된 노드를 돌아가면서 더 거리가 짧은 값이 나오면 값을 새로 갱신합니다. 알고리즘 구성 각 노드까지의 거리를 최대값으로 초기화하고, 해당 노드로 이동할 수 있는 더 작은 값일 나올 때 값을 갱신합니다.INF = 1e8distance = [INF] * (n+1) INF는 정수의 최대값이며, 1~n까지의 거리값을 저장하기 위해서 n+1로 초기화합니다. 다음으로는 도착 노드와 가중치 값을 ..

• format_list_bulleted Algorithm
• · 2024. 1. 7.
• textsms

[Python] 코딩 테스트 대비 주요 알고리즘&함수 정리

코테를 준비하면서 자주 사용하는 알고리즘 & 함수를 정리합니다. Queue 선입 선출의 구조로 queue 라이브러리를 사용합니다. import queue data = queue.Queue() print(type(data)) queue에 데이터 넣기 data.put(2) data.put(3) data.put(4) 데이터 출력 print(data.get()) print(data.get()) print(data.get()) Stack 후입 선출 구조로 별도 라이브러리 없이 파이썬의 리스트를 사용합니다. stack = [] 데이터 넣기 stack.append(2) stack.append(3) stack.append(4) 데이터 출력 print(stack.pop()) print(stack.pop()) print(..

• format_list_bulleted Algorithm
• · 2023. 9. 20.
• textsms

[알고리즘] FloodFill(SeedFill) 플러드 필 알고리즘

플러드 필 알고리즘 flood fill 혹은 seed fill이라고 불리는 알고리즘이다. 다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘이며, 채우기 도구나 지뢰 찾기 게임에서 사용된다. 일반적으로 시작 칸을 중심으로 상하좌우로 연결 된 모든 칸을 방문하여 색을 칠하는 구조이다. 여러가지 구현 방법이 있지만, 큐나 스택의 자료구조를 사용하는 것이 일반적이다. 4방향과 8방향으로 구분되며, 알고리즘 문제에서는 주로 4방향 문제를 주어진다. (8 방향의 경우, 상하좌우 + 대각선을 탐색한다) 모든 정점에서 dfs나 bfs 탐색을 통해 연결요소가 몇개인지 파악할 수 있다. 구현 https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머..

• format_list_bulleted Algorithm
• · 2023. 9. 17.
• textsms