본문 바로가기

분류 전체보기739

[백준 1377] 버블 소트 [C] 풀이 index를 이용해 쉽게 풀이할 수 있는 문제다. bubble sort를 했을 때, 정렬이 다 되기까지의 횟수, 즉 요소들이 좌측으로 밀려났 횟수 중 가장 큰 횟수를 찾으면 된다. 입력받을 때 다음과 같이 index를 달아주고, num 10 1 5 2 3 index 0 1 2 3 4 정렬을 하면 다음과 같은 모습이 된다. num 1 2 3 5 10 index 1 3 4 2 0 정렬한 배열의 요소들에 달린 index값에 대해 이전의 index값들을 뺀 값들 중 최댓값이 정답과 일치한다. 소스코드 #include #include #define max(a, b) a > b ? a : b typedef struct{ int num, idx; }Point; int compare(const void *a, c.. 2021. 9. 5.
[백준 17404] RGB거리 2 [C] 풀이 "백준 1149, RGB거리"에 조건이 추가된 문제이다. 입력받은 비용들을 여러 번 사용해야 하고, 처음에 고른 색에 따라 최소비용을 계산해주어야 한다. 소스코드 #include #define MAX 1000001 #define MIN(a,b) (a < b ? a : b) int main(){ int N, result = MAX; scanf("%d", &N); int cost[N][3], min[3] = {0,}, old[3] = {0,}; for (int i = 0; i < N; i++) scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]); for (int i = 0; i < 3; i++){ old[0] = old[1] = old[2] = MAX;.. 2021. 9. 5.
[백준 1818] 책 정리 [C] 풀이 부분 수열의 최대 길이를 구한 후 N에서 빼주면 된다. 소스코드 #include int dp[200001] = {200001}; int main(){ int N; scanf("%d", &N); int val, back = 0; for(int i = 0; i dp[back]) dp[++back] = val; else{ int left = 0, right = back, mid, idx; while(left = val) right = (idx = mid) -1; else left = mid + 1; } dp[idx] = val; } } printf("%d", N - (back + 1)); } 출처 및 참고자료 1818번: 책정리 동혁이.. 2021. 9. 4.
[백준 12738] 가장 긴 증가하는 부분 수열 3 [C] 풀이 "백준 12015, 가장 긴 증가하는 부분 수열 2"와 동일하지만, 입력받는 숫자들의 범위가 더 크다. 기존 코드로 풀린다. 소스코드 #include int dp[1000001] = {1000001}; int main(){ int N; scanf("%d", &N); int val, back = 0; for(int i = 0; i dp[back]) dp[++back] = val; else{ int left = 0, right = back, mid, idx; while(left = val) right = (idx = mid) -1; else left = mid + 1; } dp[idx] = val; } } printf("%d", ba.. 2021. 9. 4.
[백준 14003] 가장 긴 증가하는 부분 수열 5 [C] 풀이 "백준 12015, 가장 긴 증가하는 부분 수열 2"에서 부분 수열의 최대 길이를 lower bound방식으로 빠르게 구했지만, 이렇게 만들어진 임의의 수열들의 요소가 최대 길이를 이루는 요소들이 아님을 예시를 통해 알 수 있었다. 한마디 더 붙이자면, 임시로 생성하는 수열의 최댓값보다 작은 경우에는 lower bound으로 찾은 index위치에 덮어쓰기 때문에 최대 길이를 이루는 요소가 아님을 알 수 있다. 만약 입력받은 요소들이 몇 번째 index에서 덮어쓰기가 되는지 알 수 있다면, 이전의 방법으로 구한 부분 수열의 최대 길이와, 입력받은 요소의 개수 N을 조건에 따라 줄여가면, 요소들을 구할 수 있다. 소스코드 #include #define MAX 1000001 int arr[MAX], te.. 2021. 9. 4.
[백준 12015] 가장 긴 증가하는 부분 수열 2 [C] 풀이 "백준 11053, 가장 긴 증가하는 부분 수열"보다 수열의 크기가 커, 기존의 방법대로 하면 시간초과가 발생한다. 수열 전체에서 binary search로 특정한 조건의 부분 수열을 탐색하는 방법은 아닌 것 같아 lower bound만을 이용했다. 다음과 같이 수열의 길이만을 계산하기 위해 다음과 같이 수열을 만들었다. i = 0이거나, 생성 중인 수열의 가장 뒷 값보다 큰 경우에는 길이를 늘려준다. 위의 조건이 아닐 때마다, lower bound로 적절한 위치에 입력받은 값을 삽입한다. 10 20 10 11 20 와 같은 수열을 입력 받았다고 가정하자. 앞에서 순차적으로 값이 커지는 경우만 계산을 한다면 10 20으로 최대 길이가 2다. 때문에, 11처럼 20보다는 작지만, 10보다는 큰 경우 .. 2021. 9. 4.

티스토리툴바