![]()
* 2/22 팀즈 미팅에서 푼 문제 해설입니다! 해당 문제는 "프로그래머스 - [코딩 테스트 연습] - 2020 카카오 인턴십 - 경주로 건설"에서 풀어보실 수 있습니다. 문제 건설회사의 설계사인 죠르디는 고객사로부터 자동차 경주로 건설에 필요한 견적을 의뢰받았습니다. 제공된 경주로 설계 도면에 따르면 경주로 부지는 N x N 크기의 정사각형 격자 형태이며 각 격자는 1 x 1 크기입니다. 설계 도면에는 각 격자의 칸은 0 또는 1 로 채워져 있으며, 0은 칸이 비어 있음을 1은 해당 칸이 벽으로 채워져 있음을 나타냅니다. 경주로의 출발점은 (0, 0) 칸(좌측 상단)이며, 도착점은 (N-1, N-1) 칸(우측 하단)입니다. 죠르디는 출발점인 (0, 0) 칸에서 출발한 자동차가 도착점인 (N-1, N-1..
![]()
* 2/22 팀즈 미팅에서 푼 문제 해설입니다! 해당 문제는 "프로그래머스 - [코딩테스트 연습] - 2021 KAKAO BLIND RECRUITMENT - 카드 짝 맞추기" 에서 풀어보실 수 있습니다. 문제 게임 개발자인 베로니는 개발 연습을 위해 다음과 같은 간단한 카드 짝맞추기 보드 게임을 개발해 보려고 합니다. 게임이 시작되면 화면에는 카드 16장이 뒷면을 위로하여 4 x 4 크기의 격자 형태로 표시되어 있습니다. 각 카드의 앞면에는 카카오프렌즈 캐릭터 그림이 그려져 있으며, 8가지의 캐릭터 그림이 그려진 카드가 각기 2장씩 화면에 무작위로 배치되어 있습니다. 유저가 카드를 2장 선택하여 앞면으로 뒤집었을 때 같은 그림이 그려진 카드면 해당 카드는 게임 화면에서 사라지며, 같은 그림이 아니라면 원..
www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 과정 더보기 현재 큐에 들어있는 초밥의 개수를 세기 위한 배열 sushi를 선언합니다. ex) sushi[3] = 2 → 3번 초밥이 2개 들어있다. 초밥을 큐에 넣을 때 다음과 같은 요소를 확인합니다. 1. 이미 큐에 존재하는 종류의 초밥인가? → 맞다면 가지 수는 변하지 않는다. → 아니라면 가지 수에 1을 더해준다. 2. 쿠폰에 해당하는 초밥인가? → 맞다면 b..
www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 수첩1, 수첩2에 적힌 수를 각각 입력받아 수첩2의 번호가 수첩1에 있었는지(0, 1) 출력하는 문제였습니다. 처음에 해시를 사용하여 풀었다가 시간초과가 나서 이분탐색을 사용하여 풀었습니다. 이분탐색에서도 시간초과가 났었는데, cstdio를 사용하니 해결되었습니다! 정렬 left = 0, right = N-1 mid = (left+right)/2 mid가 가리키는 값이면 return mid가 가리키는 값보다 클 때 ..
www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 알파벳 대문자로 이루어진 단어에서 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제. 0 ~ 9까지의 숫자는 10개이므로 백트래킹을 통해 풀 수 있습니다. 각 알파벳에 대응되는 숫자의 조합들을 백트래킹을 통해 구하고 각 알파벳을 숫자로 치환 후 계산하여 답을 구하면 됩니다. #include #include #include using namespace std; #define..
www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 이 문제는 DP, 다이나믹 프로그래밍을 설명할 때 A반에서 출제했던 문제입니다. 이 문제를 처음 보면 어렵게 느껴질 수 있지만 그림을 그려서 따라가다 보면 쉽게 해결 할 수 있는 문제입니다. 풀이 1. 왼쪽 전봇대를 기준으로 오름차순으로 정렬을 시킵니다. 2. 오른쪽 전봇대에서 "가장 긴 증가하는 부분 수열"을 구해줍니다. 3. 2번 과정에서 구한 "가장 긴 증가하는 부분 수열"의 크기를 N에서 빼주면 답이 됩니다. ..
www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net kau-algorithm.tistory.com/49 [모의 테스트 풀이] RGB거리 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다.. kau-algorithm.tistory.com R..
www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 위와 같은 재..
![]()
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net TOP-DOWN 방식을 이용하는 DP 문제이며, DP 배열에 자기 자신의 상태를 저장한다. 삼각형의 맨 위 꼭지점부터 아래로 내려올때 각 지점에서 최대값을 저장하며 마지막까지 내려간다. 마지막에 도달하면 그 중에서 최대값을 골라내면 된다. 그림에 나타낸것과 똑같이 1,2~N-1,N 의 세가지 경우에 대해 점화식을 세워서 해결하였다. N번째의 첫번째 원소의 경우, dp[n][0] = dp[n - 1][0] + 자기자신의 값 N번째의 2~N-1번째 원소의 경우, dp[n]..
www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수의 범위가 long long 범위를 초과하므로, string을 이용하여 풀어야합니다. 점화식 dp[i] = dp[i-1] + dp[i-2] string 덧셈 길이가 짧은 문자열 앞쪽에 '0'을 추가하여 두 문자열의 길이를 같게 만들어 준 뒤 덧셈연산을 수행하였고 10이상이면 carry를 하나 늘리고 다음자릿수 계산에서 carry가 있으면 1더해주도록 했습니다. ..
![]()
www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 동적 계획법을 통해 풀 수 있는 문제입니다. 하나의 스티커를 떼면, 맞닿아있는 3개의 스티커는 뗄 수 없게 됩니다. 이 조건을 지키면서 각 칸마다 얻을 수 있는 최대값을 구해봅시다. 1번 열은 그대로입니다. 2번 열의 10점 스티커가 얻을 수 있는 최대 점수는 10+30점, 2번 열의 50점 스티커가 얻을 수 있는 최대 점수는 50+50점입니다. 따라서 스티커를 선택했을 때 얻을 수 있는 최대 점수로..
![]()
www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 이 문제는 동적 계획법을 2차원 배열에 적용하여 풀 수 있습니다. 두 문자열을 각각 A와 B라고 할 때, 2차원 배열의 가로는 문자열 A, 세로는 문자열 B로 지정하고, 인덱스 마다 해당 지점까지 존재할 수 있는 가장 긴 부분 문자열의 길이를 저장하면 됩니다. 해당 지점 (X, Y). A문자열의 X까지, B문자열의 Y까지 등장할 수 있는 공통 부분 문자열의 길이는 A의 X - 1까지, B의 Y - 1..
