Algorithm

탐욕 알고리즘은 답을 하나씩 고르는데, 미리정한 기준에 따라서 매번 '가장 좋아 보이는' 답을 선택한다. 탐욕 알고리즘은 동적계획과 마찬가지로 최적화 문제를 푸는데 주로 사용한다. 상대적으로 탐욕 알고리즘이 설계하기 훨씬 쉽다. 동적계획은 재귀 관계식을 세워서 입력사례

부르트 포스 부르트 포스란? brute 동물 force 힘 직관적으로 무식하게 힘을 쓰는 알고리즘이다. 처음부터 끝까지 계산을 다 해나가면서 해를 찾는 방식이다. 문제를 해결하기 위해서, 가능한 모든 경우에 대해 모두 직접 해보는 방법입니다. >ex) 1부터 100까지

미로 퍼즐을 푸는 문제를 풀 때 막따른 길이 나온다면 그길에서 다시 왔던 길로 되돌아가서 하나씩 길이 있는지 확인하면서 넘어가는 문제를 누구나 한번쯤 풀어본 적이 있을 것이다.되추적 알고리즘은 지나왔던 길을 표시해놔서 옳지 않은 길을 체크해놓고 문제를 해결하면서 되돌아

→ 중복되는 연산을 줄이자. 연산 속도와 메모리 공간을 최대한 으로 활용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효울적인 알고리즘을 작성해야 한다.Top down\\탑 다

최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길찾기' 문제라고도 불린다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정럽되어 있다.다익스트라플로이드 워셜벨만 포드 알고리즘그리디 + 다이나믹

비트는 컴퓨터에서 다루는 최소 단위이며, 정수를 이진수로 표현, 비트 연산을 통해 문제를 해결해 나가는 기술을 비트마스크라고 한다.예를 들어서 10개의 스위치가 있다고 가정하면이런식으로 정수형으로 나타낼 수 있다.비트 마스크는비트 연산을 통한 삽입, 삭제, 조회 등이

서로소 집합, 분리 집합 이란 서로 공통된 원소를 가지고 있지 않은 두개 이상의 집합을 말한다.트리에 속해있는 루트 노드를 그 집합을 대표하는 노드로 두고 한 원소가 어떤 집합에 속해있는지 확인하는 과정을 해당 원소가 자신이 속한 루트 노드가 누구인지 확인하는 과정을

배낭 문제는 최대한의 값어치를 낼 수 있게 제한 된 무게만큼의 물건을 가방에 넣는 문제이다. 예를 들어 limit = 10 이고 물건의 갯수가 3일 때,어떻게 문제를 해결할 수 있을까?Greedy (Fraction knapsack)가장 값어치가 비싼 물건을 담는다. 중

원소가 n개인 수열에서 부분 원소를 추출하여 만든 부분 수열 중에 원소가 오름차순으로 정렬된 수열의 길이를 LIS라고 한다.예를 들어, 1 5 4 3 2 6 7 1 이런 수열이 있다.위 수열의 부분 수열은 길이가 1짜리1, 5, 4, 3, 2, 1, ...길이 2짜리

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 푸는 것 입니다.예를 들어 일렬로 나열된 숫자 중에서 키가 3이상인 값을 갖는 최소 인덱스 값을 계산해야 한다고 가정해봅시다. 각각의 크기는 크기별로 정렬되어 있고, 만약 크기가 3이 넘는 사람은 키가 크다는 것이 증