본문 바로가기
반응형

백준134

[백준/C++] 램프 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 열의 램프들을 반전 시키는 방법을 K번 실시했을 때, 모든 행의 램프가 켜진 경우가 가장 많은 수를 구해야 한다. 이 문제에서는 램프가 가장 많이 켜진 경우를 찾기 위해 모든 경우를 탐색해봐야 하는데 이때, 모든 경우를 찾기 위한 기준을 잘 정해야 한다. 특정 열의 램프들을 끄거나 키는 것을 기준으로 잡게 되면 2^n의 시간복잡도가 나타나고 중복이 발생하게 된다. 잘 생각해보면 반대로 특정 행의 램프들을 전부 키도록 한 다음 그때, 몇 행의 램프가 켜져있는지 비교하는 방법으로 쉽게 문제를 풀 수 있다. (왜냐하면 같은 열에 있는 램프들은 전부 불이 반전되는 것에 연결되어 있다. 그렇기 때문에 한 .. 2024. 4. 21.
[백준/C++] Pho Restaurant HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 두 가지 요리만 하는 식당에 n개의 테이블이 있고, n개의 테이블당 i명의 사람이 요리를 시킨다. 이때, 같은 테이블은 같은 요리를 주문하도록 만드려면 사람을 몇 번 이동해야하는지 계산하는 문제다. 문제 자체는 크게 어렵지 않다. 테이블 당 1번 메뉴와 2번 메뉴를 주문한 사람의 수를 파악하고, 그 중에서 메뉴의 수가 더 적은 사람을 다른 테이블로 이동시키면 된다. 여기서 하나의 예외 상황이 발생하는데, 만약 모든 테이블이 1번 메뉴를 많이 시키고 2번 메뉴를 적게 시키는 경우다. (또는 모든 테이블이 2번 메뉴를 많이 시키고 1번 메뉴를 적게 시키는 경우) 이 경우 최소값인 수만 다른 테이블로 이동하.. 2024. 4. 19.
[백준/C++] 타임머신 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 음의 간선이 있기 때문에, Dijikstra알고리즘으로 문제를 풀 수 없다. 음의 사이클이 존재하는지 찾는 알고리즘에는 벨만 포드 알고리즘이 있기 때문에 벨만 포드 알고리즘을 이용해 문제를 풀었다. 벨만 포드 알고리즘에서 음의 사이클이 존재하는지 판단하는 방법은 다음과 같다. N개의 정점이 있을 때, 임의의 정점 A에 도달하기 위해 거쳐야되는 정점의 개수는 총 N-1개다. 그렇기 때문에 음의 사이클이 없다면 임의의 정점에서 다른 정점으로 도달하는 최소비용을 구하는 과정을 N-1번 하면 출발 정점에서 모든 정점에 도달하는 최단경로가 계산이 된다. 이 때, 음의 사이클이 있다면 한번 더 최단경로를 계산했을.. 2024. 4. 18.
[백준/C++] 미확인 도착지 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 시작점 st에서 도착점 ed로 가는 최단 경로에 임의의 두 점 (m, n)을 잇는 경로가 포함되어 있는지 계산하는 문제다. 문제를 해결하는 방법은 여러 방법이 있다. 1. Dijikstra 알고리즘으로 두 점 m, n을 잇는 경로를 포함하는지 체크한다. 2. Dijikstra 알고리즘으로 최단경로와 [st -> m -> n -> ed, st -> n -> m -> ed]의 최단 경로의 길이가 같은지 비교하는 방법이 있다. 이 중에서 1번 방법으로 코드를 구현해 문제를 풀었다. Dijikstra 알고리즘과 동일하게 코드를 구현하지만 m, n을 잇는 경로를 포함하는지 체크할 배열을 하나 만든다. 이후.. 2024. 4. 17.
[백준/C++] 특정한 최단 경로 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 중간에 반드시 두 정점을 거쳐서 가는 최단경로를 찾는 문제다. 결국 최단경로를 찾는 문제기 때문에 Dijikstra 알고리즘으로 쉽게 풀 수 있다. 제한사항을 보면 V의 개수가 최대 800이기 때문에 O(N^2)의 시간복잡도로 문제를 풀어도 빠르게 풀 수 있는 문제다. 이 문제의 특징은 양방향 간선이기 때문에 a -> b의 최단거리는 b -> a의 최단거리와 같다. 그러므로 이를 이용하면 최단거리를 구하기 위해서는 두 개의 값만 비교하면 된다. 1. 1 -> a -> b -> V로 도착하는 경우 2. 1 -> b -> a -> V로 도착하는 경우 위의 두 경우를 비교하면 되는데, a -> b의 최단거리.. 2024. 4. 16.
[백준/C++]최단경로 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 시작점에서 다른 정점에 도착하는 최단 경로를 구하는 문제다. 최단 경로를 구하는 알고리즘에는 다익스트라(Dijikstra) 알고리즘이 있다. 다익스트라 알고리즘은 아래 순서로 진행된다. 1. 방문하지 않은 정점 중에서 가장 비용이 적은 방문할 수 있는 정점을 선택한다. 2. 선택한 정점에서 이동할 수 있는 정점들을 방문할 수 있는 정점에 추가하고, 이동했을 때 드는 비용을 갱신한다. 3. 선택한 정점을 방문처리하고, 다시 1번 과정을 반복한다. 이 과정에서 가장 비용이 적은 방문할 수 있는 정점을 선택하는 방법에 따라 시간복잡도가 달라진다. 만약 V개의 노드를 전부 탐색할 경우 O(V^2)의 시간.. 2024. 4. 15.
[백준/C++] 이분 그래프 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 정점들의 집합을 두 개로 분류했을 때, 집합 내에 속한 정점들이 서로 인접하지 않게 할 수 있는지 판단하는 문제다. 어떻게 하면 문제를 풀 수 있을지 한번 그림으로 생각해보자 먼저 위의 왼쪽 그림의 경우를 살펴보자 하나의 정점이 속할 집합이 정해지면, 인접한 정점은 다른 집합에 속해야 한다. 그러므로 이를 이용해 하나의 정점이 0번 집합에 속했다면, 인접한 정점은 전부 1번 집합에 넣는다. 마찬가지로 하나의 정점이 1번 집합에 속했다면, 인접한 정점은 전부 0번 집합에 넣으면 된다. 이렇게 정점들의 집합을 두개로 나눠서 채워 넣으면 한 집합에 속해있는 정점들은 서로 인접하지 않도록 만들 수 있다. 그런.. 2024. 4. 14.
[백준/C++] 벽 부수고 이동하기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 (0, 0)에서 출발해 (N-1, M-1)에 가장 빨리 도착하는 최단경로를 구하는 문제다. 이 문제에서 중요한 점은 경로 중간에 벽이 있는 경우에는 벽을 부수고 이동할 수 있다는 점이다. 일단, 최단경로를 구하기 위해서는 BFS를 이용해 특정 지점에 처음 도달했을 경우에 이동한 칸수가 정답이다. 하지만 이 문제에서는 벽을 부술 수 있기 때문에 이를 고려해야 한다. 그러므로 특정 지점에 방문했을 때, 벽을 부수고 방문했는지와 벽을 부수지 않고 방문했는지를 구분해서 저장해 준다. 이를 위해 visited의 2차원 vector에 벽을 부수고 방문한 경우, 부수지 않고 방문하는 경우의 2가지 경우를 고려해 [.. 2024. 4. 13.
[백준/C++] 뱀과 사다리 게임 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 칸에 이동했을 때, 뱀이나 사다리가 있다면 다른 칸으로 이동할 수 있는 게 특징이다. 이렇게 이동을 하면서 마지막 칸인 100번 칸에 도착하면 승리하는데, 주사위를 조작해 원하는 숫자를 낼 수 있다면 100번 칸에 도달하기 위해 주사위를 가장 적게 굴리는 횟수를 구하는 문제다. 한번 이동할 때 마다 주사위를 굴리는 횟수가 1씩 늘어나므로, BFS로 문제를 풀면 빠르게 풀 수 있다. 이동 할 수 있는 곳은 현재 칸에서 1~6으로 6 곳이고, 이 6곳에 도착했을 때 뱀이나 사다리가 있다면 다른 칸으로 이동하면 된다. 이렇게 BFS로 문제를 구현하면 100번 칸에 처음 도달했을 때, 주사위를 굴린 횟수.. 2024. 4. 13.
[백준/C++] 3차원 토마토 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 토마토의 3차원 버전이다. 모든 토마토가 익을 수 있는지 확인하고, 만약 모든 토마토가 익는다면 걸리는 최소 시간을 구하는 문제다. 특정위치에 있는 토마토가 익을 수 있는 시간 중 가장 빠른 시간을 구해야 하므로, BFS를 이용하면 첫 방문했을 때가 토마토가 가장 빨리 익는 시간이 되는 것이다. 여기서 특정위치에 있는 토마토가 다음으로 탐색할 수 있는 곳은 6방향이다. 이를 이용해 6방향으로 탐색을 하고, 방문한 적이 없으면서 토마토가 있으면 queue에 넣어 탐색을 진행하면 된다. BFS로 문제를 풀 줄 안다면, 처음부터 토마토가 없는 빈칸만 잘 구분해주면 된다. 모든 위치에 대해 탐색이 끝났다면, .. 2024. 4. 12.
[백준/C++] 숨바꼭질 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 N에서 출발해 M에 도착하는데 걸리는 가장 적게 걸리는 시간을 구하는 문제다. 그러므로 BFS로 풀면 M에 처음 도달한 순간이 가장 시간이 적게 걸린 것이다. 임의의 점 X에서 다음에 갈 수 있는 곳은 X+1, X-1, X*2이다. 그러므로 이 3곳에 대해 queue에 삽입해 탐색을 하면 된다. 여기서 다음에 갈 위치가 이미 방문한 적이 있다면, queue에 삽입할 필요가 없다. 왜냐하면 BFS로 탐색을 하기 때문에 첫 방문이 가장 시간이 적게 걸린 순간이기 때문이다. 이제 문제를 풀 때, 방문을 체크할 visited vector와 queue를 이용해 문제를 풀면 된다, ​ [아이디어 정리] N에서 M.. 2024. 4. 12.
[백준/C++] 오아시스 재결합 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 두 사람이 서로 볼 수 있는지 수를 계산하는 문제다. A와 B를 선택해 그 사이에 사람의 키를 비교하기에는 매우 비 효율적이다. 두 사람 사이에 키가 큰 사람이 없기만 하면 서로 마주볼 수 있으므로 이를 이용해 문제를 풀면 된다. 그럼 여기서 두 사람 사이에 키가 큰 사람이 없다는 것은 어떤 의미일까? 잘 생각해보면 A와 B의 사이가 아닌 곳에는 키가 큰 사람이 있어도 된다는 뜻이다. 아래 그림을 한번 보면 A와 B 사이에 키가 큰 사람이 없으므로 A와 B는 볼 수 있다. 이를 이용하면 A의 왼쪽에는 키가 큰 사람이 와도 전혀 영향이 없다는 사실을 알 수 있다. 이제 문제를 푸는 방법은 다음과 같.. 2024. 4. 11.
[백준/C++] 오등큰수 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 오큰수 문제와 크게 다른게 없다. HTML 삽입 미리보기할 수 없는 소스 오큰수가 오른쪽에 있는 수 중에서 크면서 가장 가까운 수를 찾는 문제였다면, 오등큰수 문제는 등장하는 횟수를 비교하는 문제다. 즉, 비교하는 게 숫자의 크기가 아니라 등장횟수로 바뀐 것 뿐인 문제다. 처음에 문자가 몇 번 등장했는지를 map이나 array를 이용해 기록한다. 이후 순차적으로 숫자를 비교해 등장 횟수가 i번 째 수보다 큰지 비교하면 된다. 만약 i번째 수와 같거나 작다면 stack에 i번째 숫자를 기록한다. (stack에 i번째 수 추가) 마찬가지로 stack구조를 이용하면 문제를 쉽게 풀 수 있기 때문에 stack.. 2024. 4. 10.
[백준/C++] 오큰수 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 i번째 숫자의 오른쪽에 있는 수 중에서 가장 왼쪽에 있는 수를 찾으면 되는 문제다. 즉, i번째 수가 오면 그 수를 기준으로 오른쪽에 큰수가 나오는지 탐색을 하면 되는 문제다. 여기서 문제를 풀 때, 만약 i번째 수마다 오른쪽을 탐색하면 O(n^2)의 시간복잡도가 걸리게 된다. 대신 빠르게 푸는 방법이 있다. 아래 그림과 같이 3, 5, 2, 7의 4개의 숫자의 수열을 예로 들어보자. 처음에 3이라는 숫자가 들어오면 기록을 한다. 아직까지는 3의 왼쪽에 어떤 숫자가 오는지 모른다. 이후 들어오는 숫자는 5다. 여기서 5는 3보다 크기 때문에, 3은 자신보다 오른쪽에 있는 큰 수를 발견한다. 그러므로 3.. 2024. 4. 9.
[백준/C++] 문자열 폭발 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 문자열이 완성되면 삭제를 하고, 뒤에 문자들을 이어 붙이면 되는 문제다. 문제를 풀 때, 앞에서 부터 문자열을 추가해 나가다가 M의 마지막 문자가 나오면, 저장된 문자들을 탐색해 삭제가 되는지 확인했다. 아래 그림을 통해 자세하게 알아보자 M의 마지막 문자인 4가 나왔으므로 4부터 탐색해 문자열 M과 같은지 확인한다. C4로 같았으므로 문자열을 삭제해 준다. 마찬가지로 진행을 하면 아래와 같이 정답이 나오게 된다. 이렇게 하면 문자열을 앞에서부터 n번 탐색해 문제를 해결할 수 있다. 이때 문자를 저장하고 삭제를 하는 방법은 여러가지가 있겠지만, 뒤에 있는 문자부터 빼 사용할 것이므로 stack을 .. 2024. 4. 8.
반응형

티스토리툴바