조용하지않는개발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/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 단순하게 생각하여 푼다면 x1,y1 부터 x2,y2 까지의 위치의 값을 합하여 답을 출력할 수 있을 것이다. import sys input = sys.stdin.readline n,m = map(int,input().split()) graph = [[0]*(n+1)]+[[0]+list(map(int,input().spl..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 이전에 풀었던 숨바꼭질 1,2 문제들 과 유사하게 풀면 되는데 그중에 2*x의 경우에는 시간을 증가하지 않게 하면 쉽게 풀리는 문제이다. from collections import deque def bfs(v): count = 0 q = deque([[v, count]]) while q: v = q.popleft() e = v[..

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 후위 표기식을 생각하면서 조건을 어떻게 짜야하는지 고민하며 문제를 풀면 쉽게 풀 수 있다. 1. 알파벳과 표기식이 나오는 경우를 나눈다. - 알파벳이 나오는 경우 결과 리스트에 추가한다. - 표기식이 나오는 경우 아래에 조건을 따른다. 2. 표기식이 나온경우 조건식 - 시작하는 괄호가 나오는 경우 : 스택에 쌓아준다. - "+"나"-" 가 나오는 경우 : 스..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 이전에 풀었던 백준 1167번 문제와 유사한 문제이다. 그것보다는 쉬운문제이니 유사하게 접근하면 쉽게 풀 수 있다. 먼저 그래프를 생성한 후 아무 위치를 하나 잡고(여기서 저는 1번을 기준으로 잡았습니다.) 최대로 먼 곳을 찾는다. 이후 먼 곳에서 부터 다시 최대로 먼곳을 찾으면 최대의 길이가 나온다. 이때 최대의 길이가 트리의 지름, 즉 답..

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/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 1개 샀을때 부터 n개를 살때까지 최소가 되는 값을 찾기위해서는 dp 형식으로 최소값을 찾는 것이 효율적이다. 예시 4번을 예로 들어서 풀어보면 10 5 10 11 12 13 30 35 40 45 47 맨 처음 1개를 살때 최소로 사는 방법은 5 하나밖에 없다. dp에는 1번째에는 5가 쌓일것이고 다음 2개를 살때 최소를 구해보면 10원으로 2개를 사거나 최소인 1..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 요즘 다익스트라 문제를 많이 푸는것같은데 리스트에 거리가 있는 경우는 거의 다익스트라 알고리즘으로 풀면 되는 문제인듯하다. 최단 시간에 오는 문제로 모든 학생들의 정해진 위치까지의 최단 거리와 다시 돌아가는 거리를 더해서 가장 오래걸리는 학생의 소요시간을 출력하면 되는 문제이다. import sys import heapq INF =..