컴굥일지

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42842 문제 내용 위의 사진과 같이 안쪽에 노란색 칸들이 있고, 이를 1줄로 감싼 갈색 칸들이 있다. 갈색 칸의 개수와 노란색 칸의 개수가 주어질 때, 전체 카펫의 가로, 세로 길이를 구하면 된다. 문제 풀이 문제의 상황을 그림 그려보면 위와 같다. 우리는 a와 b에 어떤 값이 들어가면 되는지를 찾으면 쉽게 문제를 해결할 수 있다. 이때 갈색 격자의 수는 8~5,000, 노란 격자의 수는 1~2,000,000라고 한다. 즉 2a*2b+4

문제 https://www.acmicpc.net/problem/11564 문제 내용 좌표축이 -10^18 ~ 10^18까지 주어진다. 점프력 k와 초콜릿이 놓여있는 시작 위치 a, 끝 위치 b를 입력받아 몇 개의 초콜릿을 먹을 수 있는지 출력한다. 점프 횟수에는 제한이 없다. 문제 풀이 일단 좌표의 범위가 int 범위를 넘어가기 때문에, long long으로 선언한다. 점프력이 k로 고정되어 있고, 점프 횟수에 제한이 없기 때문에, 수학적으로 계산만 하면 된다. 0으로 시작하거나 끝나거나, 0을 포함하는 구간의 경우에는 초콜릿이 0번 자리에도 있으니 +1 하는 것을 잊으면 안 된다. 0이 포함되지 않고 한쪽으로 치우쳐져 있는 경우는, 음수나 양수나 계산 방법이 똑같다. 편의를 위해 음수일 경우 양수로 바..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12973 문제 내용 문자열에서 같은 글자 2개가 붙어있으면 제거해 주면 된다. (계속해서 지워나가야 함) b aa baa -> bb aa -> aa -> 위와 같이 연달아 같은 문자가 있으면 제거해주면 된다. 끝까지 제거했을 때, 문자열을 모두 제거할 수 있으면 1을, 문자열이 남게 되면 0을 return 한다. 문제 풀이 맨처음에는 문자열에서 붙어있는 곳을 찾아서 그 부분만 빼고 삭제하는 방법으로 구현을 했다. 이 풀이는 반복문을 여러 번 돌아야 하기 때문에 효율성 체크에서 실패가 떴다. (해당 코드가 궁금하면 더보기 클릭) 더보기 정확성 체크는 통과, 효율성 체크는 실패하는 코드 #inclu..

문제 https://www.acmicpc.net/problem/2170 문제 내용 선분을 여러 개 입력받아, 선분끼리 이을 수 있는 것은 잇는다. 최종적으로 그려져있는 선들의 길이의 총합을 구하면 된다. (서로 이어진 선분은 하나의 선으로 생각한다) 문제 풀이 골드 5 문제이지만, 문제의 풀이 방법을 떠올리면 그렇게 어렵지 않다. 1. 먼저 선분들을 정렬한다. (c++ sort 함수 쓰면, 선분의 시작이 증가하는 순으로 + 같을 경우 선분의 끝 지점이 증가하는 순으로 알아서 정렬해준다.) 2. 선분이 이어지는지를 체크한다 ( 이전 선분의 끝 지점 >= 현재 선분의 시작 지점 )이면 두 선분은 이어진다고 볼 수 있다. 이 경우, 이전 선분의 끝 지점을 갱신해 주면 된다. (max 값으로 갱신해야 한다. (..

문제 https://www.acmicpc.net/problem/7576 문제 내용 1은 익은 토마토를, 0은 아직 익지 않은 토마토를, -1을 토마토가 없는 칸을 뜻한다. 토마토는 인접한 토마토에게 영향을 받는데, 익은 토마토 옆의 익지 않은 토마토는 하루 뒤에 익게 된다. 토마토가 모두 익을 때까지의 최소 날짜를 출력하면 된다. (불가능한 경우 -1 출력) 문제 풀이 bfs로 문제를 풀면 된다. 단, 처음 시작할 때 1이었던 토마토들을 queue에 모두 넣은 상태로 돌려야 한다. 전부 익을 때까지 얼마나 걸리는지를 구하고 싶기 때문에, 이는 최단거리 문제라고 볼 수 있다. (거리는 아니지만 개념은 같다) 토마토 개수를 입력받을 때 세어둔 뒤에, bfs를 통해 익은 토마토를 체크하면서 -1 하고, 마지막..

