https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 아이디어 1. 두 가지로 나눠 생각하면 테트로미노 도형 만들기 종이 위에 올리기 2. 도형 만들기 도형이 회전이나 대칭도 가능하니 dfs를 사용하면 T도형 빼고 전부 다 만들 수 있다. dfs 탐색 깊이를 4까지 설정하면 도형을 확인할 수 있다. T 모양은 따로 함수를 만들어 처리했다. 3. 종이에 도형 놓기 시간제한이나 N, M 크기를 보고 브루트 포스를 사용하기로 결정했다. 각 위치마다 만들어..

https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 아이디어 1. 브루트 포스 문제에서 높이 이가 256까지 그리고 N, M이 500까지가 최대다. 256*500*500 = 64000000이므로 1초 안에 가능하다 생각.. 2. 시간 초과 브루트 포스로 가능하다 생각했는데 계속 시간 초과가 걸렸다. 다른 사람들이 짠 코드를 확인해 보니 elif가 아닌 else를 사용했다. pypy로 통과했다. else와 elif가 시간 차이가 많이 난다는 것을 ..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 아이디어 1. 알고리즘 선택 처음 문제를 보고 DP로 풀어야 하나 생각하면서 도저히 모르겠어서 알고리즘 분류를 보니까 그냥 브루트 포스 문제다. 2. 구현 먼저 현재 채널(100)에서 최소값이 나올 수 있는지 확인 이후 0부터 1000000까지 버튼으로 만들 수 있는 채널인지 확인 그 채널 숫자를 만드는데 필요한 버튼 개수 확인 코드 설명 N = int(input()) M = in..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 아이디어 1. 파이썬 이슈 처음에 dfs로 접근했는데 Python3로 채점하면 80% 에서 시간 초과가 발생했다. (pypy로는 통과) 포기하고 bfs로 접근했는데 또 시간 초과가 발생해서 조건을 몇 개 추가하니 통과됨. c++ 였으면 dfs로 통과했을 거 같다. 2. 구현 파트는 크게 두 개로 나눴다. 국경선 열기 인구수 분배 코드 설명 기본적으로 이중 for문을 사용해서 각 위치..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제를 보다가 최근에 공부한 플로이드 워샬로 풀 수 있을 거 같아 사용했더니 통과됐다. 풀이 과정 for _ in range(M): a,b = map(int,sys.stdin.readline().rstrip().split()) graph[a][b] = 1 graph[b][a] = 1 for i in range(1, N + 1): for j in ra..

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 미로 찾기랑 비슷하다. 저번에 탐색 문제 풀 때 bfs로 시간 초과가 뜬 경험을 삼아 dfs로 풀었는데 해결이 안 됐다. 생각해보다가 bfs로 풀었는데 바로 답이 나왔다. 내 생각에는 bfs니까 자연스럽게 최단거리가 나오니까(depth 별로 탐색) 이런 문제는 bfs로 푸는 게 좋은 거 같다. 풀이 과정 dx = [2,2,1,1,-1,-1,-2,-2] dy = [1,-1,2,-2,2,-2,1,-1]..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-와샬 알고리즘을 쓰는 문제. 모든 노드 쌍의 최단 거리를 구할 수 있다. 시간 복잡도는 O(N^3) 풀이과정 cost = [[INF for _ in range(N + 1)] for _ in range(N + 1)] for i in range(1, N + 1): for j in range(1, N + 1): if i == j: cost[i][j] = 0 for i in range(m): a..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이썬이라 억까당함. 난이도는 낮지만 시간 초과로 고생했다. 맨 처음 bfs로 풀었을때 시간 초과가 채점 70%에서 자꾸 걸리길래 방법이 틀린 줄 알았다. 아마 파이썬이 아니였으면 맞았을 거 같다. from collections import deque import sys count = 0 N = int(input()) home = [] for _ in range(N): h..