공부하자

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 요구조건은 꽤 간단하다. 전위순회로 주어진 트리를 후위순회로 변환하면 끝이다. 이때 중요한 키 포인트는 세가지가 있다. 1. 전위순회에서 가장 첫번째 노드는 루트 노드이다. 2. 전위순회에서 루트노드보다 커지는 첫번째 원소를 기점으로 왼쪽, 오른쪽 자식트리가 나뉘게 된다. 3. 나뉜 자식트리에 대하여 1~2의 과정을 재귀 형태로 반복하고, 그 과정에서 맨 첫번째 노드(루트 노드)..

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 재귀함수를 활용하여 이진트리의 전위,중위,후위 순회를 출력하는 문제이다. 트리의 입력값도 사전에 다 주고, N의 개수도 최대 26까지이기 때문에 크게 까다로운 점은 없었다. 다만 이 문제에서의 핵심 포인트는 처음 루트값이 A라는 것을 활용하여 다른 자식 노드들을 따로 알파벳으로 접근하지 않고 pair형의 배열의 인덱스로서 접근, 참조하는 것인데, 처음 풀때는 이 부분이 조금 이해가 가질..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 난이도 자체는 단순히 구현만 하면 되는 문제이기에 그리 어려운것은 없었지만, 처음에 문제 접근을 잘못 하면서 시간초과가 났고, 그로 인해 조금 헤맸다. 처음엔 단순히 vector에서 find로 인덱스를 찾고 뭐 그런 방식으로 풀었는데, 제시되는 테스트케이스가 최대 3,000,000이고, find의 시간복잡도가 O(N)이니까, 결국 O(N^2)가 된다. 시간초과가 날수밖에 없는 풀이법인 것이다. 결국 그 방법 말고 비트마스킹을 이용해..

https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 한동안 서울에 방 잡고 이사한다 뭐다 해서 정신이 없었다. 백준이랑 블로그 글 올리는것도 정말 오랜만인거 같은데, 역시 ps는 꾸준히 풀어보는게 가장 좋다. 몇주 쉬고 이랬더니 감 다 죽었나보다. 이 문제는 map을 이용해서 각 단어가 얼만큼 나왔는지 개수를 세야하는 문제다. map을 이용해 푼다면 쉽게 풀리는 문제였지만, map 구조를 이용하지 않고 풀라고 하면 어떻게 풀어야하지? 모르겠..

https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 덱을 활용하여 양방향에서 접근이 가능하게끔 풀어내야 하는 문제다. 이때 주의해야할 점은, 주어지는 종이에 적힌 수(코드상에서는 k라 정의함)가 양수인지 음수인지에 따라서 다르게 처리를 해주어야 한다는 점이다. 필자 또한 양수 음수에 따라 조건문으로 분기된 상황에서 반복횟수를 잘못 설정해 어려움을 겪었다. 기본적으로 양끝단 두 곳 모두 접근이 가능한 자료구조를 사용해야 하기에 덱을..

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 큐를 활용한 간단한 문제다. 1에서 N까지의 수를 큐에다가 먼저 넣어놓고, K-1번 큐 맨 앞에 있는 수를 다시 push 해준 다음, K번째는 pop시켜 vector에 넣어놓고 큐가 다 비워지면 vector를 출력하는 방식으로 풀었다. 사실 맨 첫번째 제출때 틀렸습니다가 떠서 당황했는데 알고보니 그냥 출력 형식을 무시하고 숫자만 출력해서 오답이 나왔다. 다음부터는 문제를 잘 읽고 풀어야겠다. #include #include #include using namespace std; in..

https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 처음엔 중복제거를 통해 해결해야하나 고민하던 찰나 구글링으로 vector에서 집합 관련된 연산을 간단히 수행할 수 있게 해주는 라이브러리가 있다 해서 활용해보았다. 입력의 최댓값이 200,000이기에 코드의 시간복잡도가 O(N^2)가 될 수 없기에 라이브러리를 활용해 간단히 해결해보았다. 대칭 차집합 뿐만 아니라 다른 합집합, 교집합 등의 연산들도 같은 라이브러리 안에서 수월하게 적용할 수 ..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net C++에서 기본으로 제공하는 map contaier에 관한 문제이다. 이 문제를 푸는데 있어서 두가지 중요한 관건은, 첫째, 입력받은 변수의 data-type이 int인지 string인지 판별할 수 있는 코드가 삽입되어야 한다. 각각의 케이스를 조건문으로 분기하여 따로따로 처리해주야 한다. 둘째, map에서 find 함수를 활용하여 값들을 찾게되는데, 이때 key와 v..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 10815번 문제와 비슷한 듯 다른 문제다. 다른 점이라 하면, 시간제한이 1초라는 점인데, 처음에 10815번 문제와 같이 set 컨테이너를 이용하여 풀었더니 시간초과가 나왔다. set에서 find나 count를 쓴다 해도 O(logN)의 시간복잡도를 가지는데, 이것이 반복문 안에서 움직이다 보니 시간초과가 뜨는 듯했다. 따라서 map을 사용하여 find나 c..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 저번 글이었던 7785번과 상당히 유사한 문제다. set을 이용하는 문제이며, set 컨테이너를 이용해야겠다고 마음먹고는 거진 10분만에 풀어버렸다. 문제 난이도 또한 상당히 쉽다. 하지만, 최댓값이 500,000이기에 O(N^2)인 경우 시간초과가 나지않을까 잠깐 걱정했으나, set컨테이너에서 특정 값을 찾는 find 메소드의 시간복잡도는 O(logN)에 불과하기 ..