C++

[프로그래머스-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

[CLion][C++]Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)

CLion에서 C++ 사용하여 Run 했을 때 Process finished with exit code 139 (interrupted by signal 11: SIGSEGV) 위와 같은 에러 문구가 뜨면서 입력도 받지 않고 Run 과 동시에 종료되는 문제가 있었다. 내가 생각한 원인은 큰 사이즈의 배열을 사용해서 그런 것같다. int dp[1001][1001]; string dp[100][100]; 일 때는 정상적으로 돌아갔지만 string dp[1001][1001]; 일 때는 위와 같은 에러 문구가 뜨면서 종료되었다. 해결 방법 배열의 사이즈를 줄인다. 배열의 사이즈를 줄일 수 없는 상황이라면, 다른 IDE를 사용해본다. (다른 IDE에서는 돌아갈 수도 있다.) 실제로 혹시나 해서 백준에 제출해보았더니..

[프로그래머스-level1]3진법 뒤집기

c++ #include #include #include #include using namespace std; int solution(int n) { int answer = 0; string s = ""; while(n>2){ s += (n%3)+48; n = n/3; } s += n+48; reverse(s.begin(), s.end()); 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; //연결되어있..