한다 공부

문제 이름은 버블 소트지만 머지 소트 (병합 정렬)로 풀어야하는 문제. 왜냐하면 1 ≤ N ≤ 500,000 이기 때문에 n^2 으로 풀 수 없기 때문이다.. 헷갈려서 정리를 해봤는데 병합만 늘 O(N*logN) 이고, 기수 정렬이 O(kN), 삽입, 선택, 버블 등 대부분의 정렬은 최악의 경우 O(N^2) 까지 갈 수 있다. 그래서 안정적으로 빠른 병합 정렬을 잘 알아두는 것이 좋다고 한다. 1초의 시간이 주어졌을 때 대부분 1,000,000 정도의 데이터는 O(kN), O(N*logN) 10,000 정도의 데이터는 O(N^2) 500 이하의 데이터는 O(N^3) 인 알고리즘이 사용 가능하다고 한다. 왜냐하면 1초에 주로 1억회의 연산이 가능한데 10,000의 경우 N^2이면 1억이 되기 때문에 위와 ..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1년 6개월 전(?) 이 문제를 푼 적이 있었다, 예전에는 음수, 양수를 따로 우선순위 큐를 이용해서 작은 수를 기준으로 정렬했는데 (greater 사용) 새로이 풀어보면서 우선순위 큐의 정렬 기준을 직접 변경하는 방법이 있길래 사용해봤다. 구조체와 operator 메소드를 사용하면 된다. (저번에 푼 방식) https://sxyzn.tistory.com/38 [C++] 백준..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 벡터를 사용하면 시간초과가 나올 것이다. 그래서 셋을 사용했다. 셋은 중복없이 정렬된 상태로 저장이 되고, 셋의 find 함수를 사용할 경우 시간복잡도는 O(logN) 를 가진다. 왜냐하면 셋은 BST(Binary Search Tree, 이진 탐색 트리) 자료구조를 갖고 있기 때문이다. 셋의 find 함수의 경우, 해당 원소가 있으면 해당 위치의 iteratior를 ..

https://www.acmicpc.net/problem/1235 1235번: 학생 번호 첫째 줄에는 학생의 수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부 www.acmicpc.net 반례를 찾지 못해서 시간이 오래걸린 문제.. 정작 반례를 찾은 다음에는 금세 구현할 수 있었다.. 잘못된 접근) 처음에는 어떻게 접근을 했냐면, 첫번째 문자열이 12345이고 두번째 문자열이 56789 세번째 문자열이 00000 이라면 첫번째 문자열을 잘라내어 (12345를 1, 또는 12, 또는 123... 과 같이 잘랐었음) 두번째 문자열의 부분 문자열과 같은지.. 세번째 문자열의 부..

https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열 www.acmicpc.net 아주 단순한 문제. 공백을 포함한 문자열을 받고, 맨처음이 공백인 경우와 맨끝이 공백인 경우를 제외하고 공백 갯수 +1을 하면 된다. cin>> 으로 받으면 공백을 인식하지 못하기 때문에 getline(cin, str) 을 사용하면 된다. #include using namespace std; int main(){ int ans=0; string s; getline(cin,s); for(int..

1541번: 잃어버린 괄호 (acmicpc.net) 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 그리디 연습을 하고자 1541번을 풀어보았다. 한 번이라도 - 가 나왔을 때 그 뒤의 값을 다 뺄셈 해주면 최솟값이 된다. a + b - c - d + e - f + g 같은 경우에는 a + b - c - (d + e) - (f + g) = a + b - c - d - e - f - g 가 된다. 어쨌거나 그리디 적으로 (?) - 나오면 그 뒤의 연산을 다 뺄셈 처리 하는게 전체의 최솟값이다. 그리디는 뭔..

[C] 트리 : 이진트리의 전위, 중위, 후위, 레벨 순회 (tistory.com) [C] 트리 : 이진트리의 전위, 중위, 후위, 레벨 순회 아까 이진트리를 구현할 때 10 / \ 20 30 위와 같은 트리를 어떻게 순회해야 잘 순회했다고 소문이 날까? 여기엔 크게 3가지 순회가 있다. 전위 순회란 루트를 방문하고 왼쪽 서브트리, 오른쪽 서 sxyzn.tistory.com 위 게시글에서 트리의 순회에 대해 알아보았다. C로 풀었던 트리의 순회를 C++에서는 map을 이용하여 풀 수 있다. map은 파이썬에서의 딕셔너리와 비슷한 자료구조이다. key - value 쌍으로 저장이 되며, key 값을 정렬된 상태로 저장한다. pair라는 것도 있는데, 이것은 두 값을 저장할 수 있다. 이 때에는 pair의 ..

2294번: 동전 2 (acmicpc.net) 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 동적 계획법 문제는 어렵다..... 이 문제는 아래와 같이 풀었다 가치가 1 3인 동전이 있다고 하자 1~6 까지의 가치합을 만든다고 하면 가치 1인 동전을 쓰면 동전의 갯수가 1 2 3 4 5 6 일 것이다. 가치 3인 동전을 쓰면 동전의 갯수는 0 0 1 2 3 1 일 것이다. 가치 1, 3 모두 쓰면 동전의 갯수는 1 2 1 2 3 1 일 것이다. 이는 어떻게 구한 것 이냐면 , ..

13549번: 숨바꼭질 3 (acmicpc.net) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 7%, 90%에서 멈추는 사람 .... 🖐 ^^ 나밖에 없을듯,.. 0-1 BFS 우선 0-1 BFS란? 최단경로 문제이면서 가중치가 0,1 만 존재할 때 덱을 이용하여 푸는 문제이다. 다익스트라를 사용했을 때 보다 빠르다. 가중치가 두 개인 상태에서 최단경로를 구해야하므로 가중치가 낮은걸 push_front를 하고 가중치가 높은걸 push_back하면 우선순위(짧은 경로)에 따..

10814번: 나이순 정렬 (acmicpc.net) 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 두가지 값을 저장하는 것이므로 pair를 이용하면 된다. 단, 첫 번째 값인 나이순으로 정렬하되 두 번째 값인 이름은 입력 순서를 유지해야한다. #include 안에 있는 sort 함수를 써서 정렬을 했다 계속 틀렸습니다가 떠서 당황했는데, 알아본 결과 sort의 경우 비교하는 값이 같을 경우에 원래 순서를 유지한다는 보장이 없다고 한다. 다시 말해 sort로 정렬하면 나이가 같은 사람들은 정렬 순서가 원래와 다르게 ..