문제 https://www.acmicpc.net/problem/10816 문제 내용 숫자 카드들을 입력받고 수를 입력받아, 그 수에 해당하는 숫자 카드의 개수가 몇 개인지를 출력하면 된다. 이때 숫자 카드의 개수는 500,000까지이고, 숫자 카드에 적혀있는 정수는 -10,000,000~10,000,000이다. 입력받는 수 또한 500,000개까지 주어질 수 있다. 문제 풀이 배열을 크게 선언해두고, 있으면 값을 증가시키는 방법은 사용할 수 없다. 숫자 카드에 적힌 정수의 범위가 너무 크기 때문이다. 이 문제는 이분탐색을 사용하면 좋다. 이분탐색이라 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법으로 탐색 전에 반드시 ..

문제 https://www.acmicpc.net/problem/1806 문제 내용 합이 S이상이 되는 연속되는 수열의 부분합 중에, 가장 짧은 길이를 출력하면 된다. 문제 풀이 투포인터 방식으로 문제를 해결하면 쉽게 해결할 수 있다. st와 en 포인터를 두고, st~en까지의 합이 S보다 작으면 en을 증가시키고, 그렇지 않으면 st를 증가시키면 된다. 인덱스(st, en)가 바뀌면 total 값도 조정을 해주어야 한다. st가 en을 앞서는 순간이 오거나, st나 en이 n이 되면 break를 걸어 불필요한 연산을 줄이고 인덱스 에러를 막아야 한다. 또한 합이 S이상인 부분합을 만들지 못하면 0을 출력해야 한다는 것을 놓치면 안 된다. 코드 #include #include using namespace..

문제 https://www.acmicpc.net/problem/14888 문제 내용 연산에 사용될 수들과 연산자가 주어진다. 연산에 사용되는 수들은 순서를 바꾸지 않고 입력된 순서대로 사용한다. 연산자는 순서를 바꾸어 식을 계산했을 때 가장 큰 결과와 작은 결과를 출력하면 된다. (단, 연산은 우선순위 관계없이 좌->우로 계산한다.) 문제 풀이 백트래킹을 통해 연산자의 순서를 결정하면 된다. 같은 연산자가 여러번 사용될 수도 있지만, 개수의 제한이 있다는 것을 유념해야 한다. 아래 N과 M(9) 문제와 푸는 방식이 유사하다. [BOJ/백준 15663][C++] N과 M (9) 문제 https://www.acmicpc.net/problem/15663 문제 내용 입력받은 N개의 자연수 중에 M개를 골라 수열..

문제 https://www.acmicpc.net/problem/2193 문제 내용 n자리 이친수의 개수를 구하면 된다. 이친수란 아래와 같다. 1. 이친수는 0과 1로만 이루어져 있다. 2. 이친수는 0으로 시작하지 않는다. (== 1로만 시작한다.) 3. 이친수에서는 1이 두 번 연속으로 나오지 않는다. 문제 풀이 dp로 해결할 수 있는 문제이다. dp[i][0]은 마지막이 0으로 끝나는 i자리 이친수, dp[i][1]은 마지막이 1로 끝나는 i자리 이친수로 설정해 두고 문제를 풀었다. 0으로 끝나는 이친수는 이전까지의 이친수가 1로 끝나든 0으로 끝나든 상관이 없다. 하지만, 1로 끝나는 이친수는 이전까지의 이친수가 반드시 0으로 끝나야 한다. +) 배열을 int로 선언하면 오버플로우가 발생하기 때문..

문제 https://www.acmicpc.net/problem/1149 문제 내용 n개의 집을 빨/초/파 3가지 색으로 칠하려고 한다. 각각의 집을 3가지 색으로 칠할 때의 비용이 주어졌을 때, 모든 집을 칠하는 최소 비용을 구하면 된다. 단, 인접한 집은 서로 색이 달라야 한다. 문제 풀이 dp로 문제를 풀 수 있다. dp[i][0]은 i번째 집을 칠하기까지 필요한 비용 (단, i번째 집은 빨간색) dp[i][1]은 i번째 집을 칠하기까지 필요한 비용 (단, i번째 집은 초록색) dp[i][2]은 i번째 집을 칠하기까지 필요한 비용 (단, i번째 집은 파란색) 이런 식으로 설정하고 문제를 풀면 쉽게 해결할 수 있다. 코드 #include using namespace std; int main() { in..