본문 바로가기
[백준/C++] 1738번: 골목길(G2) 문제 https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 www.acmicpc.net 사용한 알고리즘 2022.02.14 - [PS/Algorithm] - [알고리즘 개념정리] 10. 최단경로 알고리즘 -> 벨만-포드 풀이 음의 간선이 있으니 벨만포드 알고리즘을 사용하여 풀어보자. 이 문제에서는 금품의 양이 최대가 되는 경로를 구하는 중이므로 입력할 때 간선의 부호를 반대로 넣은 후, 음의 사이클 여부를 판단해주면 된다. 다만, 사이클이 있다고 해서 무.. 2022. 2. 25.
[백준/C++] 15942번: 전구를 켜라(G2) 문제 https://www.acmicpc.net/problem/2423 2423번: 전구를 켜라 첫째 줄에 문제의 정답을 출력한다. 전구에 불을 켜는 것이 가능하면, 몇 개의 칸을 돌려야 하는지를 출력하고, 불가능할때는 "NO SOLUTION"을 따옴표 없이 출력한다. www.acmicpc.net 사용한 알고리즘 2022.02.14 - [PS/Algorithm] - [알고리즘 개념정리] 10. 최단경로 알고리즘 -> 다익스트라 풀이 타일 말고 꼭짓점을 기준으로 생각해보자. (0,0)에서 (n,m)까지 가는 최단경로를 구하면 된다. 타일들이 간선역할을 한다고 생각하고, 타일을 회전시키지 않아도 만들어지는 연결은 가중치 0, 타일을 회전시켜야 만들어지는 연결은 가중치 1로 간선을 모델링한다. 이때, 2차원 .. 2022. 2. 14.
[백준/C++] 15942번: Thinking Heap(G2) 문제 https://www.acmicpc.net/problem/15942 15942번: Thinking Heap Binary heap은 Heap을 구현하는 방법의 하나이며 Complete binary tree 형태로 만들어진다. Complete binary tree는 Binary tree의 종류 중 하나로, 마지막 레벨을 제외한 나머지 레벨에는 노드가 꽉 차 있고 마지막 www.acmicpc.net 사용한 알고리즘 2022.02.09 - [PS/Algorithm] - [알고리즘 개념정리] 9. 트리 -> Binary Heap 풀이 heap[idx] 배열로 min-heap binary tree를 관리해준다. 1-based로 하면 부모 idx가 i일 때, 자식은 2i 와 2i+1이고 자식 idx가 i일 때,.. 2022. 2. 11.
[백준/C++] 10026번: 적록색약(G5) 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 사용한 알고리즘 2022.02.05 - [PS/Algorithm] - [알고리즘 개념정리] 8. 그래프/그래프 탐색 -> 2차원 상에서의 그래프 탐색 풀이 이차원 상에서의 그래프 탐색이다. 모든 정점에 대해, 그 정점과 입접한 정점은 상, 하, 좌, 우 방향에만 있다. 따라서 각 정점의 좌표 (x,y)에 대해 (x+1, y), (x-1, y), (x, y+1), (x, y-1) 중 특.. 2022. 2. 6.
[백준/C++] 16564번: 히오스 프로게이머(S1) 문제 https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ X www.acmicpc.net 사용한 알고리즘 2022.02.02 - [PS/Algorithm] - [알고리즘 개념정리] 7. 이분탐색/분할정복 -> 매개변수 탐색 풀이 팀 목표 레벨의 '최댓값'을 구하는 문제이므로 최적화 문제라고 할 수 있다. 결정 문제로 바꾸어 푸는 매개변수 탐색 기법을 사용해보자. 목표레벨 T는 최초 레벨들 중 최소값보다 작.. 2022. 2. 3.
[백준/C++] 2370번: 시장 선거 포스터(G4) 문제 https://www.acmicpc.net/problem/2370 2370번: 시장 선거 포스터 첫줄에는 포스터의 개수 n(1 ≤ n ≤ 10,000)이 주어지고, 그 다음 n줄에는 각 포스터의 왼쪽 끝의 위치와 오른쪽 끝의 위치 l, r이 주어진다. (1 ≤ l 좌표압축 풀이 포스터의 개수 n의 범위는 1 ≤ n ≤ 10,000 이고, 각 포스터의 왼쪽 끝의 위치와 오른쪽 끝의 위치 l, r의 범위는 1 ≤ l < r ≤ 100,000,000 이다. 벽의 칸이 1~10^8으로 큰 범위를 가지므로 실제로 붙이는 것처럼 배열 마킹한 후 카운트하는 방법으로는 AC받을 수 없다. 포스터의 실제 길이가 중요한 게 아니라 어떠한 포스터가 보이는 구간이 '있는지'가 중요하다. 즉, 실제 간격이 중요하지 않고 .. 2022. 2. 3.

티스토리툴바