본문 바로가기

백준133

[백준/C++] LCS 3 (No. 1958) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 어떻게 풀 수 있을까 고민을 많이 했다.단순한 LCS 와 다르게 3개의 문자열에 대한 LCS를 구하는 문제였기 때문이다. 처음에는 3중 for문을 이용해 a, b, c의 문자열이 같은지 비교하고 LCS를 구해 min값을 출력하면 되는 줄 알았지만, 반례가 존재했다. 그래서 2개의 문자열만 비교하는 방법을 확장해 문제를 풀었다.먼저 a, b, c 문자열의 각 i, j, k번을 비교해보자. 그리고 LCS[i][j][k]를 a_i, b_j, c_k번 문자열까지 비교한 경우의 LCS라고 가정하자. 그러.. 2024. 11. 12.

[백준/C++] 도미노 예측 (No. 17943) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 xor 연산에 대해 잘 알고 있으면 쉽게 풀 수 있는 문제다. xor 연산은 2진법으로 표현한 뒤 두 수를 비교했을 때 같은 자리에 있는 수가 같으면 0 다르면 1로 표현하는 연산이다. 즉, A (xor) A는 같은 수 이므로 모든 자리에 있는 수가 같으므로 값이 0이 된다.또한 A (xor) 0을 연산할 경우 0과 연산했으므로 0은 모든 자리에 있는 수가 0이므로 결과 값이 0이 된다. 이를 이용하면 누적해서 xor을 계산해 둠으로써 쿼리의 연산을 빠르게 해결할 수 있다. 아래 그림을 보며 생각해보자 위 .. 2024. 11. 7.

[백준/C++] 도로 네트워크 (No. 3176) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 먼저 이 문제를 풀기 전에 LCA 2 문제를 풀 수 있다면 이해하는데 도움이 많이 된다. " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 도로 네트워크 문제는 N개의 노드에 대해 N-1개의 간선이 있으며, 다른 도시로 이동할 수 있는 최단 경로가 유일하게 하나 존재한다.즉, 잘 생각해보면 이 그래프는 트리 구조를 이루고 있다는 사실을 알 수 있다. 문제에서 A 도시에서 B 도시로 가는 경우에 최소 비용과 최대 비용을 구하라고 했으며, 경우가 K로 최대 10만이기 때문에 단순 탐색을 반.. 2024. 11. 5.

