algorithm

재귀호출 1. 알고리즘이란? 알고리즘 : 계산을(컴퓨터를) 통하여 문제를 해결하는 방법 의사코드 : 문제를 해결하고자 하는 방법과 의도를 표한 코드 알고리즘의 성질 1.유한성 : 유한한 횟수를 거치고 종료되어야함. 즉, 무한루프는 알고리즘이 아니다. 2.명확성 : 알

문제 : n개의 숫자가 차례대로 주어질 때, 매 순간마다 “지금까지 입력된 숫자들 중에서 k번째로 작은 수”를 반환하는 프로그램을 작성하세요.프로그램의 입력으로는 첫째줄에 n과 k가 입력되고, 둘째줄에 n개의 숫자가 차례대로 주어집니다.코드 : 문제 : 입력으로 n개의

1. 문제 해결 절차 문제를 정확히 이해한다. 문제를 해결하는 알고리즘을 개발한다. 알고리즘이 문제를 해결한다는 것을 증명한다. 알고리즘이 제한시간내에 동작한다는 것을 보인다.(효과성) 알고리즘을 코드로 작성한다. 디버깅을 할 필요가 없어야한다. 왜냐 3, 4번에서 다

알고리즘 실습

재귀함수를 디자인하기위한 3가지 단계1) 함수의 정의를 명확히 한다.2) 기저 조건에서 함수가 제대로 동작하게 작성한다.3) 함수가 제대로 동작한다고 가정하고 함수를 완성한다.사실 퀵정렬도 분할정복법 중 하나이다. 분할정복법은 크게 3가지로 나눌 수 있다.문제를 소문제

알고리즘 실습

순간의 최적의 선택이 궁극적으로 최적의 선택이다.단순한 방법도 문제 풀이에는 충분하다.탐욕적 기법으로 만드는 방법은 간단하지만 탐욕적 기법으로 방법을 만드는 것은 결코 쉬운일이 아니다!가설이 아닐 때의 상황에서 모순을 보여줌으로써 오히려 가설이 맞다는 것을 증명하는 역

탐욕적 기법 알고리즘 실습

1. 자료구조의 의미 자료구조란 : 자료를 저장하는 구조. 여러가지 종류가 있으며 저장된 자료에 대해 접근하는 방법등의 차이가 존재한다. 프로그램에 필요한 자료들을 효율적으로 담기 위해 공부. 프로그램에서 특정 알고리즘을 구현하기 위해 적절한 자료구조를 사용해야 좋은

문제 : machine.addNumber(x) : 정수 x를 최댓값 기계 machine에 추가합니다.machine.removeNumber(x) : 정수 x를 최댓값 기계 machine으로부터 제거합니다. 만약 정수 x가 최댓값 기계 내에 없다면 아무 일도 일어나지 않습

스택과 큐 자료구조의 예시 큐는 head 이상 rear 미만의 index data를 갖고있고 선입선출의 자료구조를 갖고있다. 큐에서 push는 rear 위치에

1. 스택구현하기 문제 스택에서 정수를 제거 스택의 size 출력 스택이 비어있는지 여부 출력 스택의 꼭대기 값 출력 아직 2%씩 완성도가 부족하다... 2. 큐 구현하기 큐에서 정수를 제거 큐의 size 출력 큐가 비어있는지 여부 출력 큐의 head 값 출력 큐의

트리 1. 비선형구조와 트리 선형 구조는 자료가 순서를 가지고 연속되어있음 비선형 구조는 선형 구조에 해당하지 않는 자료구조(ex 트리, 그래프) 그런데 사실 그래프 > 트리로 그래프가 포괄하는 개념임 경로란 어떤 정점에서 다른 정점으로 이동하기 위해 거치는 모든

1. 이진트리 순회 구현하기 1-1. 이진트리 순회 구현하기 2. 이진트리 만들기

출력 연산 시 가장 우선순위가 높은 원소를 출력한다.이때 배열로 구현한다면 시간복잡도에 있어 매우 불리하다.그래서 고안된 방법이 바로 완전이진트리(힙)이다.Max Heap : 부모노드는 항상 자식 노드보다 큰 값을 갖고있다.Min Heap : 부모노드는 항상 자식 노드

