한다 공부

문제 이름은 버블 소트지만 머지 소트 (병합 정렬)로 풀어야하는 문제. 왜냐하면 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하면 우선순위(짧은 경로)에 따..

이분 탐색은 효율성을 요구하는 문제에서 많이 쓰인다고한다. 이러한 이분 탐색은 실생활에서도 많이 쓰인다. 최근에 무한도전을 봤는데 노홍철이 생각한 숫자를 멤버들이 특정 횟수 내에 맞춰야하는 게임을 했다. 1~100 까지의 수라고 하면, 50을 물어보고 up down을 해서 범위를 좁혀나가는게 가장 현명하다. 이 방법이 이분 탐색이다. C++에서는 #include을 통해 binary_search라는 함수를 사용할 수 있다. 이 경우 원하는 요소가 있으면 1을 반환, 없으면 0을 반환한다. 그런데 보통의 알고리즘 문제에서는 1, 0을 반환하는 것 뿐만 아니라 해당 요소의 인덱스 (위치) 등을 물어볼 수도 있기 때문에 이를 구현할 줄 알아야한다. 함수를 이용해서 풀 수도 있다. 주의해야할 점은, 이분 탐색에서..