🌱1 Day, 1 Commit Wonseok's Record

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의 경우 세로, ..

https://programmers.co.kr/learn/courses/30/lessons/12953 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr 해설 : n개의 숫자가 주어질 때, 모든 숫자의 최소공배수를 구하는 문제이다. 풀이 : 수들 중 가장 큰 수 a부터 모든 수를 곱한 값 l까지 1씩 더해가며 모든 수에 대해 나머지를 확인하며 최소공배수가 되는 값을 찾도록 구현하였다. 1234567891011def solution(arr): l = 1 for i in a..

https://programmers.co.kr/learn/courses/30/lessons/12948 코딩테스트 연습 - 핸드폰 번호 가리기 프로그래머스 모바일은 개인정보 보호를 위해 고지서를 보낼 때 고객들의 전화번호의 일부를 가립니다. 전화번호가 문자열 phone_number로 주어졌을 때, 전화번호의 뒷 4자리를 제외한 나머지 숫자 programmers.co.kr 해설 : 핸드폰 번호가 주어졌을 때 핸드폰 번호의 뒷 4자리를 제외한 나머지 숫자들을 모두 * 로 변환하여 출력하는 문제이다. 풀이 : Python의 list slicing을 이용하여 뒷 4자리를 제외한 나머지의 길이만큼 *를 만들어주고, 여기에 원래 뒷자리 4개를 붙여주었다 12def solution(phone_number): retur..

https://programmers.co.kr/learn/courses/30/lessons/12945 코딩테스트 연습 - 피보나치 수 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = programmers.co.kr 해설 : 2 이상의 n이 입력되었을 때, n 번째 피보나치 수를 1234567로 나눈 나머지를 출력하면 된다. 풀이 : DP의 가장 대표적인 문제이다. n-1과 n-2번째의 값을 더하여 n..

https://programmers.co.kr/learn/courses/30/lessons/12936 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 해설 : 1번부터 n번, 총 n명의 사람이 줄을 서는 모든 경우를 사전순으로 정렬한 후 k번째 줄 서는 방법을 찾는 문제이다. 풀이 : 처음엔 permutations을 이용하여 실제로 줄 서는 모든 방법을 찾으려고 하였으나 n의 범위가 20이므로 메모리, 시간 효율성에서 모두 통과하지 못했다. 따라서 다른 방법을 생각하였는데 이는 수학적 특징을 이..

https://programmers.co.kr/learn/courses/30/lessons/12929 코딩테스트 연습 - 올바른 괄호의 갯수 올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모 programmers.co.kr 해설 : 소괄호의 짝이 n개 주어질 때, 이 소괄호의 짝을 이용해서 만들 수 있는 모든 올바른 괄호열의 개수를 찾는 문제이다. 풀이 : 우선 괄호가 올바른 괄호열인지 체크하는 함수를 구현하고, 재귀를 이용해서 n개의 짝으로 만들 수 있는 모든 괄호 문자열에 대해 올바른 괄호열인지 체크하도록 했다. 123456789101112..