문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 처음에는 단순 DFS로 문제를 접근했다. 하지만 DFS를 사용하면 시간 초과가 발생한다. 이 문제는 DP를 사용해서 해결해야 한다. 점화식을 아래와 같이 세우면 된다. dp[i][j] = i번째 집을 j 색깔로 칠할 때 비용의 최솟값 dp[i][j] = Math.min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) // 이때 j와 같은 숫자는 제외..
문제 https://www.acmicpc.net/problem/1022 1022번: 소용돌이 예쁘게 출력하기 첫째 줄에 네 정수 r1, c1, r2, c2가 주어진다. www.acmicpc.net 풀이 모든 숫자를 계산해서 저장하는 것은 메모리의 한계로 가능하지 않다(10000*10000=1억 개의 int) 따라서 숫자는 계속해서 계산해나가면서, 범위에 있는 배열에만 값을 저장하면 된다. 이때 map[r2-r1+1][c2-c1+1] 을 선언해서 사용하면 된다. 자세한 내용은 코드를 참고하자. 코드 HTML 삽입 미리보기할 수 없는 소스
문제 https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 풀이 단순 구현 문제이다. 꼼꼼히 작성하는 게 중요하다! 나는 이 문제를 다음과 같이 해결했다. 먼저, 원판은 2차원 배열 circle [][]을 이용해서 표현했다. 이후 두 가지 함수를 작성했다. 1. 원판을 돌리는 함수 -> 시계, 반시계 방향을 기준으로 원판의 숫자를 돌린다. 인덱스 계산을 잘해야 한다. 2. 숫자를 지우는 함수 -> 모든 원소를 돌며 상하좌우를 탐색해 ..
문제 https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 풀이 이 문제는 단순 구현 문제이지만, 풀기 쉽지 않았다. 내 풀이는 다음과 같다. [그림 1]과 같이 temp 배열을 만들고, 사각형의 테두리를 기준으로 왼쪽 위부터 반시계방향으로 원소를 탐색하면서 R칸씩 밀어서 (범위를 벗어나면 나머지 연산) 저장해놓는다. 이후 다시 똑같은 순서로 탐색하면서 t..
문제 https://www.acmicpc.net/problem/1669 1669번: 멍멍이 쓰다듬기 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍 www.acmicpc.net 풀이 나는 수학 문제가 너무 어렵다. 이 문제는 수열 문제로 생각을 잘해야 풀 수 있다. 키차이 Day 1 Day 2 Day 3 Day 4 Day 5 1cm 1 2cm 1 1 3cm 1 1 1 4cm 1 2 1 5cm 1 2 1 1 6cm 1 2 2 1 7cm 1 2 2 1 1 8cm 1 2 2 2 1 9cm 1 2 3 2 1 키차이에 따른 키 크는 과정이다. 잘보면 4cm, 9cm 는 1,2,..
문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 처음에는 모든 벽에서 BFS를 돌려 모든 벽마다 갈 수 있는 곳을 세려고 했으나 이렇게 하면 시간초과가 난다 ㅠㅠ 그래서 다른 방법을 생각해냈다. 모든 0의 묶음을 개수로 표시하고, 해당 벽에서 4방향을 조사해서 다른 묶음이라면 0의 개수를 더해주기만 하면 된다. 예를 들어, 아래와 같은 상황이 있다고 하자. 010 1x2 110 -> xx2 (x는 벽, 숫자는 0..
문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 꽤 까다로운 DFS+백트래킹 문제였다. 숫자가 행, 열, 3*3 보드에 존재하는지 O(1)에 체크하기 위해 1. HashSet row[10] 2. HashSet col[10] 3. HashSet board[10] 이렇게 3개의 HashSet 배열을 만들었다. 즉, 보드의 (x,y) 좌표에 특정 숫자를 넣으려고 하면, row[x] 와 col[y]에 해당 숫자가 있는지 체크하면 된다...
문제 https://programmers.co.kr/learn/courses/30/lessons/60059?language=java 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 풀이 이 문제는 배열을 확장시켜서 풀면 쉽게 해결할 수 있다. 위와 같이 배열을 확장시켜서 차례대로 자물쇠와 키를 맞춰보면 된다. 이때 배열을 얼마나 확장시켜야 할까? 잘 보면 "자물쇠의 길이 + (키의 길이*2) - 2"만큼 확장시키면 된다는 것을 알 수 있다. 따라서 해결 과정은 다음과 같다. 1. "자물쇠의 길이 + (키의길이*2) - 2" 크기의 배열 map[][]을 만든다..
문제 https://programmers.co.kr/learn/courses/30/lessons/60058?language=java 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 풀이 간단한 구현 문제로 정말 문제에서 시키는 대로 함수를 작성하면 끝이다. 자세한 내용은 코드를 참고하자. 코드 import java.util.*; class Solution { public String solution(String p) { String answer = dfs(p); return answer; } public sta..
문제 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 풀이 이 문제는 간단한 구현 문제이다. 문자열을 압축할 zip 함수를 만들어 해결하였다. 1개씩 묶는 것부터 s의 길이까지 묶는 갯수를 늘려서 가장 짧은 길이로 압축 되는 것을 확인 하면 된다. 코드 import java.util.*; class Solution { public int solution(String s) { int answer = 1000000; for(int i=1; i 1){ ret += String.valueOf(cnt) + pr..