이름 못 정한 블로그

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 상당히 문제가 간단하다. 구구절절 상황극이 있지도 않고, 문제에서 주어지는 조건도 심플하기 때문에 문제를 이해하는데에는 시간이 얼마 걸리지 않았다. 하지만 처음 풀 때 두가지 정도의 예외 사항을 놓쳐서 바로 통과를 받지는 못 했다. 첫번째 예외 사항은 지우는 노드가 루트인 경우이다. 간단히 조건문을 사용해서 처리할 수 있었다. 두번째는 루트 노드 바로 밑에 붙어있는 노드를 삭제하는 경우다. 처음 구현에서는 트리 구조에서 따로 노드를 삭제해주지는 않고 BFS..

1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 간단한 그리디 문제였다. 그리디임을 알고 문제를 시작했기 때문에 완전히 문제에 대한 지식이 없이 풀었다고 하기는 힘들다. 문제의 핵심은 카드 수가 적은 묶음부터 합치는 것이다. 이 아이디어는 쉽게 떠올릴 수 있었는데, 8%대에서 틀렸습니다를 봤다. 그 이유는 새로운 카드 묶음을 다시 큐에 집어넣고 다시 두개를 뽑았어야 했는데, 큐를 새롭게 업데이트해주지 않았기 때문이다.

2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 본격적인 학기 시작 전에 여유가 조금 있어서 정말 오랜만에 PS를 했다. 저번 방학 + 학기 초까지는 꽤 열심히 했었는데, 학기가 바빠지고 이번 방학 때는 다른 활동을 하느라 한참 방치되어 있었다. 최근에 C++도 다루지 않았다 보니 평소보다 시간이 좀 더 걸렸던 것 같다. 이 문제는 분할 정복을 이용해서 푸는 문제였다. 문제에 주어진 24를 기준으로 설명하면, 큰 그림은 작은 그림 3개로 쪼갤 수 있다. 또 작은 그림은 더 작은 그림 3개로 쪼갤 수 있는 형태를 가졌다. 그래서 더 이상 쪼갤 수 없는 그림까지 쪼..

17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 역시나 삼성 기출문제였다. 삼성 문제는 일단 문제를 꼼꼼히 읽는 게 중요한 것 같다. 문제를 완벽히 이해하고 필요한 기능을 하나하나 구현하면 풀 수 있다. 이번 문제를 풀기 위해서 가장 고민했던 부분은 게임의 진행 상태를 어떤 자료구조에 담을까였다. 제일 처음엔 링크드 리스트로 할까했는데 Singly 하게 구현해서는 안 됐고 Doubly까지 구현해야 했다. STL의 리스트가 Doubly로 구현되어 있다고 알아서 그걸 사용할까 생각했다. 그런데 최대로 필요한 경..

19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 오랜만이라 반가운 BFS 문제였다. 문제는 복잡하거나 구현할 것이 많다거나 하지는 않았다. 택시가 동시에 여러 명을 태우고 다녔으면 그건 좀 골치 아팠을 것 같다. 하지만 이 문제는 택시에 한 번에 한 명밖에 태울 수 없기 때문에 그리디하게 풀면 되는 문제였다. 택시의 운행 알고리즘은 엄청 심플하다. 1 현재 택시 위치에서 가장 가까운 승객을 찾는다. 2 그 승객을 태우고 도착점까지 최단 거리로 운행한다. 이 과정에서 연료가..

15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 삼성 SW 기출문제를 열심히 풀고 있다. 이 문제는 사실 어제 풀었는데 오늘에서야 포스팅한다. 내가 접근한 방법은 실제로 선들을 90도씩 회전시키는 방법이었다. 이 과정에서 배열을 중심점을 기준으로 90도 돌리는 게 쉽지 않았다. 내가 평소에 배열의 좌표를 잡는 방식과 다르게 되어 있어서 진짜 헷갈렸다. 문제에 주어진대로 해보려다가 결국은 체념하고 내가 원래 하던 대로 바꿨더니 그나마 이해하기 편했다. 이제 와서 보면 별거 없었는데 그 ..

19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 보통 내용도 붙여 넣는데 이 문제 같은 경우엔 문제가 너무 길어서 따로 붙이지 않았다. 문제를 풀기 위해서 두 가지 자료구조가 필요하다고 생각했다. 그래서 상어들의 현재 상태를 저장하고 있는 구조체와 냄새의 현재 상태를 저장하는 구조체를 만들었다. 첫 번째 구조체는 다른 알고리즘 문제들과 비슷하게 현재 상어의 좌표와 방향, 생존 여부가 들어있다. 이 문제가 특이한 점은 각 상어마다 이동 방향의 우선순위가 다르다는 것이었..

15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 문제 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접..

17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 문제 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구..

14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을..