조용하지않는개발Blog

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 문제를 보았을 때 알 수 있는 힌트 왼쪽에서 오른쪽으로 가는 선을 겹치지 않고 오른쪽 방향으로 위, 가운데 아래로 움직이며 끝까지 가게 하였을때 최대로 갈수있는 개수를 찾는 문제이다. 처음 봤을때 dfs로 풀면 되겠다. 끝까지 가는 것을 확인하고 백트래킹을 하면 되겠다 생각을 했다. 하지만 그렇게 구현을 하면 너무 많은 반복을 하게 된다. R이 10000이고 C는 500이나 되기에 무조건 시간 초과가 난다...

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/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/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 처음 풀었을때 dfs, bfs로 접근하면 되겠구나 라는 생각은 들었다. 접근은 잘했지만 정점 1부터 n까지 반복하여 돌리면 시간 초과가 나온다. 이것을 통해 뭔가 다른 조건이 하나 더 있겠구나! 라는 생각이 들었다. 이 조건을 찾기 위해서는 https://blog.myungwoo.kr/112 이 블로그를 참고했다. 블로그에서는 임이의 정점..

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=411 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 문제를 보았을때 알수있는 힌트 단순 BFS,DFS 문제에 한가지 조건을 더해서 좀더 어렵게 만들었다. 하지만 문제에 힌트가 있다. 격자 화면의 맨 가장자리에는 얼음이 놓이지 않는 다고한다. 그렇다면 바깥 부분에서 1에 닿는 부분을 체크하며 지워나가면 답을 찾을수있는 문제이다. import sys from collections import deque input= sys.stdin.readline nx=[0,0,1,-1] ny=[1,-1,0,0] n,m = map(int,input().split()) grap..

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

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=409 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 자율주행팀 SW 엔지니어인 당신에게 장애물과 도로를 인식할 수 있는 프로그램을 만들라는 업무가 주어졌다. 우선 [그림 1]과 같이 정사각형 모양의 지도가 있다. 1은 장애물이 있는 곳을, 0은 도로가 있는 곳을 나타낸다. 당신은 이 지도를 가지고 연결된 장애물들의 모임인 블록을 정의하고, 불록에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 장애물이 좌우, 혹은 아래위로 붙어 있는 경우를 말한다. 대각선 상에 장애물이 있는 경우는 연결된 것이 아니다. [그림 2]는 [그림 1]을 블록 별로 번호를 붙..