알고리즘

DP - Dynamic Programming (동적 계획법) 복잡한 문제를 여러 개의 간단한 무제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 원리 큰문제를 작은 문제로 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들은 결괏값은 항상 같아야함 메모이제이션(Memoization)모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재상요할 때는 이 DP 테이블을 이용 톱다운 방식과 바텀 업 방식으로 구현 메모제이션 원리 피보나치 수열 구하는 공식은 f(n) = f(n-1) + f(n-2)으로 n번째 수열은 n-1번째 수열과 n-2번재 수열을 더한 값이다. 즉, 5번째 피보나치 수열은 4번째 와 3번째를 더한 값이고, 작은 문제로 나누면 4번째와 3번째..

시간 복잡도 시간 복잡도란 알고리즘이 주어진 문제를 해결하기 위한 연산 횟수 시간 복잡도 유형 1.빅-오메가 Ω(n) : 최선일 때(best case)의 연산 횟수를 나타내는 표기법 가장 빠른 케이스, 어떤 식의 최고 차수 2.빅-세타 𝚯(n) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법, 빅-오, 빅-오메가를 만족한느 교집합 평균 실행시간 3.빅-오 O(n) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 가장 느린 케이스 상수는 무시 혹은 1로 통일 상한선을 기준으로 하여 모든 경우의 수를 포함 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋은 이유 프로그램은 다양한 테스트 케이스를 수행하여 모든 케이스를 만족할만한 케이스를 염두해 둬야 하는데 그 경우가..

문제 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이..

소수를 구하는 알고리즘 - 에라토스테네스의 체 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법 알고리즘[편집] 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간..

DFS( Depth first Search) - 깊이 우선 탐색 그래프 완전 탐색 기법 중 하나로, 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 기능 특징 시간 복잡도(노드 수 : V, 에지 수 : E) 그래프 완전 탐색 재귀함수, Stack(LIFO) 사용 O(V+E) DFS 원리 시작할 노드를 정한 후 사용할 자료구조 초기화 Stack에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입 Stack 자료구조에 값이 없을 때까지 반복 DFS 구현 방법 두 가지 재귀 1 -> 2 -> 5 -> 6 -> 3 -> 4 -> 스택 1 -> 3 -> 4 -> 6 -> 2 -> 5 -> * 재귀의 ..

문제 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 2 이상 100 이하인 자연수입니다. wires는 길이가 n-1인 정수형 2차원 배열입니다. 입출력 예 n wires result 9 [[1,3],[2,3],[3,4],[4,5],[4,..

해시 (Hash) Hash는 데이터를 저장하는 자료 구조 중 하나로, 특정한 함수를 사용하여 데이터를 일정한 크기의 고정된 값으로 변환하는 과정을 말합니다. 이렇게 변환된 값은 보통 “해시 코드” or “해시 값” 이라고 불립니다. 해시 함수는 임의의 크기의 데이터를 고정된 크기의 데이터로 변환하는 특징이 있습니다. 해시 함수(Hash Fuction) 해시 함수는 주어진 입력에 대해 항상 동일한 해시 코드를 생성하며, 입력 데이터가 조금만 다르더라도 해시 코드가 크게 달라져야 합니다. 이러한 특성을 가진 해시 함수를 “고르게 분포되었다” 고 말합니다. 해시 함수 종류 MD5, SHA-1, SHA-256 등 특정한 용도나 특성에 맞게 다양한 종류가 존재한다. 그 중 3가지 만 간략하게 설명하겠습니다. 1...