🕹️ 알고리즘

[프로그래머스-level1]완주하지 못한 선수

반복문을 이용했더니 시간초과가 나서 해시를 이용하여 풀어서 통과했습니다! #include #include #include using namespace std; string solution(vector participant, vector completion) { string answer = ""; map m; for(int i = 0; ifirst; break; } } return answer; }

[2812]크게 만들기

www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 받은 입력 문자열을 하나씩 스택에 넣고 스택의 top위치 값이 현재 값보다 크면 최대 K번 pop한다 그럼 내림차순 형태의 수가 나오게 된다. 모두 같은 숫자일 경우에는 더이상 지워지지 않으므로 마지막에 N-K길이의 문자열로 출력하도록 했습니다 #include #include #include #include #include using namespace std; int main() { int N, K; cin>>N>>K; string s; cin>>s; stack st; int d = 0;..

[3079]입국심사

www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net #include #include #include using namespace std; vector v; long long N, M; long long calc(long long mid){ long long res = 0; for(int i = 0; i

[프로그래머스-level1]모의고사

c++ #include #include #include using namespace std; vector solution(vector answers) { vector answer; int a[] = {1,2,3,4,5}; int b[] = {2,1,2,3,2,4,2,5}; int c[] = {3,3,1,1,2,2,4,4,5,5}; int score_a = 0; int score_b = 0; int score_c = 0; for(int i = 0; i

[프로그래머스-level1][1차]다트게임

2018 KAKAO BLIND RECRUITMENT 문제 #include #include using namespace std; int solution(string dartResult) { int answer = 0; //점수 총합 int num = 0; vector sum; //1,2,3회 점수기록 for(int i = 0; i='0'&&dartResult[i]

[알고리즘]그리디(Greedy, 탐욕법, 욕심쟁이기법)

그리디 알고리즘이란? 탐욕알고리즘, 욕심쟁이기법 이라고도 합니다. 매순간 최적이라고 생각하는 해를 선택해나가서 최종적으로 최적해에 도달하는 알고리즘이라고 할 수 있습니다. 그렇게 때문에 구한 해가 항상 최적임이 보장되지는 않아서 근삿값을 구하는 용도로 사용되기도 합니다. 탐욕법이 충족되기 위한 조건 앞의 선택이 이후의 선택에 영향을 주지않을 때 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해일때 이렇게 2가지 조건을 만족할 때 그리디알고리즘이 잘 작용합니다. 이 조건들을 만족하지 못하면 최적해를 구하지 못하고 근삿값은 구할 수 있습니다. 개념자체만 봤을 때는 이해가 잘 안될 수 있으니 예제를 봅시다. 예제1 - 거스름돈(백준 5585번) 잔돈으로 500, 100, 50, 10, 5, 1엔이 있고 1..

[알고리즘]퀵 정렬(Quick Sort)

퀵정렬이란? 퀵정렬은 이름그대로 빠른정렬, 즉 다른 정렬알고리즘에 비해 빠르다고 할 수 있습니다. 다른원소와의 비교를 통해 정렬이 이루어지므로 비교정렬에 속하고, 같은 수가 있는 경우 같은 수의 순서가 달라질 수 있어서 불안정 정렬에 속합니다. ex) 5(1), 5(2), 3, 2, 1 -> 1, 2, 3, 5(2), 51(1) 시간복잡도 최악의 경우 O(n^2) 평균 O(n log n) 알고리즘 임의의 수(pivot)를 고른다. 피벗을 기준으로 두 수를 비교하여 왼쪽에는 pivot보다 작은 수, 오른쪽에는 pivot보다 큰 수가 오도록 분할한다. 분할된 리스트 가운데에 피벗을 위치 시키고, 양쪽 리스트에 대해 재귀적으로 수행한다. 예제 가장 오른쪽에 있는 4를 pivot으로 정함. pivot을 제외하고..

[알고리즘]깊이우선탐색(DFS),너비우선탐색(BFS)

그래프 탐색이란? 하나의 정점에서 시작하여 다른노드와 이어진 간선을 통해 다른 모든 정점들을 한번씩 방문하는 것입니다. 깊이우선탐색, 너비우선탐색은 그래프 탐색의 기본이라고 할 수 있습니다. 깊이우선탐색(Depth-First Search) 새로운 노드가 탐색될 때마다 그 노드로 이동하고, 다시 돌아와서 새로운 노드를 탐색하는 방법 시작노드에서 시작 인접한 다른노드 탐색 탐색한 노드에서 인접한 노드 중 탐색되지않은 노드 확인 인접한 노드 중 탐색되지 않은 노드가 없으면 다시 되돌아오면서 탐색되지않은 노드 확인 만약 탐색되지 않은 노드가 있다면 탐색 소스코드(c++) #include #include using namespace std; int N, E; //노드개수, 에지개수 int U, V; //연결되어있..

[알고리즘]완전탐색(Brute-force)

브루트포스(brute force)알고리즘, 완전탐색이란 가능한 경우를 모두 탐색해보는 방법입니다. 예시로는 해킹 시 모든 가능한 경우의 비밀번호를 다 넣어보는 것 등이 해당됩니다. 특정 알고리즘을 쓰게 하기 위해 시간제한이 짧은 경우엔 시간초과가 나지만, 때로는 완전탐색을 하는 방법이 간단하고 확실한 방법일 수 있습니다. 예제 (c++) 백준 2309-일곱 난쟁이 9명의 키가 입력으로 주어지는데 키 합이 100이 되는 7명의 키를 출력하는 문제입니다. #include #include #include using namespace std; int main() { vector v; int sum = 0; int one = 0; int two = 0; for (int i = 0; i < 9; i++) { int..

[백준-16693]Pizza Deal(C++)

소스코드 #include using namespace std; int main(){ double A1,P1,R1,P2; cin>>A1>>P1>>R1>>P2; if(A1*P2>R1*R1*3.1415926535*P1){ cout