[백준/C++] 벌레컷 (No. 27651) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 조건을 파악하면 빠르게 풀 수 있는 문제다. 구간은 [머리, 가슴, 배] 이며 조건은 (머리 구간 합 그럼 구간을 크게 [LEFT, CENTER, RIGHT] 로 나눌 수 있다. 이제 이를 이용해 문제를 풀 수 있는데, RIGHT 구간의 값이 정해졌을 때, CENTER의 값이 RIGHT보다 크면서 LEFT 구간이 RIGHT 구간보다 작도록 만족하는 구간 중 가장 큰 인덱스를 찾으면 된다. 즉 그림을 참고하면 위 그림과 같이 표현할 수 있는데 조건을 만족하면서 가장 큰 index를 찾으면 index의 값이 경.. 2024. 10. 31.

[백준/C++] 조 짜기 (No. 2229) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 문제에 대한 설명이 애매해서 추가하면, 나이로 정렬을 했기 때문에 붙어있는 사람들끼리 조를 이루어야한다는 조건이 추가되어야 한다. 즉, A, B, C 순서로 있다면, [A, C]로 조를 만들 수 없지만, [A, B, C]로 조를 만들 수 있다는 뜻이다. 이제 이를 이용해 문제를 풀어 나가면 된다. 만약 i번째 사람까지 조가 정해졌다면, 그때의 최대 값을 이용해 j번째 사람까지 조가 이루어졌을 경우의 최대값을 갱신해 나가면서 풀 수 있다. 이렇게 단계로 풀 수 있기 때문에 DP 배열을 이용해 풀 수 있다. dp[.. 2024. 10. 29.

[백준/C++] Tree (No. 13244) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 트리의 특징을 잘 알고있으면 쉽게 풀 수 있는 문제다. 먼저 트리의 특징은 사이클이 없고, 한 노드에서 경로를 따라 다른 모든 노드에 방문할 수 있어야한다는 점이 있다. 그러므로 이러한 조건을 만족하는 경우를 찾아 tree인지 graph인지 출력하면 되는 문제다. 먼저 트리의 특징을 이용하면 쉽게 N과 M의 수를 이용해 트리인지 그래프인지 판단할 수 있다.트리는 노드의 개수가 N일 때 경로(간선)의 개수가 N-1이라는 특징이 있다. 만약 경로가 N-1보다 크다면, 사이클이 무조건 존재하게 된다.경로가 N-1.. 2024. 10. 28.

[백준/C++] 규칙적인 보스돌이 (No. 29792) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 N, M, K가 작고 max값을 이용하면 쉽게 풀 수 있는 문제다. 먼저 각 캐릭터가 15분동안 사냥을 할 수 있기 때문에 N개의 캐릭터가 15분 동안 보스를 잡아 얻을 수 있는 메소의 최대값을 구하면 된다.이후 캐릭터를 M개 선택할 수 있으므로 정렬해서 메소를 얻을 수 있는 캐릭터를 M개 선택하면 된다. 이때, 보스를 잡아서 얻을 수 있는 메소를 나타내는 방법은 다음과 같다. 먼저 i번째 보스를 잡을 때 타임이 T만큼 걸린다고 가정하고 얻을 수 있는 메소가 D라고 하자.이후 현재 시간이 S라면 V[S] +.. 2024. 10. 24.

[백준/C++] Fly me to the Alpha Centauri (No. 1011) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 잘 생각하면 쉽게 풀이방법을 생각할 수 있다. 이동거리가 1 증가, 그대로, 1 감소 3가지 경우 중 하나기 때문에 최대한 빠르게 이동하려면1, 2, 3, 4, ... n-1, n, n, n-1, ... 3, 2, 1 와 같은 방법으로 이동하는 게 가장 빠르다. 이를 이용해 (1~n, n~1)의 이동거리가 y와 x 의 거리의 차이보다 작거나 같으면서 가장 큰 n을 찾으면 된다. 예를 들어 만약 y와 x의 거리 차이가 7이라고 가정해보자. 그러면 위 조건을 만족하는 n은 2가 된다. 이후 현재 이동거리가 1,.. 2024. 10. 22.

[백준/C++] 전화번호 수수께끼 (No.14369, 14370) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 완전탐색을 해야하나? 생각이 들었다.그런데 0~9 를 영어로 표현하면 0은 'Z' 처럼 한번만 나와서 빠르게 0의 개수를 파악할 수 있다는 생각에 각 수를 영어로 표현하기 시작했다. 처음에는 Z나 8의 G처럼 구분되는 수만 빼려고 했는데, 잘 생각해보니 0을 빼면 Z, E, R, O 각 글자가 하나씩 빠지면서 문자의 개수로 특정 수가 몇 개 인지 파악이 되겠다는 생각이 들었다. 그렇게 알파벳의 개수로 숫자가 몇 개 인지 파악할 수 있는 경우를 구해나갔고 알파벳의 개수를 잘 세면 매우 빠르게 문제를 풀 수 있음을.. 2024. 10. 21.

[백준/C++] 마법천자문 (No. 23325) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 모든 경우에 대해 계산을 하게되면 매우 많은 경우가 발생하므로 다른 방법으로 풀어야 한다. 이때, 잘 생각해보면 우리가 원하는 값은 최대 값이므로 특정부분까지 계산하는 방법이 매우 다양해도 최대값만 고려하고 다른 방법은 고려하지 않아도 된다는 것을 알 수 있다. 그러므로 이를 이용해 DP로 해결했다. 푸는 방법은 간단하다. DP[i] = i번까지 계산한 방법 중 최대값 으로 정의한다. 그러면 DP[i] 뒤에 이어지는 연산을 생각해보면 i+1은 무조건 연산자가 된다. 그리고 i+2는 무조건 숫자기 때문에 아래.. 2024. 10. 18.

[백준/C++] 빠른 무작위 숫자 탐색 (No. 25688) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 예전에 풀었던 실버 문제 중 이와 비슷한 문제가 있어서 쉽게 풀 수 있었다. 푸는 방법은 어떤 순서로 가야 가장 빠르게 방문할 수 있는지 브루트 포스로 탐색을 해야하는 문제다.단지, 예전에 풀었던 문제랑 다른 점은 A에서 B로 가는 경우를 BFS로 갈 수 있는지 탐색해야 한다는 점이었다. 1~6번 수 들을 방문하는 경우의 수 즉, 6!의 경우를 계산하도록 구현하면 된다. 이때, 1~6번 숫자를 방문했는지 체크하기 위해 bit연산을 사용했다.(visited 배열로 체크해도 상관없다) 이제 실제로 어떤 방법으로 구현했는지.. 2024. 10. 17.

[백준/C++] 가운데에서 만나기 (No. 21940) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 풀 때, 어떤 답을 원하는지 정확히 알기 힘들었다... 일단 왕복시간이 a도시에서 b도시를 방문하고 a도시로 돌아오는 경우로만 정의되어있어 아무 값이나 사용하면 되는지, 최솟값을 사용해야하는지 명확하지 않았다. 친구들의 왕복시간 들 중 최대가 최소가 되는 도시 X를 선택한다. 라는 지문이 있는데 이 의미가 먼저 친구들이 i도시를 왕복하는 시간들을 각각 구한다.그 다음 그 왕복 시간 중 최대값을 구한다.이제 1~N번 도시까지 구한 최대값을 비교하고 그 중 최솟값을 찾아 최솟값인 도시의 번호를 출력한다... 2024. 10. 12.

[백준/C++] 벼락치기 (No. 14728) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 기준만 잘 잡으면 풀 수 있다. 공부할 수 있는 최대 시간이 10000이므로 아래와 같은 배열을 하나 만든다. 이 배열은 T시간동안 공부했을 경우 얻을 수 있는 점수의 최대값을 저장하는 배열이다.그리고 전부 -1로 초기화를 한 다음 시간이 0 인 경우만 0으로 초기화한다.여기서 DP[T] = -1일 경우는 현재 T시간을 공부하는 방법이 없다는 뜻이다. 그 후 입력을 받아 n개의 공부의 값을 이용해 위 배열을 채워나가면 된다.(이때, 과목에 대한 시간 = E, 성과 = V라고 하자) 10,000 부터 0 .. 2024. 10. 9.

[백준/C++] 직각삼각형 (No. 1711) 문제 문제 설명 " data-ke-type="html"> HTML 삽입미리보기할 수 없는 소스 풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 풀 때, 처음에 잘못 생각해서 단순 반복으로 구하면 되는 문제인 줄 알았다.실제로도 풀려서 잘 풀렸구나 싶었는데, 막상 다른 사람들의 풀이를 보니 시간이 적게 걸려서 구경했다. 다시보니 내 풀이가 약 561,375,500의 경우를 계산하는 풀이였었다는 걸 그 때 알았다;;약 1500C2의 경우로 해결된다고 착각했었다.. 다른 사람들의 풀이를 보니 시간을 조금 더 줄일 수 있는 풀이는 내적과 비율을 이용하는 방법이 있었다. 내적한 값이 0이 되려면 a벡터의x * b벡터의x = -a벡터의y * b벡터의y 이 성.. 2024. 10. 8.

[백준/C++] 계란으로 계란치기 (No. 16987) 문제 문제 설명 "> HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때 가장 효율적인 방법이 있을까? 고민했지만 방법이 떠오르지 않았다.그래서 완전 탐색으로 모든 경우를 고려해 계란을 깨는 방법을 선택했다. 이러한 방법이 가능한 이유는 N이 8로 작기 때문에 8^8 = 2^24로 충분히 빠르게 해결이 가능하기 때문이다. 1번 계란부터 차례대로 다른 계란을 치는데 만약 깨져있다면 넘어가도록 코드를 구현했다. 이 과정에서 내구도와 무게가 저장된 vector가 계속 복사되지 않도록 Call by Reference를 이용했다. i번 계란으로 j번 계란을 칠 수 있다면 i.. 2024. 10. 1.

이전 1 2 3 4 ··· 9 다음

티스토리툴바