Hello Ocean! 🌼

문제 https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출 www.acmicpc.net 2차원 맵에서, 출발에서 도착점으로 가는데, X로 표시된 필요한 물건들을 모두 챙겨서 나가는 최소 이동거리를 구하는 문제이다. 풀이 그래프상에서 최소 이동 횟수를 구하는 문제이기 때문에 BFS를 이용했다. 그리고, 그래프상에 X가 있는 지점을 모두 방문하는게 조건이기 때문에 X방문체크를 어떻게 할지 고민하다가, X가 최대 5개라고 해서 길이 5짜리 비트마스크를 이용해서 방문체크를 해주..

문제 https://www.acmicpc.net/problem/13701 13701번: 중복 제거 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 www.acmicpc.net N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 2^25 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 이상 500만 이하이다. 풀이 숫자를 순서대로 입력받아..

알고리즘 문제를 풀 때, 원래 cin/cout을 이용했었는데 백준에서 난이도가 골드 이상인 문제중에 간혹 cin/cout으로 인해서 시간초과가 발생하는 문제들이 있었다. cin.tie(NULL) 같은 문법을 추가해서 입출력 시간을 줄이는 방법도 있었지만, 그래도 scanf/printf가 제일 빠른 것 같아 얼마전 부터는 scanf/printf를 사용하려고 노력하고 있다. 다시 이걸 써보니 cin/cout이 얼마나 편리하고 친절한 문법인지 깨닫게 되었다.. https://www.acmicpc.net/problem/17244 17244번: 아맞다우산 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 ..

문제 https://www.acmicpc.net/problem/11437 -> LCA 1 https://www.acmicpc.net/problem/11438 -> LCA 2 주어진 두 노드에 대해 LCA(가장 가까운 공통 조상)을 구하면 되는 문제이다. 1번과 2번의 차이는 노드의 최대 갯수 및 시간 제한의 차이이다. LCA2가 훨씬 빡빡하다. 풀이 1. 11437 LCA1번 풀이 연결된 두 노드 a,b가 N-1개의 줄에 걸쳐서 입력되는데, a,b중에 어떤 노드가 부모노드인지는 입력 받을 때에는 알 수가 없다. 그래서 처음에는 연결리스트 형태로 저장했다가, 입력을 다 받은 후에 BFS를 통해 루트인 1부터 타고 들어가서 트리구조를 파악할 수 있도록 했다. (각 노드의 부모와, 깊이 저장) 그리고 LCA를..

문제 https://www.acmicpc.net/problem/12888 BOJ 나라는 도시와 두 도시를 연결하는 도로로 이루어져 있다. 이 나라의 도로 네트워크는 완전 이진 트리의 형태를 가진다. 수빈이는 BOJ 나라의 도로 네트워크 트리의 높이 H를 알고 있다. 트리의 높이를 안다면, 도시의 개수와 도로의 개수도 구할 수 있다. 트리의 높이가 H인 경우에 도시의 개수는 2(H+1)-1개 이고, 도로의 개수는 2(H+1)-2개가 된다. 아래 그림은 H = 2일 때, 그림이다. 수빈이는 도로 네트워크에 차를 보내려고 한다. 모든 차는 시작 도시와 도착 도시가 있으며, 같은 도시를 두 번 이상 방문하지 않는다. 차의 시작 도시와 도착 도시가 같을 수도 있다. 모든 도시를 방문한 차의 개수가 모두 1개가 되..

문제 https://www.acmicpc.net/problem/10838 N개의 노드로 구성된 루트가 있는 트리가 다음과 같이 주어진다. 각 노드는 0부터 N-1까지의 번호로 구별되고, 0번 노드는 루트 노드이고, 나머지 노드 각각은 0번 노드의 자식 노드이다. 트리에 적용할 수 있는 연산은 세 종류이며, 이를 통해 트리의 모양을 바꾸거나 트리 에지에 색칠을 할 수 있다. 각 연산과 그 의미는 다음과 같다. paint(a, b, c): a번 노드와 b번 노드를 잇는 최단 경로를 찾은 후, 경로 상에 있는 모든 에지를 색깔 c로 칠한다. move(a, b): a번 노드의 부모 노드를 b번 노드로 바꾼다. 단, b번 노드는 a번 노드를 루트로 하는 부트리(subtree)에 속하지 않는다. 부모 노드를 바꾸기..