알고리즘

1차원 배열이 있고, 배열 안에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 설정한다.2개의 포인터를 조작해가면서 원하는 것을 얻는 형태의 알고리즘.투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.배열에서 연속된 데이터 구간에서 처리하기를 원하거나

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것그래프 완전 탐색 기법 중 하나그래프 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동해 다시 탐색을 수행하는 알고리즘미로를 탐색할 때 한 방향

너비 우선 탐색 = breadth-first search그래프를 완전 탐색하는 방법 중 하나시작 노드에서 출발해 업로드중..

데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식버블정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법루프를 돌면서 인접한 데이터 간의 swap연산으로 정렬 O(n^2) \-> 다른 정렬 알고리즘보다 속도가 느린편 비교 연산이 필요한 루프

대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법구현이 복잡O(n^2) : 비효율적 \-> 코테에서는 많이 사용하지않음최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap남은 정렬 부분에서 최솟값 또는 최댓값

이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식구현하기 쉽다.O(n^2) : 느린편선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입!현재 index에 있는 데이터 값을 선택한다현재 선택한 데이터가 정렬된 데이터 범

가장 유명한 정렬 알고리즘중 하나인 퀵정렬에 대해 알아보자 분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요

병합정렬은 코테의 정렬 관련 문제에서 자주 등장한다!특히 2개의 그룹을 병합하는 원리는 꼭 숙지해야한다. 분할 정복 방식을 사용해, 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문

값을 비교하지 않는 특이한 정렬값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘O(kn)k = 데이터의 자릿수\-> 예) 234, 123 비교시 4와3, 3과 2, 2와 1만 비교10개

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이며 대상 데이터 탐색타깃 데이터 탐색중앙값 비교를 통한 대상 축소 방식O(logN)ex) 맨 처음 원소의 개수가 8에서 4, 2, 1

동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘해 선택 : 현재 상

주어진 배열의 값 범위가 작은 경우 빠른 속도를 갖는 정렬 알고리즘이다. 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행한다.입력 배열의 최댓값, Counting Array 생성원소의 누적합을 구하기 위한 Counting Array 생성을 위

노드 : 정점 , 무엇이든 표시할 수 있다.에지 : 노드 간 연결선그래프를 구현하는 3가지 방법이 있다.에지를 중심으로 그래프를 표현배열에 출발 노드, 도착 노드를 저장하여 에지를 표현 또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 에지르 표현가중치가

일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어있는 알고리즘그래프 알고리즘의 일종으로서 상호 배타적 집합, Disjoint-set 이라고도 한다.

기본적으로 그리디한 선택을 바탕으로 알고리즘을 진행한다.가장 적은 비용으로 모든 노드를 연결하기위해 사용하는 알고리즘 최소비용 신장트리를 만들기 위한 대표적인 알고리즘 ex) 여러개의 도시가 있을때 각 도시를 도로를 이용해 연결하려 할 때 비용을 최소한으로 하기위한 알

위상어떤 사물이 다른 사물과의 관계 속에서 가지는 위치나 양상Directed Acyclic Graph (DAG)는 사이클이 없는 방향 그래프입니다.DAG는 이벤트 간의 우선순위를 나타내기 위해 주로 사용됩니다.사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 순

복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법특정한 알고리즘이 아닌 하나의 문제해결 패러다임왜 DP를 사용할까? 사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다.

LCS는 문자열을 이용한 대표적인 동적 계획법 문제입니다.LCS개념 혹은 풀이접근법을 공부하지않으면 이해하기 어려울 수 있기때문에, 이번시간에 공부해봅시다.우선, 2개의 문자열이 주어집니다. 이 둘의 공통된 가장 긴 문자열을 찾으면 그게 LCS입니다.공통된 문자열은 서

도시들이 있고, 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌고 다시 출발도시로 돌아왔을 때 드는 최소 비용을 구하는 문제컴퓨터 과학 분야에서 가장 중요하게 취급되는 문제 중 하나출발도시를 정해주지 않는데, 사실 어

컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다.이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트마스크라고 한다.더 빠른 수행시간더 간결한 코드더 적은 메모리 사용시프트연산시 타입의 범위를 넘어가는 overflow, underflow를 매우

java에서는 변환에 사용할 수 있는 메소드 제공하고있고, 알고리즘인가 싶겠지만(?) 코테에 꽤 자주나오는걸로 알고있어서 따로 정리한다.10진법에서 N진법으로, N진법에서 10진법으로 변환하는 방법을 알아보자.수학으로 생각하면 10진법으로 표기된 숫자를 N으로 나누어

가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법즉, 무식하게 가능한 거 다 해보겠다는 방법이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.

시뮬레이션, 구현, 완전 탐색은 서로 유사한 점이 많다.일련의 명령에 따라서 개체를 차례대로 이동시키는 것풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제실수 연산을 다루고 특정 소수점 자리까지 출력해야 하는

조합은 수학적으로 위와같이 표기한다.이는 n개 중에서 r개를 뽑는 경우의 수를 뜻한다.조합과 비교되는 순열은 위와같이 표기하며, 이는 n개 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 말한다.순열과 조합의 차이는 순서의 고려 유무이다.즉, 조합에서는 1,2,3과

n개의 숫자 중에서 r개의 수를 순서 없이 뽑는 경우예를 들어 1, 2, 3 이란 숫자 배열에서 2개의 수를 순서 없이 뽑으면이다.nCr =n−1Cr−1+n−1Cr하나의 원소를 이미 선택하고, 나머지 원소들에서 남은 것을 선택하는 경우의 수 + 하나의 원소를 선택하지