어흥

문제 링크: https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. www.acmicpc.net 1. 주의할 점 - Tree와 depth를 잘 설정해야한다. - LCA 알고리즘을 정확히 이해해야한다. 2. 구현 - 첫 번째 시도: LCA에 대한 개념을 모르고 Parent,Depth 배열만을 이용해서 구현 -> TLE - 두 번째 시도: LCA에 대한 개념을 익히고 적용 -> lg|Node의 최대갯수|의 올림 만큼만 Tree를 밑으로 판다고 생각한다. Dep..

문제 링크: https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 국가를 나타내는 정수와 이 국가가 얻은 금, 은, 동메달의 수가 빈칸을 사이에 두고 주어진다. 전체 메달 수의 총합은 1,000,000 이하이다. www.acmicpc.net 1. 주의할 점 - 전체 메달 수의 총합이 100만이다. -> 금 X M+ 은 X M + 동 X M (M은 특정 수)로 하기엔 M을 쉽게 생각하지 못했다 - 찾고자 하는 index에 집중하지 말고 해당 index의 금은..

문제 링크: https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 문제 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의 www.acmicpc.net 1. 주의할 점 - 50m걸을 때마다 맥주를 1개씩 줄이는 방식으로 하면 복잡하다 -> 1000m이내에 편의점..

문제 링크: https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 1. 주의할 점 - 벽을 세웠다고 가정 -> 계산 -> 추가로 세웠던 벽을 허물어야한다 2. 구현 - DFS를 통해 벽을 세울..

문제 링크: https://www.acmicpc.net/problem/5214 5214번: 환승 문제 아주 먼 미래에 사람들이 가장 많이 사용하는 대중교통은 하이퍼튜브이다. 하이퍼튜브 하나는 역 K개를 서로 연결한다. 1번역에서 N번역으로 가는데 방문하는 최소 역의 수는 몇 개일까? 입력 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어진다. 총 K개 숫자가 주어지며, 이 숫 www.acmicpc.net 1. 주의할 점 - Node의 수가 많아서 2차 배열로 할 경우 메모리 초과가 발생 가능하다 - HyperTube를 어떻게 저장..

문제 링크: https://www.acmicpc.net/problem/4179 4179번: 불! 문제 지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자! 미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다. 지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다. 불은 각 지점에서 네 방향으로 확산된다. 지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다. 지훈이와 불은 벽이 있는 공간 www.acmicpc.net 1. 주의할 점 - BFS 문제 - 메모리초과로 인해 몇번 틀렸다. 메모리초과 조심하자 2. 구현 [초기 설계] 불을 더 퍼트린 다음에..

문제 링크: https://www.acmicpc.net/problem/10711 10711번: 모래성 문제 명우와 친구들은 여름방학을 맞이하여 해변가에 놀러가기로 했다. 이번에 여행을 떠난 해수욕장의 이름은 ALPS(Awsome Land & Poor Sea)이다. 해변가에서 수영복을 입은 미녀들에게 관심이 많은 원철이와는 달리 명우는 해변가의 모래에 더 관심이 많다. 해변가의 모래는 무한한 것들을 만들 수 있는 가능성을 내포하고 있다. 또한 이렇게 만들어진 작품이 파도에 의해 사라지는 모습은, 마치 자신이 가장 빛날 수 있는 시간을 알고 스스로 아름답게 www.acmicpc.net 1. 주의할 점: - 배열의 크기가 커서 check/visit 배열을 매번 초기화해주면서 하기엔 TLE가 발생한다 - res..

문제 링크: https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 1. 주의할 점 - 구현시 숫자가 이상하게 중첩되거나 날라가는 경우가 없도록 조심한다 2. 구현 - DFS로 00000~33333까지 짠다(0: 위로, 1: 오른쪽으로, 2: 아래로, 3: 왼쪽으로) - 정확하게 구현한다(과거엔 Deque을, 현재는 Vector를 이..