🌱1 Day, 1 Commit Wonseok's Record

https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 해설 : 기타리스트 강토가 기타줄을 갈려고 한다. 갈아야 할 기타줄의 수 N과 가격을 찾아본 브랜드 M이 주어지고, 브랜드 별 패키지(기타줄 6개 묶음) 의 가격과 낱개의 가격이 주어진다. 이 때, 기타줄을 가는데 드는 최소 비용을 찾는 문제이다. 풀이 : 그리디 알고리즘을 사용하는 쉬운 문제이다. 낱개의 가격이 가장 싼 브랜드와, 묶음의 가격이 가장 싼 브랜드를 찾고 낱개 * (사야하는 기타..

https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 해설 : 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다..

https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 해설 : +---+ | D | +---+---+---+---+ | E | A | B | F | +---+---+---+---+ | C | +---+ 전개도가 다음과 같은 주사위의 A부터 F까지의 수가 주어지고 이를 N x N x N 개 쌓아서 정육면체를 만든다고 할 때, 바깥에 드러나는 5개의 면들에 있는 숫자들의 합의 최솟값을 찾는 문제이다. 풀이 : 수학에 많이 약한 내..

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 해설 : 음이 아닌 정수 X가 가장 큰 자릿수부터 가장 작은 자릿수까지 감소한다면 (숫자가 작아진다면) 이는 감소하는 수 이다. N이 주어질 때 0부터 시작하는 감소하는 수들 중 N번째 수를 출력하는 문제이다 (숫자는 1,000,000) 이하이다. 풀이 : 완전 탐색 문제이다. N번째 수인지 확인하는 cnt 변수를 두고, 이 cnt 변수가 N보다 작은동안 1부터 1,000,000까지..

https://www.acmicpc.net/problem/1026 해설 : 숫자가 담겨있는 A와 B 배열이 주어질 때 A[0] * B[0] + A[1] * B[1] + ...... + A[n-1] * B[n-1] 의 최솟값을 구하는 문제이다. 단, B정렬은 재배열할 수 없다는 조건이 있다. 풀이 : A배열과 B배열을 한 쪽은 오름차순, 한 쪽은 내림차순으로 정렬한 후 0번 인덱스부터 n-1번 인덱스까지 더해주면 되는 문제인데 B배열을 정렬할 수 없다는 조건이 있다. Python의 min과 max 함수를 이용하여 각 배열의 최솟값과 최댓값을 곱해준 뒤 답에 더해준다. 이후 배열에서 방금 사용한 값을 삭제해주는 식으로 구현하였다. 1 2 3 4 5 6 7 8 9 10 11 12 n = int(input())..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 해설 : 크기가 N인 큐에서 M개의 수를 뽑아내려고 한다. 뽑아내는 연산은 0번째 원소만 가능할 때, 큐를 왼쪽, 또는 오른쪽으로 한 칸씩 회전시키는 연산을 최소 몇 번 하여 뽑아내려는 값을 전부 뽑아낼 수 있는지 찾는 문제이다. 풀이 : 자료구조중 덱을 사용하여 구현하면 효율적으로 구현이 가능하다. 스택, 큐, 덱의 차이점은 아래 링크에 정리해 두었다. (스택, 큐, 덱이란? : https:..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 해설 : White와 Black으로 이루어진 N*M 사이즈의 체스판이 주어진다. 이 체스판을 8 x 8의 사이즈로 자르려고 할 때, W와 B가 번갈아가면서 나오는 체스판의 원래 패턴을 만들어주기 위해 최소 몇 개의 칸을 칠해야 하는지 찾는 문제이다. 풀이 : 8 x 8로 자를 수 있는 모든 경우에 대해 이중 for문으로 전부 탐색하며 W 또는 B로 색칠해야하는 개수를 카운트해준다. 이를 m..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해설 : 0과 1로 이루어진 2차원 배열이 주어진다. 유기농 배추를 재배하기 위해 1들의 군집(인접한 1들의 집합)마다 배추흰지렁이 한 마리를 방생한다고 할 때, 총 몇 마리가 필요한지 찾는 문제이다. : 풀이 : BFS 또는 DFS로 해결할 수 있는 문제이다. 나는 BFS로 해결하였다. for문으로 배열의 모든 원소를 탐색하며 1인 원소(배추)를 만날 때마다 인접한 모든 원소를, 탐색하고 카운트를 1 증가시..

https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 해설 : 백트래킹의 대표문제인 n-queen 문제이다. n*n 체스판에 n개의 퀸을 놓을 수 있는 방법의 수를 찾는 문제이다. 풀이 : 백트래킹은 pruning이 중요하다고 배웠다. 재귀로 모든 경우를 탐색하지만 더 탐색해도 의미가 없는 경우 (절대 답이 될 수 없는 경우) 에 대한 조건으로 재귀를 종료해주어야 한다. n-queen의 경우 세로, ..