본문 바로가기

Algorithm279

[백준/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++] [PCCP 기출문제] 3번 / 충돌위험 찾기 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 생각보다 구현이 까다로웠던 문제다.특정 위치에서 로봇들이 서로 충돌하는지 파악하고 그 지점의 수를 더하면 되는 문제다. 다양한 방법이 있겠지만, 기본적으로 로봇이 움직이는 규칙이 있기 때문에 row 위치가 다르면 row방향으로 움직이고 그다음에 column방향이 다르면 column방향으로 이동하는 움직임을 한다. 그러므로 이를 이용해 특정시간에 로봇들의 위치를 파악하면 어느 위치에서 겹치는지 파악할 수 있다. 처음에는 각 r * c * 시간 으로 3차원 vector를 만들어 저장하려고 했다. 하지만, 이렇게 .. 2024. 10. 4.

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

티스토리툴바