동적 계획법, DP란? 다이나믹 프로그래밍이란, 하나의 문제를 여러 작은 파트로 나누어서 그 결과를 저장하여 하나의 문제를 해결하기 위한 알고리즘이 아닌 문제해결 방식 중 하나이다. 일반적인 재귀 방식과 매우 유사한데, 큰 차이점은 일반적으로 재귀를 단순히 사용할시 동일한 작은 문제들이 여러번 반복 되어 비 효율적인 계산이 될 수 있다는 것이다. DP를 사용하기 위해서는? 겹치는 부분, 즉 문제에서 동일한 반복이 일어나는지 파악해야한다. 또한, 부분 문제의 최적 결과 값을 사용해 문제의 최적 결과를 낼 수 있어야 한다. DP는 부분 문제의 결과를 저장하여 재 계산하지 않아야 하는데, 부분 문제가 반복적으로 나타나지 않는다면 재사용이 불가함으로 사용할 수 없다. 앞에서 말했듯이, DP는 알고리즘이 아닌 문..
프로그래머스 알고리즘
이진탐색 (이분탐색) 분할정복 분할정복 알고리즘은 문제를 나눌 수 없을 때까지 나누어서 각각 푼 후에 다시 병합하여 답을 얻는 알고리즘이다. 순환적으로 문제를 푸는 하향식 접근 방법이다. 분할 → 해결 → 결합의 단계를 거친다. 관련된 방법으로는 이진탐색, 합병정렬, 퀵 정렬, 선택 문제 등이 있다. 💡 이진 탐색이란, 원하는 값 k을 찾는 과정 처음 범위는 인덱스 0부터 끝까지 탐색한다. 이 때 중간 인덱스를 abs로 한다, abs의 값과 찾는 원소(M) 이라고 했을 때 abs와 M이 같다면 탐색을 종료한다, abs의 값보다 M의 값이 크다면 abs + 1의 자리의 값을 다시 반복한다. public static boolean BSearch(int[] arr, int n) { int left = 0; i..
Heap 완전 이진 트리의 일종, 우선순위 큐를 위하여 만들어진 자료구조 여러개의 값들 중에서 최대값, 최소값을 빠르게 찾아내도록 만들어진 자료구조 반정렬 상태를 유지한다. 큰 값이 상위 레벨에 있고, 작은 값은 하위레벨에 있다. 모든 부모노드의 key 값이 자식노드의 key 값 보다 항상 크거나 작은 이진트리 Heap 구현 구현을 쉽게 하기 위해 배열의 첫 번째인 인덱스 0 은 사용되지 않는다. /* 최대힙 삽입 */ void insert_max_heap(int x){ maxHeap[++heapSize] = x; // 힙 크기를 하나 증가하고 마지막 노드에 x를 넣는다. for (int i=heapSize; i>1; i/=2) { // 마지막 노드가 자신의 부모 노드보다 크면 swap if (maxHe..
class Solution { public int solution(String[] babbling) { int answer = 0; return answer; } } 문제 설명 머쓱이는 태어난 지 6개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음을 최대 한 번씩 사용해 조합한(이어 붙인) 발음밖에 하지 못합니다. 문자열 배열 babbling 이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해주세요. 제한사항 1 ≤ babbling의 길이 ≤ 100 1 ≤ babbling[i]의 길이 ≤ 15 babbling의 각 문자열에서 "aya", "ye", "woo", "ma"는 각각 최대..
HashTable 매우 빠른 평균시간내에, 삽입/삭제/탐색연산을 제공한다. Key, Value를 동시 저장하는 테이블이며, key 값을 매핑했을때 나오는 값이 value 값이다. Hashtable table = new Hashtable(); // 해쉬테이블의 초기화 방법이다. 0 1 2 3 4 5 6 7 8 9 key값을 index로 매핑하여 ( function ) Table에 저장한다. table.put(T, T); 로 엘리먼츠를 추가하면 index 0 부터 차례대로 들어간다. 테이블 공간이 하나씩 생성되면서 공간을 차지하게되면 추가할때마다, 동시에 탐색할떄마다 0부터 돌아가기 때문에 시간이 오래걸리고 비효율적이게 된다. 이러한 비효율을 줄이기 위해서 hash function(해시함수)을 사용하여 in..
Big - O 표기법 알고르짐 수행시간을 최고차항 만으로 간단하게 표시한다. 대략적인 증가값만 나타내는 방법 알고리즘 성능 기본 연산 : 배정연산 대입연산, 복사연산 == 1단위시간 산술 연산 : +, -, * , / == 1단위시간 비교 연산 : >, = index; i-- ) { elementData[i + 1] = elementData[i]; } // 해당 index 위치에 값을 넣기위해 한자리씩 뒤로 밀어낸다. elementData[index] = element; return true; // index 위치에 element값을 집어넣는 코드, } public boolean addFirst(Object element) { return add(0,element); }/ // add 메서드를 호출하여 ..
using System; public class Solution { public int solution(string[] spell, string[] dic) { int answer = 0; return answer; } } 문제 설명 PROGRAMMERS-962 행성에 불시착한 우주비행사 머쓱이는 외계행성의 언어를 공부하려고 합니다. 알파벳이 담긴 배열 spell과 외계어 사전 dic이 매개변수로 주어집니다. spell에 담긴 알파벳을 한번씩만 모두 사용한 단어가 dic에 존재한다면 1, 존재하지 않는다면 2를 return하도록 solution 함수를 완성해주세요. 제한사항 spell과 dic의 원소는 알파벳 소문자로만 이루어져있습니다. 2 ≤ spell의 크기 ≤ 10 spell의 원소의 길이는 1입니..
public string solution(string my_string, int num1, int num2) // my_string 에서 index num1과 num2에 분자를 바꾼 문자열 { string answer = ""; return answer; } 문제 설명 문자열 my_string과 정수 num1, num2가 매개변수로 주어질 때, my_string에서 인덱스 num1과 인덱스 num2에 해당하는 문자를 바꾼 문자열을 return 하도록 solution 함수를 완성해보세요. 제한사항 1
