Algorithm

[백준 1613] 역사 C++

1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 플로이드-와샬 1. 문제 해결 아이디어 사건들의 전후 관계를 파악하는 문제라서 처음에 바로 위상 정렬로 풀기 시작했었다. 근데 위상 정렬을 해놓으니 관계도는 명확히 그려지지만 임의의 정점 2개를 선택했을 때 해당 정점들이 서로 어떤 관계에 있는지 알아보려면 매번 BFS가 필요해 보였다. 효율이 안 좋게 느껴졌고 위상 정렬은 아닌 것 같아 알고리즘 분류를 켜서 어떤 알고리즘을 써야 하는지 힌트를 받았다. 플로이드-와샬 알고리즘을 쓰는 문제였다. N이 400..

소방차 (FIRETRUCKS)

algospot.com :: FIRETRUCKS 소방차 문제 정보 문제 한겨울 날씨가 추워지면 각종 난방 기구 때문에 화재가 발생하기 쉽습니다. 어느 추운 겨울날 서울 시내 n개의 지역에 동시에 화재가 발생했습니다. 피해를 최소화하기 www.algospot.com 다익스트라 문제 설명 더보기 각 소방서마다 불이나는 집까지의 최단거리를 구하고, 그 중에서 가장 가까운 소방서만 선택해서 전체 시간을 구한다면 시간초과가 날 것이다. Key point는 소방서가 시작점이기 때문에 가상의 정점(0번 정점)을 만들고, 0번 정점에서 소방서까지 가는 비용을 0으로 잡고 queue에 넣어주면 된다! -> 0번 정점에서 모든 소방서로 가중치가 0인 간선을 연결한다고 생각하자 우선순위 큐에서 항상 가장 적은 시간이 소요되..

[백준 17143] 낚시왕 C++

17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 1. 낚시왕은 0번 col에서 오른쪽으로 한 칸 이동 2. 낚시왕이 있는 열에서 땅과 제일 가까운(row값이 가장 작은 상어)를 잡는다 3. 상어이동 상어 - 방향, 크기, 속도 특정방향으로 이동하다가 벽을 만나면 방향을 바꿔서 뒤로 감 상어 객체 생성 모든 상어가 일단 이동하고 겹치게 된 상어가 있으면 크기가 가장 큰 애들만 살아남음 맵에는 상어가 2마리 이상 있다는걸 알 수 있는 장치가 필..

[백준 11779] 최소 비용 구하기 2 C++

11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 A 도시에서 B 도시로 가는 최소 비용을 알아야 한다. 간선의 비용은 음수가 없다. 위 두가지 정보로 다익스트라문제인걸 알았다. 다익스트라 알고리즘에 의해서 도착점을 발견하면 현재 가지고 있는 최소 비용이 도착점 까지의 비용이된다. bfs를 수행하면서 현재 정점에 도달하기 직전에 거쳐온 정점을 저장해둔다. 예시 입력을 그래프로 나타냈다. 1이 시작점이고 우선순위 큐에 의해서 queue에 4, 2,..

[백준 14003] 가장 긴 증가하는 부분 수열5 C++

14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 이분 탐색 1. 문제 해결 아이디어 [백준 12015] 가장 긴 증가하는 부분 수열2 C++ 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이전까지 풀.. hyeo-noo.tistory.com 위 문제에서 추가적인 요소만 넣어준다면 해결 ..

[백준 3055] 탈출 C++

3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS 1. 문제 해결 아이디어 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 위 문제랑 거의 똑같은듯 하다 고슴도치는 물이 곧 차오를 지역으로 가지 못하기 때문에 bfs를 통해서 물을 먼저 채워준다 이때 채워진 물을 nextwater 큐에 넣어준다. 물은 . 부분에만 채워질 수 있다. 물..

[백준 14891] 톱니바퀴 C++

14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 하나의 톱니가 돌아가면 다른 톱니도 돌아가야하므로 연쇄반응을 구현해야한다. 재귀로 풀어내려고 했고 현재 바퀴를 시계/반시계 방향으로 회전시키기 전의 3시, 9시 방향의 자기정보를 가지고 있어야 한다. 현재 영향을 주는 방향을 매개변수로 입력받아서(lr) (0은 양방향, 1은 오른쪽으로, -1은 왼쪽으로) 영향을 줄 바퀴를 정해서 함수를 호출했다. 로직은 이게 전부인듯 하다. 삼성 SW기출답게 구현력을 요구하는..

[백준 6087] 레이저 통신 C++

6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS 1. 문제 해결 아이디어 처음에 시뮬레이션 문제인가? 생각했는데 그냥 BFS에 조건이 몇 개 추가된 문제였다. 먼저 DP풀듯이 각 칸에 도달하기 위한 최소 거울의 개수를 구해야 겠다는 생각을 했다. 그리고 이미 방문한 칸에 다시 도달할 수 있어야 올바른 최솟값을 구할 수 있다고 깨달았다. 가장 기본적으로, 주어진 W, H 범위 내에서만 움직여야하고, 벽인 경우 que에 넣으면 안된다. que의 초기값이 하나의 점이 아니라 임의의 C에서 4방향으로..

[백준 14890] 경사로 C++

14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 구슬 탈출 2 문제를 풀다가 코드가 너무 길어지고.. 구현이 더러워져서 도망치듯 풀게 된 문제다. 도망쳐왔지만 이 문제도 절대 만만하진 않았다. 분명 문제에는 경사로는 서로 겹치면 안 된다고 적혀있어서 가로와 세로 경사로끼리도 겹치면 안되는줄 알았다. 그런데 알보고니 가로 경사로와 세로 경사로는 서로 영향을 주지 않기 때문에 문제가 더 쉬워졌다! 가로길 + 세로길 해주면 답이 나오게 되었다! 문제 설명이 부실한듯해서 시간을 좀 잡아먹었..

[백준 1238] 파티 C++

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 단순한 다익스트라 문제는 A->B까지 가는 거리의 최단거리를 구하는 것이지만 이 문제는 A->X로가는 최단거리 + X->A로 되돌아오는 최단거리를 구해야 한다. A->X로 가는 최단거리를 구해보자. 정점의 개수가 최대 1000개, 간선의 개수가 최대 10000개 이므로 O(|V||E|) = 10,000,000 이 되어 시간내에 풀 수 있다고 생각했다. 그래서 A->X로 가는 최단거리를 A의 개수만..