Algorithm/문제 풀이

[BAEKJOON_1916 - JAVA] 최소비용 구하기

문제 www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 풀이 dist값 초기화가 중요. 인접리스트를 구현, 최소거리를 지속적으로 탐색 구현하다보니 프림과 비슷한 구조를 가졌다. 프림은 다익스트라와 달리 두 노드 사이가 최단거리가 아닐 수도 있다. 프림은 무향 그래프에서만 작동하고, 다익스트라는 무향, 유향 그래프에서 모두 작동한다. 프림이 다익스트라를, 다익스트라가 프림을 보장해주지 않는다. (최소스패닝트리가 최단경로트리를, ..

2020. 12. 28. 11:40

Algorithm/문제 풀이

[BAEKJOON_10026 - JAVA] 적록색약_V2

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net 풀이 기존에 풀었지만 알고리즘 스터디 문제에 있어서 재풀이. 기존에는 map을 적록색약 전용으로 복사를 해서 풀었지만, 이번에는 하나의 메소드에 적록색약 여부를 전달. map의 크기가 N= N || col = N) { return false; } return true; } } // 좌표를 담을 class class Pos { int row; int col; pub..

2020. 12. 27. 11:48

Algorithm/문제 풀이

[BAEKJOON_1197 - JAVA] 최소 스패닝 트리(MST)

문제 www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 최소 스패닝 트리 기본 문제, 개념을 다시 상기 시키고자 풀이. ( 꾸준히 해야 까먹지 않는다.) Prim과 Kruscal 모두 시도. 간적크 간많프 → 간선이 적으면 크루스칼 알고리즘 / 간선이 많으면 프림 알고리즘 ex) 항상 위와 같지는 않다. 하지만 대부분 간선의 갯수에 따라 알고리즘을 선택 MST를 한다면 프림과 크루스칼 두가지 방법으로 풀어보는..

2020. 12. 27. 10:20

Algorithm/문제 풀이

[BAEKJOON_3020 - JAVA] 개똥벌레

문제 www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 BruteForce로 풀려다 시간 제한 1sec를 본뒤 고민. 이분탐색을 사용하는 것 까지는 알겠는데 적용방법을 블로그를 통해 참고. 누적합을 적용해야하는 것을 참고했다. 석순과 종유석을 분리하는 이분 탐색으로, 누적합을 통해 파괴하지 않는 장애물을 제외. 석순의 경우 바닥, 종유석의 경우 천장임을 주의하며 풀이. 과정 석순과 종유석이 순서대로 들어오므로, 입력을 각각 다른 배열에 높이를 기준으로 받는다..

2020. 12. 24. 08:00

Algorithm/문제 풀이

[BAEKJOON_8983 - JAVA] 사냥꾼

문제 www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 풀이 시간 제한이 1sec, 사대의수(100,000) * 동물의 수(100,000) → 1000억 TLE(시간초과 발생). 사대의 기준에서 탐색이 아닌 동물의 기준에서 가장 가까운 사대를 찾는 방식 사용. 과정의 4,5번이 많이 헷갈렸는데, 쉽게 이해 하자면 mid( = (left+right)/2 ) 중간값을 본인의 좌표쪽으로 계속 줄여나간다고 생각. 또는 본인의 값보다 작으면 본인과 크기가 같게 한다고 ..

2020. 12. 24. 07:42

Algorithm/문제 풀이

[BAEKJOON_14391 - JAVA] 종이 조각

문제 www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 풀이 가로 세로를 어떻게 나눌지에 대해 매우 막막했다. 고민 뒤 다른분들의 코드를 참고 맵을 만들어 '1'과'0'으로 가로, 세로를 판단. ex) '1' 이면 가로, '0'이면 세로 주황색을 '1' / 파랑색을 '0' 이라고 가정하는 경우 가로의 수 = 543 + 829 (3자리의수 2개) / 세로의수 = 9+2+7 (1자리의수 3개)로 판단 할 수 있다. 이와 같은 가정을 가지고 과정을 시작한다. 과정..

2020. 12. 24. 06:24