본문 바로가기
반응형

백준143

[백준/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.
[백준/C++] 앱 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 풀 때, 냅색 문제와 같이 풀었다. M의 크기를 갖는 배열을 만든 다음 i 만큼의 메모리를 cost를 주고 만들 수 있다면 새롭게 비용을 주고 특정 메모리를 만들 수 있는지 체크했다. 이렇게 풀면 통과는 되지만 10,000,000 * 100의 연산을 해야하기 때문에 비효율적 이었다. 다른 풀이가 있을까 찾던 중 메모리가 기준이 아니라 cost를 기준으로 하는 풀이가 있었다. DP[N][cost]을 만들고 여기에 메모리를 저장 하는 방법이다. 아래 그림을 따라 진행해보자 먼저 처음에 위 그림과 같이 초기화를 한다. 이후 첫번째 비용과 메모리를 이용해 Cost를 써서 얼마의 메모리를 만들 수 있는지.. 2024. 4. 7.
[백준/C++] 동전 1 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 k의 크기가 10000으로 제한되어 있기 때문에 쉽게 풀 수 있는 문제다. 동전의 가치가 전부 다르고 몇 개를 사용해도 되며, k원을 만드는 모든 경우의 수를 구해야 된다. for문으로 j원의 돈을 만들 수 있으면 j원에 coin을 더해 [j+coin]원을 만들 수 있다. 이때, coin을 여러개 사용할 수 있으므로 [j+coin*2], [j+coin*3] ... 도 만들 수 있다. coin에 숫자를 곱해 더하는 방법도 있겠지만, 좀 더 편한 방법이 있다. 예를 들어 2, 4의 동전이 주어지고 k가 10이라고 하자 그러면 2로 만들 수 있는 돈의 가치에 대한 경우의 수는 아래 그림과 같다. 그러면 2로.. 2024. 4. 6.
[백준/C++] 양팔저울 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때, 정말 풀 수 있나? 의문이 들었다.왜냐하면 아무리 DP로 푼다고 해도, 시간 복잡도는 O(3^n)이 되기 때문이다.  (n은 추의 개수) 여기서 3^n인 이유는 아래와 같이 3가지 경우가 존재하기 때문이다. 1. 구슬 쪽에 추를 올리는 경우2. 추를 사용하지 않는 경우3. 구슬 반대편에 추를 올리는 경우 그렇기 때문에 시간 복잡도는 O(3^n)이다.  한번 최악의 경우를 상상해 보면 추의 무게가 1, 3, 9 ,27 ... 처럼 3의 배수로 늘어나는 경우이다. (중복해서 만들어지는 추의 무게가.. 2024. 4. 5.
[백준/C++] 힘세고 강한 아침 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 풀 때, query가 들어올 때마다 계산을 했다. 그랬더니 시간초과가 나서 반복되는 계산을 줄이도록 문제를 풀었다. N이 100이기 때문에 첫 언어, 중간 언어를 정해 특정 언어로 변환하는데 걸리는 최소 비용을 계산할 수 있기 때문이다. 이 경우 O(N^2 * 최소 비용을 계산하는 시간복잡도) 이므로 문제가 해결될 것이라고 생각했다. 처음에 최소 비용을 계산할 때, priority queue를 이용해 탐색하지 않은 언어 중 항상 변환 비용이 가장 낮은 언어가 앞에 오도록 코드를 구현했다. 문제는 priority queue에 삽입하는데 O(logn)의 시간복잡도가 걸리기 때문에 시간초과가 또 났다... 2024. 4. 3.
[백준/C++] 수열 회전과 쿼리 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 수열의 회전에 관한 문제다. 문제의 내용을 보면 수열을 이동하는 쿼리와 수열의 특정 범위의 합을 묻는 쿼리에 대해 답을 출력하는 문제다. 여기서 특정 범위의 합은 매번 계산하기보다 누적합을 이용하면 한번의 계산으로 답을 출력할 수 있다. 수열의 이동은 원순열을 생각하면 편하다. (한쪽 끝으로 이동하다가 범위를 넘어서면 반대쪽으로 넘어간다) 먼저 처음에 시작 index를 정한다. 이제 수열의 시작 부분이 k만큼 증가하면 이는 시작 index가 오른쪽으로 이동한 것과 같다. 만약 시작 부분이 k만큼 감소하면 이는 시작 index가 왼쪽으로 이동한 것과 같다. 여기서 합을 구하는 범위가 N을 넘어가지 않기 .. 2024. 3. 12.
[백준/C++] 삼각 초콜릿 포장 (Sweet) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 규칙을 찾으면 쉽게 풀 수 있는 문제다. 빨간색 포장은 아래에 육각형이 두개 붙은 삼각형, 파란색 포장은 위에 육각형이 두개 붙은 삼각형 모양이다. 삼각형 포장의 각 줄 마다 맨 왼쪽의 index를 0이라고 가정하자. 이때, 빨간색 삼각형 모양의 포장의 윗부분 육각형의 index를 i라고하면 아래에 있는 육각형의 index는 i, i+1이 된다. 즉, 각 줄을 y라고 하면 빨간색 삼각형으로 포장지를 채우기 위해서는 'R' == [y][i] == [y+1][i] == [y+1][i+1]이 성립해야 한다는 것이다. 파란색도 비슷하게 조건을 찾을 수 있다. 파란색의 맨 왼쪽 위 육각형의 좌표를 [y][i]라.. 2024. 3. 2.
반응형

티스토리툴바