기로에 서다

문제 www.acmicpc.net/problem/20164 20164번: 홀수 홀릭 호석 호석이는 짝수랑 홀수 중에서 이니셜이 같은 홀수를 더 좋아한다. 운전을 하던 호석이는 앞차의 번호판이 홀수로 가득할 때 사랑스러움을 느낄 정도이다. 전화번호도 홀수만 있고 싶다. 그렇게 www.acmicpc.net 풀이 문제의 연산을 살펴보면 숫자를 세 개의 숫자로 분할하거나, 숫자의 자릿수들을 검사하므로 편의를 위해 다루는 숫자들을 문자열로 처리하기로 하며, 이 문제의 시작이자 끝인 분할하는 함수를 생각해봅시다. 1. 숫자를 분할하고 새로운 숫자를 만들어내는 연산을 한 후, 새로운 숫자도 연산을 거쳐야 하므로 분할하는 과정은 재귀를 사용해 해결해야 함을 알 수 있습니다. 2. 아래의 그림과 같이 길이가 k$(k>=..

문제 www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 1. 어떤 칸에 빗물이 채워지는 조건에 대해서 생각해볼 때, 그 칸을 제외한 (좌측의 최대 높이, 우측의 최대 높이) 둘 중 작은 높이에서 어떤 칸의 높이를 뺀 만큼 채워진다는 걸 알 수 있습니다. (물론 물이 채워져야 하므로 좌측의 최대 높이, 우측의 최대 높이는 어떤 칸의 높이보다 높아야 합니다.) 2. i칸을 제외한 i칸 좌측의 최대 높이를 $pre[i]$, 우측의 최대높이를 ..

문제 programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 풀이 1. 이동하는 비용에 대해서 살펴보면 다음 칸으로 이동할 때의 방향이 현재 칸으로 이동한 ..

문제 programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 풀이 1. 어떤 조건(모든 보석종류를 포함)을 만족하고 연속되는 가장 짧은 구간을 찾는데 N의 상한이 10^5이기에 투포인터로 푸는문제임을 알 수 있습니다. 2. 보석의 이름을 매핑하며 모든 보석의 종류의 개수를 세어줍니다. 3. "[l, r)구간의 보석의 종류(Curkind)가 모든 보석의 종류(Allkind)를 포함하는가?" 라는 조건을 기준으로 l, r을 움직이는데 현재 보는 보석의 개수(gemscnt)를 관리해가..

문제 programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 풀이 1. 우선 구해야하는건 + , - , * 의 서로 다른 연산자 우선순위 3!가지 순열을 구성해보고 모든 연산결과의 최소를 구하는 것입니다. 2. 입력으로 받은 문자열에 숫자와 연산자가 섞여있으므로 주어진 식을 파싱해가며 우선순위가 서로 다른 연산자 식을 계산하기 간편하게 중위표기식에서 후위표기식으로 변환해줍니다. 3. 중위표기식에서 후위표기식(post)으로 바꾸는..

문제 programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 풀이 $$(R, C) = ((numbers[i] - 1) / 3, (numbers[i] - 1) \% 3)$$ 1. 키패드를 좌표계라고 생각한다면 0을 제외한 번호 i의 좌표는 위와 같이 바꿀 수 있고, 마찬가지로 손의 위치도 간단하게 좌표로 나타낼 수 있습니다..

문제 www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 문제 풀이 간단한 구현 문제이지만 신경 써야 할 부분이 몇 가지가 있었습니다. 1. 로봇이 내리는 경우는 벨트가 한 칸 회전해서 N번칸에 도착하거나 N-1번 칸의 로봇이 이동하여 N번칸에 도착하였을 때 총 두 가지뿐입니다. 2. 조금만 생각해보면 항상 로봇이 타는 번호가 1번이며 먼저 탄 로봇이 먼저 내리고 내리는 칸이 N번 칸이므로 로봇이 (N+1) ~ 2*N번 칸인 컨베이너 벨트 ..

문제 www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이�� www.acmicpc.net 문제 풀이 1. 두 점을 연결하는 비용은 각 x, y, z좌표끼리 차의 최소 값이므로 N개의 행성을 연결하려면 좌표끼리의 차를 값으로 가지는 N - 1개의 간선을 찾아야 합니다. 2. 이는 아래의 관찰을 통해 각 축에 대해서 좌표를 정렬했을 때 인접한 점들의 차만 간선에 추가하는 방법을 통해 해결했습니다. 서로 인접한 세 점 A, B, C에 대해 모든 점을 연결할 때, ..

문제 www.acmicpc.net/problem/12107 12107번: 약수 지우기 게임 1 N=4인 경우, A는 처음에 4,2,1을 지운다. 칠판에 남은 수는 3으로, B는 3을 지울 수밖에 없어 패배한다. www.acmicpc.net 문제 풀이 모든 수의 약수인 1을 제외한 N-1개의 수로 게임을 진행했을 때의 결과로 N개의 수를 뽑는 상황을 생각해보면 아래와 같습니다. 1. N - 1개의 수로 게임했고, 마지막 순서가 상대(B)에게 갈 때 A가 처음 뽑은 수의 약수에 1을 포함한다면 똑같이 마지막 순서가 상대에게 가므로 (A)승리 2. N - 1개의 수로 게임했고, 마지막 순서가 나(A)에게 올 때 A가 처음 순서에 1만 집고 시작하면 마지막 순서가 상대에게 가므로 (A)승리 3. 따라서 N이 1..

문제 www.acmicpc.net/problem/15927 15927번: 회문은 회문아니야!! 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 www.acmicpc.net 문제 풀이 1. 문자열이 팰린드롬이 아닌 경우) 문자열 그 자체가 팰린드롬이 아닌 가장 긴 부분 문자열의 길이이므로 그 길이를 출력하면 됩니다. 2. 문자열이 팰린드롬인 경우) 일반적인 팰린드롬의 성질에 대해서 생각해볼 때, 문자열의 시작과 끝 중에서 한 글자만 빠져도 팰린드롬이 깨진 다는 걸 알 수 있습니다. 모든 문자가 같은 문자열일 경우 모든 부분문자열에 대해 각 ..