본문 바로가기
반응형

전체 글308

[프로그래머스/C++] 스티커 모으기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 하나의 스티커를 떼면 양옆의 스티커를 사용할 수 없게 된다. 원으로 이어진 스티커를 위와 같이 직선으로 생각해 보자. 만약 첫번째 스티커를 뗀다면 마지막 스티커는 원형이므로 첫번째 스티커와 붙어있어 뗄 수 없게 된다. 하지만 첫번째 스티커를 그대로 둔다면 마지막 스티커를 뗄 수 있게 된다. 그러므로 2가지 경우를 생각해 각각 계산하고, 첫번째 스티커를 떼는 경우가 스티커 숫자의 합이 높은지 안떼는 경우가 스티커 숫자의 합이 높은지 계산하면 된다. 이제 어떤 스티커를 떼야하는지는 어떻게 알 수 있을까? 스티커가 위 그림처럼 나열되어 있을 때, i번째 스티커를 떼려면 i - 1번째 스티커는 떼지 않은 상태.. 2024. 3. 14.
[프로그래머스/C++] 미로 탈출 명령어 (2023 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 미로를 통과하기 위한 여러 경로 중 오름차순으로 가장 빠른 경로를 return하면 되는 문제다. 먼저 정확히 k번을 움직여 그 도착점에 도달해야하기 때문에 도달이 가능한지 판단하는 것도 중요하다. 만약 위 그림처럼 시작점과 목적지가 주어졌다면, 시작점에서 목적지로 도달하기 위해서는 짝수 번 움직여야한다. 왜냐하면 도착지점과 시작지점의 거리가 3+3 = 6으로 짝수이기 때문이다. 만약 k가 홀수라면 어떤 방법을 써도 도달할 수 없다. 이유는 쉽게 생각할 수도 있지만, 굳이 수식을 써서 증명을 해보면 먼저 s의 좌표를 sx, sy라고 하자 이제 상하좌우로 움직이는 횟수를 a, b, c, d로 표현하면 이동.. 2024. 3. 13.
[백준/C++] 수열 회전과 쿼리 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 수열의 회전에 관한 문제다. 문제의 내용을 보면 수열을 이동하는 쿼리와 수열의 특정 범위의 합을 묻는 쿼리에 대해 답을 출력하는 문제다. 여기서 특정 범위의 합은 매번 계산하기보다 누적합을 이용하면 한번의 계산으로 답을 출력할 수 있다. 수열의 이동은 원순열을 생각하면 편하다. (한쪽 끝으로 이동하다가 범위를 넘어서면 반대쪽으로 넘어간다) 먼저 처음에 시작 index를 정한다. 이제 수열의 시작 부분이 k만큼 증가하면 이는 시작 index가 오른쪽으로 이동한 것과 같다. 만약 시작 부분이 k만큼 감소하면 이는 시작 index가 왼쪽으로 이동한 것과 같다. 여기서 합을 구하는 범위가 N을 넘어가지 않기 .. 2024. 3. 12.
[프로그래머스/C++] 지형 편집 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 봤을 때, 블록의 층에 해당하는 높이가 최댓값이라는 사실은 쉽게 추리할 수 있다. 예를 들어 블록의 층이 2층과 4층짜리만 있다고 가정하자. 이 경우 모든 블록을 2층으로 만들거나 4층으로 만들 경우에 답이 있다. 왜냐하면 3층에서 2층으로 만드는 비용을 a라고 하고, 3층에서 4층으로 만드는 비용을 b라고 하자. 그러면 위 그림처럼 4층에서 3층으로 가는 비용도 a로 같다. 그렇기 때문에 a와 b가 대소 관계를 갖게 된다면, 정답은 2층이나 4층에 있게 된다. (a==b인 경우만 3층일 경우가 정답이 될 수 있는데, 이 경우는 2층으로 쌓나 4층으로 쌓는 경우도 3층으로 쌓는 경우와 비용이 같게 된다.. 2024. 3. 11.
[프로그래머스/C++] 아방가르드 타일 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 DP문제면서 매우 간단한 줄 알았다... 하지만 정답이 아니길래 곰곰히 생각해봤더니 많은 패턴들이 숨어있었다. 먼저 아래 그림을 보자 단순히 3개를 연속으로 붙이는 경우와 1개를 붙이는 경우의 패턴이 있다. 저 패턴들을 붙였을 때 길이를 k라고 하면, 아래와 같이 나타낼 수 있다. $$DP[k-3] \times 1, \,\,\,\,\, DP[k-1] \times 1$$ k보다 길이가 3 짧은 경우에서 3개를 붙여 현재 패턴을 만들 수 있고, k보다 1개 더 길이가 짧은 경우에서 현재 패턴을 만들 수 있기 때문에 위처럼 나타낼 수 있는 것이다. + 이러한 타일링 문제를 처음 보면 세워져있는.. 2024. 3. 10.
[프로그래머스/C++] 등굣길 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 출발지에서 도착지까지 도달하는 최단경로의 개수를 return하는 문제다. 여기서 방향은 항상 오른쪽 아래로 움직이기 때문에, 일정 횟수를 움직여서 도달할 수 있는 위치는 정해져 있다. 그러므로 n칸 움직여서 도달할 수 있는 위치는 위와 왼쪽방향에 있는 n-1칸 움직여서 도달할 수 있는 곳의 경우의 수의 합과 같다. 아래 그림을 참고하면 이해가 쉬울 것이다. 위 그림과 같이 1, 1이 출발지 3, 4가 도착지라고 하면 각 칸까지 이동하는데 걸리는 경우의 수를 나타낼 수 있다. 예를 들어 (2,2)에 도달하는 경우의 수는 (1,2)에서 아래로 이동하는 경우와 (2,1)에서 오른쪽으로 이동하는 경우가 있다... 2024. 3. 8.
[프로그래머스/C++] 등산코스 정하기 (2022 KAKAO TECH INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제에서 핵심은 특정 노드를 방문할 때마다 경로 중에서 가장 시간이 오래걸린 값을 저장해야 된다는 것이다. 그리고 가장 시간이 오래 걸리는 구간의 크기가 같다면 봉우리의 숫자가 가장 작은 값을 return해야한다. 이와 비슷한 문제를 해결하는 알고리즘 중에는 다익스트라 알고리즘이 있는데, 다익스트라 알고리즘은 최단 경로를 구하는 알고리즘으로 가장 작은 값을 계속해서 계산해 나가는 알고리즘이다. 이 문제도 마찬가지로 항상 intensity가 가장 작은 값을 가지고 있으면서 만약 intensity가 같다면 mountain의 번호가 가장 작은 경로를 먼저 계산하면 편하다. 여기서 위 그림과 같이 S에서 시작을 한다.. 2024. 3. 7.
[프로그래머스/C++] 숫자 타자 대회 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때, 단순히 그리디로 풀 수 있나? 고민을 했다. 하지만 어떤 손가락을 움직일지 선택을 하기 위해서는 뒤에 오는 숫자들에 규칙같은게 있어야 하는데, 없기 때문에 그리디로 풀면 안된다는 결론이 나왔다. 그래서 생각한 방법은 탐색이었는데, 탐색도 그냥 하기에는 너무 많기 때문에 DP로 문제를 해결했다. 손가락 위치를 기준으로 특정 숫자를 입력할 때, 내 손가락의 위치를 기록한 vector가 있다면, 최악의 경우 100,000*10*10으로 문제가 해결되기 때문이다. 그리고 특정 번호에서 다른 번호로 이동해서 누르는 경우의 가중치를 쉽게 계산하기 위해 계산을 도와줄 2차원 vector를 만들었다... 2024. 3. 6.
[프로그래머스/C++] 기지국 설치 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 조금만 생각하면 쉽게 풀 수 있는 문제다. 아래 그림을 참고해 보자 여기서 기지국을 어떻게 설치해야 할까? 이미 설치된 기지국의 범위와 새로 설치하는 기지국의 범위가 같다는 점에 유의하면 기지국을 최소로 설치하기 위해서는 기지국이 설치되지 않은 연속된 칸을 기지국의 범위로 나누면 쉽게 해결할 수 있다. 그림에서 보이듯이 기지국을 설치할 때 차지하는 칸의 범위가 3이라면 1~2 범위는 크기가 2이므로 기지국을 하나 설치해서 그 범위를 메꿀 수 있다. 다음 범위는 6~9의 범위를 메꿔야 하는데, 범위의 크기가 4이므로 기지국을 2개 설치해야 메꿀 수 있다. 이처럼 연속으로 비어있는 부분의 크기를 기지국의 .. 2024. 3. 5.
[프로그래머스/C++] 억억단을 외우자 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때, 최악의 경우 5000000을 1~5000000 사이의 수로 나누어 보면서 개수를 세는 문제인가 생각이 들었다. 하지만 이 경우 N^2이 되기 때문에 불가능 했다. [첫 번째 풀이] 그래서 생각한 아이디어는 결국 곱셈해서 특정한 수가 나온다는 것은 약수의 개수와 같기 때문에 소인수 분해를 이용해 푸는 방법이었다. 여기에 e에 대한 수들을 전부 계산할 필요 없이 e/2까지만 계산하면 된다는 생각이 들었다. (e/2이하의 숫자라면 2를 곱해서 약수의 수가 더 많은 수를 만들 수 있기 때문이다.) 그러므로 최악의 경우 2500000*(logN 이하의 소수의 개수)로 문제가 해결 될 것이라고 .. 2024. 3. 5.
[프로그래머스/C++] 코딩 테스트 공부 (2022 KAKAO TECH INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 모든 문제를 풀기 위한 알고력과 코딩력을 상승시키고, 이때 최소 시간을 구하는 문제다. 여기서 문제를 풀기 위해서는 문제에서 요구하는 알고력과 코딩력을 만족해야 하므로, 모든 문제를 풀기 위해서는 각 문제에서 요구하는 알고력과 코딩력의 값 중 가장 큰 값 이상으로 능력을 올리면 된다. 여기서 최소 시간을 구해야 하는데 DP를 이용하면 쉽게 풀 수 있다. 특정 수치의 알고력과 코딩력을 갖추는데 걸리는 최소시간을 구하면, 이 최소 시간을 이용해 다른 특정 알고력과 코딩력을 갖추는데 걸리는 최소시간을 구할 수 있기 때문이다. (즉, 작은 문제를 해결하는 것으로 전체 문제를 해결할 수 있기 때문에 DP를 이용.. 2024. 3. 4.
[프로그래머스/C++] 단어 퍼즐 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 최솟값을 어떻게 찾을지만 고민하면 쉬운 문제다. 이전에 작은 문제들을 바탕으로 다음 문제를 해결하는 DP로 쉽게 풀 수 있는데, 왜냐하면 특정단어까지 만드는데 사용되는 최소횟수를 이용해 다음 문자까지 만드는데 사용되는 단어의 최소 횟수를 구할 수 있기 때문이다. 아래 그림을 보면 특정 문자가 주어지면 그 문자의 i번쨰 문자를 만드는데 단어가 사용되는 최소 횟수가 적혀있다. 이제 d라는 문자까지 만드는데 사용되는 최소 횟수는 다음과 같이 구해 볼 수 있다. 1. a에 "bacd"라는 문자를 더하기 2. b에 "acd"라는 문자를 더하기 3. a에 "cd"라는 문자를 더하기 4. c에 "d"라는 문자를 더.. 2024. 3. 3.
[백준/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.
[프로그래머스/C++] 짝수 행 세기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 아이디어가 정말 안 떠올랐다. 규칙을 발견해 조합으로 해결이 될 것처럼 보였는데, 아무리 고민을 해도 짝수개의 열을 만드는 작업이 잘 안됐다. 그러다가 다른사람의 질문에서 홀수와 짝수라는 힌트를 얻고 방법이 떠올라 문제를 해결할 수 있었다. 먼저 문제의 조건에서 a 배열의 특정 열에 1이 포함된 개수와 b 배열의 특정 열에 있는 1의 개수가 같아야 된다. 그렇기 때문에 이 조건을 만족하기 위해 a의 각 열 당 몇 개의 1이 있는지 개수를 센 다음에 그 열에 있는 1들의 개수만큼 각 행에 배치를 해주면 된다. 여기서 1의 개수를 배치하는 방법을 조합으로 나타낼 수 있는데, n개의 행에서 1을 배치할 r개.. 2024. 2. 29.
[CodeForce] Codeforces Round 929 (Div. 3) [A ~ F] 풀이 HTML 삽입 미리보기할 수 없는 소스 Dashboard - Codeforces Round 929 (Div. 3) - Codeforces codeforces.com HTML 삽입 미리보기할 수 없는 소스 [#A] A번 문제는 단순한 문제다. 특정 수열이 주어지면 2가지 작업을 수행할 수 있다. 한 가지 작업은 위치를 재배열 하는 것이고, 나머지 작업은 특정 범위안의 수에 -1을 곱하는 것이다. 이때, 두 작업을 수행한 뒤 수열의 합의 최댓값을 구하면 되는 문제다. 수열의 합이 최댓값이 되기 위해서는 모든 수가 음수가 아닌 양수가 되면 된다. 그러므로 위치를 재배열 할 때 음수들이 전부 붙어있게 재배치하고, 그 범위에 -1을 곱하면 전부 양수가 되므로, 결과값은 모든 배열의 수의 절댓값을 더한 값과 같다... 2024. 2. 28.
반응형

티스토리툴바