조용하지않는개발Blog

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 이 문제는 정해진 숫자를 차례대로 출력 될수있게 하면 되는 문제이다. 백트래킹과 dfs를 이용해서 풀면 쉽게 풀린다. 또한 그냥 itertools의 permutations을 통해 풀면 간단하게 풀수있다. # dfs와 백트래킹 import sys input= sys.stdin.readline def dfs(x,y): if m==y: print(*x) el..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 처음에 문제를 잘못 이해해서 고생했지만 위 4개를 이어붙인 모습으로 최대가 되는 값을 찾는 문제였다. 백트래킹을 활용하면 문제를 풀 수 있지만. 문제가 되는 부분인 ㅗ,ㅜ,ㅓ,ㅏ 이 모양을 어떻게 만드느냐가 중요한 사항이다. 처음에는 4가지를 코드로 구현해서 결과를 출력해보았다. import sys dx = [0,0,1,-1] dy = [1,-1,0,0] inp..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 보고 간단하게 푸는 방법으로는 조합을 출력되게하면 끝이 나겠구나? 생각이 들었다. 파이썬에는 itertools의 combinations 가 존재하기에 이것을 이용하면 엄청 쉽게 풀 수 있다. import sys from itertools import combinations input= sys.stdin.readline n,m = map(int,input..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 보고 0인 위치에 숫자를 대입하는 형식으로 풀면 되겠다 라는 생각이 들었다. 숫자를 넣기전에 넣어도 되는 위치인지 아닌지만 확인하면 끝이 나지 않을까 생각하였다. 백트래킹, bfs로 풀면 문제는 어렵지 않게 풀린다. import sys input = sys.stdin.readline graph = [list(map(int,input().split())) ..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 통해서 그래프 문제라는 것을 알수있었다. 또한 bfs,dfs를 통해서 전진하며 카운트를 하는 문제이고, 다시 돌아오는 경우(백트레킹)를 대비하며 풀어야하는 문제이다. 이때 추가적으로 같은 알파벳이 나오는 경우 패스하면 되는 문제이다. 뭔가 접근할때 dfs를 풀면 쉽게 풀리겠다 싶어서 풀었는데 시간 초과가 계속 났다. pypy3로 넘어가니 조금 되는..