본문 바로가기
728x90

알고리즘/개념정리10

알고리즘 / DP(Dynamic programming) 동적계획법 DP(Dynamic programming) 동적 계획법 동적 계획법(DP)은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. state의 값을 메모리에 저장하여 반복적인 연산을 피해 시간 복잡도를 낮추고 메모리 낭비를 막는다. 코딩 테스트에 dp는 자주 나오는 문제이다. 하지만 나는 dp 푸는 것이 두려워 계속 미뤄뒀지만.. 이제는 진짜 풀어볼 때가 되었다... DP를 푸는 방법 DP를 사용하여 푸는 문제인지 확인 어떻게 상태를 표현할지 정함 상태 관계를 수식화 top-down or bottom-up 방식으로 풀지 정함 1. DP를 사용하는 푸는 문제인지 확인 특정 수량의 최대 최소를 구하는 문제들, 특정 조건을 만족하는 배열 개수를 세는 문제 등 DP로 풀 수 있다. 중복되는 함수들을 생.. 2021. 9. 28.
알고리즘(C++) / STL : set, multiset STL : set, multiset 2021.09.06 - [알고리즘] - 알고리즘(C++) / 프로그래머스 level 3 : 이중우선순위큐 문제를 풀면서 multiset에 대해 알 수 있었다. set과 multiset에 대해서 공부해본다. set 유일한 원소만을 가질 수 있는 구조로서 수학적으로 집합을 의미한다. key값을 저장할 수 있다. 하지만, key 값이 중복될 수 없다.(multiset은 중복 가능) 자동으로 정렬된다. (defalt는 오름차순) 노드 기반이다. 균형 이진 트리로 구현되어있다. (binary search tree) 빠른 탐색이 가능하다. 임의 접근이 불가능하다. (배열처럼 접근x, iter 반복자로 접근) 생성, 삽입(insert), 삭제(erase), 탐색(find) 등이 가.. 2021. 9. 6.
알고리즘(C++) / 이진 탐색(이분 탐색) - binary_search(), lower_bound(), upper_bound() 이진 탐색(이분 탐색) - binary_search(), lower_bound(), upper_bound() 이진 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 리스트가 반드시 정렬되어 있어야 사용이 가능하다. start, end, mid를 사용하여 찾으려는 데이터와 mid에 있는 데이터를 반복적으로 비교하여 데이터를 찾는다. 전부를 탐색하는 탐색 속도에 비해 빠르다. 알고리즘 헤더를 선언하여 이진 탐색 함수 binary_search(), lower_bound(), uppwer_bound() 함수를 사용할 수 있다. (#include ) 시간 복잡도는 O(logN)이다. 함수를 알아보도록 한다. binary_search() 찾으려는 데이터 값의 존재 여.. 2021. 8. 29.
알고리즘(C++) / string 자르기 : stringstream, 문자열 파싱istringstream, ostringstream string 자르기 : stringstream string을 자르고 싶을 때마다 반복문으로 어느 문자열까지 자르곤 했었는데 그렇지 않고 stringstream을 사용하여 string을 자르는 방법을 알아본다. stringstream은 string에서 같은 string을 자르기 위해서는 사용되지 않고 자료형에 맞는 문자열을 얻기 위해서 사용된다. 가지고 있는 string에서 공백과 \n을 제외한 문자열을 차례대로 빼내는 역할을 수행한다. 예를 들면 abc 123 def에서 stringstream을 사용하면 abc, 123, def로 다른 자료형(string, int)끼리는 문자열을 자를 수 있지만 ab, c123, def처럼 다른 자료형을 자르기 위해서는 사용되지 않는다. //stringstream tes.. 2021. 8. 22.
알고리즘(C++) / 문자 대소문자 판별, 숫자 판별, 공백 판별 문자 대소문자 판별, 숫자판별 문자를 대문자인지 소문자인지 숫자인지 공백인지 판별할 수 있는 함수를 알아본다. isupper //대문자 판별 if (isupper('A')) { cout 2021. 8. 4.
알고리즘(C++) / 벡터(vector) 중복제거 : unique 벡터(vector) 중복제거 unique 벡터에서 중복되는 수 제거가 필요할 때가 있다. 그럴경우에 unique를 사용하여 중복되는 수를 제거할 수 있다. 만약 벡터에 수가 { 1,1,3,3,0,1,1 }가 저장되어있다고 하면 unique 함수를 사용한 후에는 벡터에 {1, 3, 0, 1, 0, 1, 1 } 과 같이 저장되어 있다. 빨간색 부분은 벡터에 존재하는 수이고 파란색 부분은 원래 벡터에서 바뀌지 않은 부분이다. 이때 algorithm 헤더를 선언해주어야한다. vector arr = {1,1,3,3,0,1,1}; unique(arr.begin(), arr.end()); erase함수는 벡터를 원하는 위치를 지워준다. arr.erase(unique(arr.begin(), arr.end()), arr.. 2021. 7. 1.
알고리즘 / unordered_map C++ STL 중 해쉬 맵 unordered_map을 설명한다. 특징 map보다 더 빠른 탐색을 하기 위한 자료구조이다. unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)이다. map은 Binary Search Tree로 탐색 시간 복잡도는 O(log n)이다. unordered_map을 사용하기 위해서는 #include 을 선언해야 한다. unordered_map은 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능을 보인다. 하지만, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수도 있다. index로 접근할 수 없고 iterator로 접근해야 한다. 데이터가 많은 경우에는 unordere.. 2021. 6. 26.
알고리즘 / DFS(Depth First Search), BFS(Breath First Search) 그래프를 탐색하는 방법에 DFS(Depth First Search)와 BFS(Breath First Search)가 있다. 깊이 우선 탐색인 DFS와 너비 우선 탐색인 BFS를 알아보도록 한다. DFS(깊이 우선 탐색, Depth First Search) 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 대표적으로 백트래킹에 사용된다. 일반적으로 재귀 호출을 사용하여 구현하지만, 단순한 스택 배열로 구현하기도 한다. 갈림길이 나타날 때마다 '다른 길이 있다'는 정보만 기록하면서 자신이 지나간 길을 지워 나간다. 그러다 막다른 곳에 도달하면 직전 갈림길까지 돌아가면서 '이 길은 아님'이라는 표식을 남긴다. 그렇게 갈림길을 순.. 2021. 4. 10.
알고리즘(C++) / cin, cout 입출력 속도 높이기 백준 2751문제를 풀 때 입력과 출력은 맞게 나오는데 결과는 시간 초과라는 결과가 나왔다. 알아본 결과 cin과 cout을 사용할 때 시간이 상당히 걸린다는 것을 알았다. 그래서 cin과 cout의 입출력 속도를 높여 다시 구현해보았다. cin과 cout의 입출력 속도를 높이기 위해 다음 줄을 추가해주면 된다. ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 일종의 편법이지만 이 방법을 사용하면 cin과 cout의 속도를 높일 수 있다. 하지만 주의할 점이 있다. scanf,printf와 섞어 사용 X 싱글 쓰레드 환경에서만 사용 다음과 같은 점만 주의해주면 코드를 작성하는데 문제가 없다. 또한 추가로 endl을 사용하는 것보다는 "\.. 2021. 4. 10.
알고리즘 / 그리디 알고리즘(탐욕 알고리즘) 그리디 알고리즘이란? Greedy Algorithm은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 그리디 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 그리디 알고리즘을 활용한 문제들이다. 장점 계산 속도가 매우 빠르다. Dynamic programming 및 다른 알고리즘보다 빠른 속도로 최적해를 도출할 수 있다. 그리디 알고리즘을 적용할 수 있는 문제 유형에 대해 이해한다면 효율적으로 최적해를 찾을 수 .. 2021. 3. 1.

티스토리툴바