춤추는 개발자

문제 출처 https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 접근 방식 및 풀이 - DFS 재귀로 부르면서 M길이 만큼이면 return - 중복 사용 여부는 지금 사용하는 숫자가 list에 담겼는지 확인 소스 코드 N,M = map(int, input().split()) arr = list(map(int, input().split())) tmp_list = [] def dfs(start): # print(f'start : {start} ..

문제 출처 https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 접근 방식 및 풀이 - 정렬 로직은 sorted 함수 사용 - DFS 로 재귀로 부르면서 list에 담다가 길이가 M이면 return 소스 코드 N,M = map(int, input().split()) arr = list(map(int, input().split())) tmp_list = [] def dfs(): if len(tmp_list) == M: for i in rang..

문제 출처 https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 접근 방식 및 풀이 - DFS 재귀로 호출하고, 길이가 M 이면 return 조건 추가. 소스 코드 N, M = map(int, input().split()) tmp_list = [] def dfs(start): if len(tmp_list) == M: for i in range(M): print(tmp_list[i], end=' ') print('') return for i in r..

문제 출처 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 접근 방식 및 풀이 - DFS 재귀함수 호출하다가 M 길이만큼이면 출력 소스 코드 N, M = map(int, input().split()) tmp_list = [] def dfs(): if len(tmp_list) == M: for i in range(M): print(tmp_list[i], end=' ') print('') return for i in range(1,N+1): tm..

문제 출처 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 접근 방식 및 풀이 - DFS 재귀함수로 호출하면서 list에 담아두다가 M개 만큼 담기면 출력 - 중복체크 하기 위해서 list에 있는지 없는지 확인. 소스 코드 N,M=map(int, input().split()) tmp_list = [] def dfs(start): if len(tmp_list) == M: for i in range(M): print(tmp_list[i], end..

문제 출처 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 접근 방식 및 풀이 - DFS를 사용하여 재귀로 호출하다가 M이면 중단(가지치기)하기 소스 코드 N, M = map(int,input().split()) tmp_list =[0]*M def dfs(level): if level == M: for i in range(M): print(tmp_list[i], end=' ') print('') return for i in range(1,N+..

문제 출처 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 접근 방식 및 풀이 - 가장 가까운 물고기를 구하는 것은 BFS를 이용하여 최단거리 찾기 - 가장 가까운 물고기 찾은 위치에서 다음 물고기 찾아가자. - 짧게 구현하는 것보다 세부 조건들을 까먹지 말고 구현하면서 함수화 해보기 - 세부조건 : 나보다 큰 물고기는 지나갈 수 없다. 자신의 크기보다 작은 물고기만 먹는다. 소스 코드 import sys from collections ..

문제 출처 https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경 www.acmicpc.net 접근 방식 및 풀이 - BFS를 활용한다. - 명령어를 한번씩 실행하면서 결과값을 저장하고, 계속 돌다가 출력해야하는 값이 나..

문제 출처 https://www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 ( 3≤m, n≤1000). 세 번째 줄부터 차례로 m 개의 줄에는 피자 A의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 그 다음 n 개의 줄에는 차례로 피자B의 미리 잘라진 피자조각의 크기를 나타내는 정수가 주어진다. 각 종류의 피자조각의 크기 www.acmicpc.net 접근 방식 및 풀이 - A피자, B피자의 부분합의 배열을 구한다. - 두 부분합의 배열을 투포인트 알고리즘을 통해 목표값을 찾..

문제 출처 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 접근 방식 및 풀이 - 백트래킹 + DFS 문제 - N-Queen (백준 9663번)과 비슷한 문제 - 백트래킹 3가지 조건 :..