입력 : 첫 번째 줄에 힙이 수행할 명령의 수를 나타내는 정수 n을 입력합니다. ( 1≤n≤540000)두 번째 줄부터 n개의 줄에 걸쳐 수행할 명령을 입력합니다. 명령의 종류는 다음과 같습니다.0 x : 정수 x를 힙에 입력 (0≤x≤5400000 \\le x \\l

복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 푸는 방법. 이떄 하위문제의 답을 저장하여 중복 연산을 하지 않는다.다음과 같은 문제를 풀 때fibonacci 딕셔너리에 저장해둔 값을 cache(캐시)라고 하고 캐시에 저장되어있는 값을 꺼내서 쓰는 것을 memoiz

1. 정렬 1) 선택 정렬 📝 정의: 가장 작은 것을 선택하여 가장 앞으로 보낸다. 📋 예시) 1,5,4,7,3,6,2,10,9,8 를 오름차순으로 정렬하시오. 이때 가장 앞에서부터 순서대로 1,5,4,7,3,6,2,10,9,8 중 가장 작은 1을 index 0

탐색 너비 우선 탐색 📝 정의 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. "특히 맹목적인 탐색"을 하고자 할 때 사용할 수 있는 탐색 기법이다. 🛠 특징 너비 우선 탐색은 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야할 때

하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다. 한 번 푼 것을 여러 번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법이기도 하다.일반적으로 상당수 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 갖고 있다. 다만 분할 정복 기법은 "정렬" 과 같은 몇몇 요

Dijkstra 최단 경로 탐색 알고리즘 📝 정의 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다만 이때, 음의 간선을 포함할 수 없다. 물론 현실 세계에서는 음의 간선이 존재하지 않기 때문에 다익스트라는 현실 세계에

Floyd Warshall Algorithm 📝 정의 dijkstra 알고리즘은 한 정점에서 다른 모든 정점의 최단 경로를 구할 때 사용하여 네비게이션 같은 곳에 자주 사용된다고 하였다. 하지만 모든 정점에서 모든 정점으로의 최단 경로를 구할 땐 플로이드 와샬 알고리

Topology Sort 📝 정의 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 예를 들어 다음과 같이 어떠한 일련의 순서가 정해져 있는 task 가 있다고 가정할 때, 이는 조건으로 해석할 수 있다. 🛠 특

Strongly Connected Component 📝 정의 그래프 안에서 강하게 결합된 정접 집합을 뜻한다. 서로 긴밀하게 연결되어 있다고 하여 강한 결합 요소라고 말한다. 🛠 특징 SCC 라고도 불린다. SCC 는 같은 SCC 에 속하는 두 정점은 서로 도달

Network Flow 📝 정의 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는가를 측정하는 알고리즘. 네트워크 플로우는 최대 유량문제를 해결하기 위한 알고리즘이다. 그럼 유량이 뭘까? 🛠 특징 교통 체증, 네트워크 데이터 전송 등 다양한 분야에

네트워크 플로우(https://velog.io/@jeong_woo/%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-%ED%94%8C%EB%A1%9C%EC%9A%B0A 집단이 B 집단을 선택하는 방법에 대한 알고리즘이다.이분 매칭은 네트워크 플

KMP 알고리즘은 대표적인 문자열 매칭 알고리즘이다. 기본적으로 문자열 매칭 알고리즘이란 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘이다.이는, 우리가 크롬에나 파폭에서 ctrl + f 를 눌러 글자 찾기에도 해당 알고리즘이 다 들어가 있는 것이다

특이한 문자열 매칭 알고리즘이다. 항상 빠르지는 않지만 일반적인 경우 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘이다.문자열에 해싱 기법을 사용하여 해시 값으로 비교하는 알고리즘이다.문자열의 해시 값을 비교하여 그 일치 여부를 검사하는 알고리즘이다는 것이다.앞서