기로에 서다

문제 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. 문자열이 팰린드롬인 경우) 일반적인 팰린드롬의 성질에 대해서 생각해볼 때, 문자열의 시작과 끝 중에서 한 글자만 빠져도 팰린드롬이 깨진 다는 걸 알 수 있습니다. 모든 문자가 같은 문자열일 경우 모든 부분문자열에 대해 각 ..

문제 www.acmicpc.net/problem/2381 2381번: 최대 거리 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 각 점의 x, y좌표가 주어진다. 각 좌표의 범위는 -1,000,000이상 1,000,000이하이다. www.acmicpc.net 풀이 절댓값을 풀어서 나오는 네 가지 경우는 아래의 꼴입니다. 1. $±((a + b) - (c + d))$ 2. $±((a - b) - (c - d))$ 각 식을 살펴보면 결국 두 점간의 거리를 구하는 게 x, y좌표 대, 소관계와 관계없이 좌표 간의 합(차)의 차이를 구하는 것과 같고, 이에 최대 거리를 구하는 것은 각 좌표 간 합(차)의 최대 값에서 최소 값을 빼는 것과 같습니다. 코드 #include using namespace std; int..

문제 www.acmicpc.net/problem/5980 5980번: Corn Maze This past fall, Farmer John took the cows to visit a corn maze. But this wasn't just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both www.acmicpc.net 문제 풀이 알파벳으로 입력받는 Transport해주는 점들의 좌표를 따로 관리해주며 그 점들 간의 이동시에는 0 코스트가 들기 때문에 방..

문제 www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제 풀이 지나갈 수 있는 최소 값과 최대 값을 투포인터로 관리하며 시작점부터 bfs를 통해 끝점까지 가는 경우에 최대 값 - 최소 값을 갱신해준다면 $O(N^2*200)$으로 시간내에 답을 구할 수 있습니다. 코드 #include using namespace std; typedef pair pi; const int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,..

문제 www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 각 R줄 동안 C만큼의 문자열이 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제 풀이 1. 빙하가 녹는 시간마다 BFS를 돌릴 때, 최악의 경우 $O(R*C*max(R,C))$로 TLE가 난다. 2. 이에 빙하가 녹는시간을 BFS 한번으로 전처리한 후, 빙하가 녹는 시간에 대한 백조의 이동을 줄여보기로 한다. 3. 백조가 만날 수 있는 최소시간이 T초일 때, T-1초엔 녹지않은 빙하때문에 만날 수 없다는 점에서 "시간이 T일 때 백조가 만날 수 있는 가?" 라는 결정함수..