[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

CS - 자료구조

Array(List)의 특징과 장단점 Array 배열을 활용하면 순차적으로 데이터를 저장한다는 특징이 있습니다. 데이터에 순서가 있기 때문에 0부터 시작하는 index가 존재하며, index를 사용해 특정 요소를 찾고 수정이 가능합니다. 순차적으로 존재하는 데이터의 중간에 요소가 삽입되거나 삭제되는 경우 그 뒤의 모든 요소들이 한 칸씩 뒤로 밀리게 됩니다. 순서가 중요한 자료구조에서 순서를 보장해주는 Array를 활용하는 것이 좋습니다. Kotlin에서의 Array와 List array는 사이즈가 할당되어져 있고, Mutable 타입이므로 수정이 가능합니다. 인덱스를 참조해서 값을 수정할 수 있다는 장점이 있습니다. 리스트는 순서가 있고, 사이즈는 자동할당되며 대부분 수정이 불가능한 ImmutableLi..

• format_list_bulleted Computer Science/자료구조
• · 2023. 12. 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

[알고리즘] 에라토스테네스의 체

에라토스테네스의 체 소수를 찾을 때 가장 적은 시간 복잡도를 소요하는 알고리즘이다. 여러 개의 수가 소수인지 아닌지를 판별하며, N보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 에라토스테네스보다 시간 복잡도가 높은 알고리즘과 비교하여 해당 알고리즘의 이점을 파악한다. 일반적인 소수 찾기 알고리즘 소수의 판별법을 사용한다. 소수란 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수이다. 6의 경우 1,2,3,5을 약수를 가지므로 소수가 아니고, 7의 경우 1,7만을 약수로 가지므로 소수라고 할 수 있다. 가장 간단한 소수 판별법은 아래와 같으며, 어떤 수의 소수를 찾을 때 시간 복잡도가 O(n)이 된다. # 가장 간단한 소수 판별법 # 모든 수를 나누어서 소..

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

[알고리즘] 그래프 - 위상 정렬(Topology Sort)

위상 정렬 알고리즘 (Topology Sort) 위상 정렬이란 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스리지 않도록 순서대로 나열하는 것이다. ex> 선수 과목을 고려한 학습 순서 결정 (우선순위) 선수 과목구조란 여러 수강 과목이 존재하는 경우 "c언어 과목을 들어야 알고리즘 강의를 수강할 수 있다" 라는 규칙을 지켜서 수강 신청을 하는 것을 말한다. 즉 어떤 그래프를 위상 정렬하면 그 결과로 정점들을 원소로 가지는 위상적 순서대로 정렬된 배열이 된다. 진입 차수 : 특정 노드로 들어오는 간선의 수 진출 차수 : 특정 노드에서 나가는 간선의 수 큐를 이용한 위상 정렬 알고리즘 파이썬을 통해서 위상정렬을 구현할 경우 큐를 활용한다. 위상 정렬 알고리즘의 규칙은 아래와 같다. 1. 모든 정점을..

• format_list_bulleted Algorithm
• · 2023. 5. 10.
• textsms