솧로그

https://www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1, www.acmicpc.net m명에게 과자를 나눠줄 수 있는 과자의 최대 길이를 구해야 한다. 따라서 과자들을 정렬한 후에 이분탐색으로 그 최대 길이를 찾으면 된다. 주의할 점은 다음과 같다. 하나의 과자를 여러 조각으로 나눌 수 있다(예제 2 참고). 따라서 주어진 과자 갯수보다 조카 갯수가 더 많아도 가능하다. 따라서 과자들을 탐색하면서..

https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 각 자리의 알파벳을 바꾸는 횟수와 자리를 이동하는 횟수를 더하면 된다. 각 자리의 알파벳을 바꾸는 횟수는 간단하다. answer += Math.min(name.charAt(i) - 'A', 26 - (name.charAt(i) - 'A')); 자리를 이동하는 횟수를 구하는게 어렵다. 자리를 이동하는 방법은 다음과 같이 3가지가 있다. 쭉 오른쪽으로 이동 먼저 오른쪽으로 가다가 왼쪽으로 이동 먼저 ..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 처음에는 좀 막혔는데 아이디어만 잘 생각하면 쉽게 풀 수 있다. dp[i]를 i를 포함한 연속 합의 최댓값이라고 했을 때, dp[i] = max(dp[i - 1], input[i])이다. 주의할 점은 dp[i]가 i까지의 최댓값이 아니라, i를 포함한 경우의 최댓값이다. 따라서 답은 dp[n]이 아니라, dp 배열에서의 최댓값이다. 입력 값으로 음수가 주어질 수 있다(ex, -1, -2, -3). 즉 dp ..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 지난 번에 푼 퇴사 문제와 동일한데 N의 범위만 커졌다. 따라서 퇴사 문제의 답을 제출하면 시간 초과가 나고, O(N)의 시간 복잡도로 해결해야 한다. 코드를 보면 금방 이해할 수 있다. 주요 포인트는 다음과 같다. max는 i 날짜까지의 최대 수입을 의미한다. i 날짜에 일을 시작하면 일이 끝난 다음날인 nextDay에 돈을 받는다고 가정한다. dp[nextDay]..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net dp 문제이고 내가 실수한 코드는 다음과 같다. for (int i = 1; i = 0; j--) { if (input[j] < input[i]) { dp[i] = dp[j] + input[i]; break; } } } 그런데 만약 input 값이 "20 60 50 70"인 ..

https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net bfs 문제로 크게 막힘없이 풀 수 있었다. 다만 주의할 점과 내가 놓친 부분은 다음과 같다. 상근이는 불이 붙으려는 칸으로 이동할 수 없다. 그리고 상근이가 있는 칸에 불이 옮겨옴과 동시에 상근이가 다른 칸으로 이동할 수 있다. 따라서 불이 먼저 이동하고, 상근이가 이동해야 한다. 불과 상근은 시간 당 한 칸씩 이동할 수 있다. 따라서 fireQue.size()만큼 각 불들이 한 칸씩 이동하도록 하고, pe..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 상하좌우로 총 5번 움직였을 때 그래프에 있는 가장 큰 수를 구하는 문제이다. 따라서 상하좌우로 5번 움직이는 조합을 찾기 위해 재귀를 사용해야 한다. 그리고 상하좌우로 움직이는 로직을 구현해야 한다. 기존 배열을 보고 새로운 배열을 만들어야 한다. 새로운 배열에 값을 채울 인덱스인 fillIdx와 기존 배열과 값을 비교할 인덱스인 checkIdx가 필요하다. 기존 배..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 일차원 그래프의 bfs 문제이다. 주의할 점은 다음과 같다. 최소 시간을 구해야 하기 때문에 dfs가 아닌 bfs로 풀어야 한다. 최소 시간을 각 그래프의 위치에 저장해준다. 한 칸 뒤로 이동, 한 칸 앞으로 이동, 두배 앞으로 이동으로 한 위치당 총 3번의 탐색을 하면 된다. 그래프를 벗어나거나 이미 방문한 위치인 경우에는 탐색하지 않는다. (최소 시간을 갱신X) 내가..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 해결법을 떠올리는 건 쉽다. 연산의 최소 값을 구해야 하므로 -가 붙는 수를 최대한 크게 만들면 된다. 예를 들어 다음과 같이 식이 있다고 가정하자. a + b - c + d + e -f 그러면 -의 값을 최대한 크게 만들기 위해 c, d, e를 한 묶음으로 묶어주면 된다. 문제는 값이 입력될 때 숫자와 연산자를 어떻게 구분하고 어떻게 저장할지 고민이었는데.. -를 기준으로 먼저 나눈 ..

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net bfs 문제인데 이 문제를 풀며 주의할 점이 몇가지 있다. 논리적으로 불과 지훈이 동시에 이동해야 한다. 따라서 코드 상으로 불과 지훈이 순차적으로 한 번씩 이동해야 하는데, 둘 중에 불을 먼저 이동시켜야 한다. 불이 먼저 이동해서 불이 번지면, 지훈이가 불이 있는 곳을 피해서 이동해야 하기 때문이다. 불을 한 번 이동시킬 때는 fireQue의 사이즈만큼 이동을 처리해주어야 한다...