최선을다하는

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 3 ×N 크기의 벽을 2 ×1, 1 × 2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 문제에서 주어진 힌트와 같이 2개 단위로 커질 때마다 그 타일을 이 전 타일들로 만들지 못하는 유일한 타일 배치가 2개씩 생기게 된다. 2개만 유일하게 3가지의 경우가 가능하다. 입력값으로 홀수가 주어지게 된다면 3*N 이 총홀수개의 단일 타일이 필요하게 되므로 만들 수 있는 경우의 수는 없다. 짝수가 들어올 경우 본인만의 ..

https://www.acmicpc.net/problem/18115 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net 문제 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다. 수현이는 처음에 카드 N장을 들고 있다..

6번째 내용은 트리였다. 강의 내용은 역시 어려운 것은 없었고 순회 방식등에 대한 내용이었다. 그리고 4문제가 기본문제로 주어졌는데 처음 2문제는 어렵지 않게 풀 수 있었다. 3번째 문제는 SWEA 1232번 사칙연산 문제였다. 앞선 두문제와 다르게 한자리 숫자가 아닌 여러자리 숫자가 올 수 있었으며 인덱스가 N의 반이 넘어가도 리프노드가 아닐 수 있어 문자가 올지 숫자가 올지 모르는 경우였다. 그래서 사칙연산 자체는 쉬웠으나 입력값을 받는데 난항을 겪었다. char 형식으로 받으려다가 마지막에서야 string 으로 받은 다음에 숫자면은 int 로 변환을 하는 방법을 사용했다. string stream 을 사용했지만 그냥 stoi 를 사용하는게 더 편했을 것 같다. vector 나 queue를 사용하면서..

https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 N(2 ≤ N ≤ 50,000) 개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그다음 줄..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 문제 수 N개 A1, A2,..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j)의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103..

https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 문제 모두 알다시피 동호는 커피숍의 마담이다. (마담이 무엇인지는 본인에게 물어보도록 하자.) 어느 날 커피숍의 손님 A 씨가 동호에게 게임을 하자고 했다. 그 게임은 다음과 같은 규칙을 갖는다. N개의 정수가 있으면, 동호는 다음과 같이 말한다. “3~7번째 수의 합은 무엇이죠?” 그러면 상대방은 “그 답은 000입니다. 그리고 8번째 수를 2로 고치도록 하죠” 그..

SWEA의 5번째 내용은 그래프 탐색에 관한 내용이었다. 그래프 탐색에는 여러 가지 이론들이 있지만 강의에서는 대표적인 DFS와 BFS에 관한 내용이 나왔다. 강의는 너무 쉬운 내용이라 금방 넘겼고 바로 문제 풀이에 들어갔다. 기초 DFS와 BFS라는 제목을 가진 문제 두 개를 풀었는데 DFS와 BFS를 활용하는 문제였는데 문제가 굉장히 불친절했다. 입력값도 트리를 파악할 수 없게 만들어 직접 출력해보아야 했고 입력값에 쓰레기 값도 들어있어서 문제 풀이에 굉장히 난항이 있었다. BFS 문제는 그보다 나았지만 행과 열 순서로 주지 않고 열 과 행 순서로 좌표를 주고 인덱스는 (0,0)부터 주지만 실제 좌표는 (1,1)부터 시작하여 굉장히 혼란스러웠다. 그리고 난 후 기본문제를 풀기 시작했는데 프로세서 연결..

https://www.acmicpc.net/problem/1091 1091번: 카드 섞기 지민이는 카지노의 딜러이고, 지금 3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다. (0 ~ N-1번) 일단 지민이는 카드를 몇 번 섞은 다음에, 그것을 플레이어들에게 나누어 준다. 0 www.acmicpc.net 문제 지민이는 카지노의 딜러이고, 지금 3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다. (0 ~ N-1번) 일단 지민이는 카드를 몇 번 섞은 다음에, 그것을 플레이어들에게 나누어 준다. 0번째 위치에 있던 카드가 플레이어 0에게 가고, 1번째 위치에 있던 카드는 플레이어 1에게 가고, 2번째 위치에 있던 카드는 플레이어 2에게 가고, 3번째 위치에 있..

https://www.acmicpc.net/problem/24041 24041번: 성싶당 밀키트 첫 번째 줄에 $N, G, K$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번째 재료에 대한 정보인 부패 속도 $S_i$, 유통기한 $L_i$와 중요한 재료인지를 나타내는 www.acmicpc.net 문제 인스타 빵타쿠들의 꾸준한 사랑을 받는 베이커리 은 수현이가 그동안 쌓아온 노하우를 바탕으로 밀키트 사업에도 진출했다! 이제 성싶당의 맛을 집에서도 즐길 수 있다! 이 소식을 놓칠 리 없는 빵타쿠 한별이는 바로 성싶당에 달려가 밀키트를 사 왔다. 그러나 문제를 푸느라 바쁜 한별이는 깜빡 잊고 유통기한 안에 밀키트를 먹지 못했다. 눈물을 머금고 밀키트를 버리려고..

이번 내용은 분할 정복에 관한 내용이었다. 분할 정복의 대표적인 문제로 머지 소트, 퀵 소트, 그리고 이진 탐색을 공부하였다. 특별히 어려운 내용은 없었다. 저번 학기에 알고리즘 수업에서 되게 자세히 배운 내용이라 친숙하였다. 대부분의 내용이 수업 때 배운 내용보다 깊지 않은 내용이었는데 임인성 교수님이 굉장히 잘 가르쳐 주시고 시험 문제도 시간 복잡도와 다양한 코드를 접할 수 있게 출제하셔서인지 기본적인 알고리즘에 대한 이해도가 굉장히 높아졌다는 것을 느낄 수 있었다! 주어진 문제를 보니 바로 vector를 이용한 쉬운 풀이와 오늘 배운 분할정복으로 직접 정렬하여 문제를 풀 수 있겠다. 하지만 두 문제 다 50개의 테스트 케이스 중 0개 성공, 즉 다 실패해버렸다. 2시간을 고민하고 답을 뒤지던 중 정..