boj

[백준 2661] 좋은 수열 C++

2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 백트래킹 연습하기 #2 res : 지금까지 만들어진 수열 is_bad() 함수의 나쁜 수열 찾는 방법 ex1) res = 32121 start lo hi 0 32 121 1 21 21 -> start=1 일 때 lo == hi 이므로 나쁜 수열이 되어 return false ex2) res = 3212323 start lo hi 0 321 2323 1 212 323 2 12 323 3 23 23 -> start=3 일 때 lo==hi 이므로 나쁜 수열이 되어 return f..

[백준 1759] 암호만들기 C++

1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹 연습하기 #1 Stack Permutation C++ 순열을 구하기위해 dfs를 사용했는데 visit 배열 대신 stack을 사용해서 구현해보았음 n이 8이 넘어가면 하루종일 걸려요.. 모든 경우의 수를 출력해주기 때문에 어쩔 수 없다 if(node == N) 부분의 for hyeo-noo.tistory.com 이전에 스택을 이용해 permutation을 구현한 코드처럼 C개의 문자중에서 L개를 뽑는 경우를 모두 출력하는 문제이다 추가된 조건들 암호를 이루는..

[백준 11404] 플로이드 C++

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 최단경로 플로이드-와샬 알고리즘 11404문제 예제 입력의 그래프이다 숫자가 겹쳐보이는 이유는 1 4 1 , 1 4 2 처럼 1번에서 4번 노드로 가는 경우의 비용이 중복되어서 입력되기 때문이다 플로이드-와샬 알고리즘은 동적계획법을 활용한 알고리즘이다 그래서 임의의 vertax 에서 다른 vertax로 가는 모든 경우의 수를 조사해서 최소 비용을 구할 수 있다. 그리고 다익스트라 최단거리 알고리즘은 edge의 비용이 음수인 경우는 찾지 못하는 반면 플로이드-와샬 ..

[백준 3109] 빵집 C++

3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 이 문제는 그리디 알고리즘을 적용한 DFS문제이다 그리디를 어떻게 적용하는가?? 항상 오른쪽 위 부터 탐색을 해야한다(0번째 Row부터 탐색할 경우만 해당. R-1번째 부터 탐색하면 오른쪽 아래부터 탐색) 탐색을 한 부분은 다시 탐색하지 않는다! (DP개념도 같이 적용) 문제를 이해했다면 항상 오른쪽 위 부터 탐색해 간다는건 쉽게 이해할 수 있다 나도 처음엔 이것만 생각해서 백트래킹 방식을 적용해 37 번 라인에 방문했던 곳을 초기화 해주는 코드(Map[r][c] = 0;)가 ..

[백준 12015] 가장 긴 증가하는 부분 수열2 C++

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이전까지 풀어봤던 LIS 문제들과 푸는 방법이 조금 다르다 기존LIS는 for문을 2번 돌려서 O(n^2) 시간안에 풀었다면 이번 문제는 수열의 크기가 N st){ int mid = (st + ed)/2; if(key > arr[mid]){ st = mid+1; } else{ ed = mid; } } return ed; } void solve(){ int cnt = 1; res.push_back(arr[0]); for(int i = 1; i

[백준 10090] Counting Inversion C++

10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net 분할 정복 1. 문제해결 아이디어 임의의 수열에서 자신보다 뒤에 있는데 자신보다 작은 수의 개수의 총 합을 구하는 문제이다 N^2로 풀면 너무 쉽겠지만 N

[백준 1111] IQ Test C++

www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 처음에 x가 0이 되는 경우를 깜박해서 ZeroDivisionError 가 발생했었다 같은 수가 연속으로 나올경우 x값이 0이 된다! 모든 점이 한 직선위에 있음을 알아차리고, 직선의 기울기와 y절편을 구한다 구한 기울기와 y절편이 모든 좌표 쌍에 적용된다면 a, b는 구해진 것임 그리고 N==1, N==2일때의 기저조건 예외처리를 해주고 마무리를 했다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..

[백준 14501] 퇴사 C++

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dp와 브루트포스 방식을 모두 적용할 수 있는 좋은 문제이다! solve1은 브루트 포스와 dp를 적용해서 O(n^2)에 풀 수 있는 방법이다 solve2는 solve1과 논리는 같지만 top-down방식으로 재귀함수를 이용한 방법이다 solve3는 동적계획법을 최대한 활용해서 Pi, Ti를 뒤에서부터 탐색하는 방법을 사용해 O(N)만에 해결하는 방법이다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 5..

[백준 2798] 블랙잭 C++

N이 최대 100 이므로 3장을 뽑는 모든 경우의 수를 탐색하는 O(N^3) 알고리즘을 수행할 수 있다 for 문을 돌면서 sum에 현재 선택한 카드 3장의 합을 저장하고, sum이 M을 넘지않지만 현재 결과보다 크다면 현재 결과를 갱신한다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include using namespace std; int main(){ int N, M, num[101], sum = 0, result = 0; cin >> N >> M; for(int i = 0; i > num[i]; } for(int i = 0; i

[백준 1074] Z C++

분할정복은 어려워! 코드만 보면 되게 간단해 보이는데 간단하게 만들기 위해 머리를 짜내는게 힘들다.. 내 머리는 재귀적인 생각을 잘 못하는듯 하다 처음에 입력받은 N값을 2로 나눈 값을 solve()로 넘겨준다 -> 이 때 n == 2라고 가정하자(N == 3인 경우) (r, c)가 몇 사분면에 있는지 4개의 if문을 통해서 판별한다 판별기준 : row + n 과 col + n row+n을 기준으로 r이 이 값보다 작으면 1, 2 사분면 중 하나, 같거나 크면 3, 4 사분면 중 하나이다. col+n을 기준으로는 c가 이 값보다 작으면 1, 3 사분면 중 하나, 같거나 크면 2, 4 사분면 중 하나이다. 총 4가지 기준으로 분할 정복을 실행하고 r, c의 위치를 찾으면 (n == 0) 리턴하여 지금까지 ..