시작하는 중

https://www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 단순하게 탐색하면 시간초과가 난다. 파이썬이 1초에 약 1억번이라고 생각하면 된다고 알고 있었는데 아마 형변환하고 문자열 뒤에 붙이는 과정이 더 오래걸리는 것 같다. 앞으로 참고하면 좋을 듯 싶다. 그래서 최적화를 할까 뭐를 할까 고민했었는데 생각해보니깐 자릿수마다의 경우의 수는 정해져있다. k에 해당하는 자연수의 자리수 특정하기 1의 자리 수 N이 1 -> 9로 증가하는 동안 N이 1 증가할 때마다 k가 가르키는 자리수도 바로..

https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 탐색 문제 탐색하다가 터질 폭탄만 스택에 넣고 터지는 연산을 한번에 해주면 된다. 바로 갱신 해버리면 값이 갱신되서 터질 폭탄도 다른 폭탄에 의해 없는 폭탄 취급해버리기 때문이다. 1. 모든 초마다 전부 탐색하면서 0이면 심어주고 1,2면 1씩 증가, 3이면 터뜨릴 스택에 넣어주고 2. 터뜨릴 스택이 존재한다면 전부 터뜨려주기 처음 1초는 아무것도 안한다고 했어서 처음에 2 상태로 시작하고 탐색도 2초가 되는 차례..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제를 이해하는데 시간이 걸렸는데 A,B,C,D,E가 아무 숫자나 와도 되고 A-B-C-D-E의 친구관계를 가지는 것이 문제 조건이다. 결국 그래프탐색에 있어서 5개의 노드를 거치면 1을 출력하면 되는 것이다. 7에서 시작하면 최대 깊이는 4 (7-3-4-0)이지만 2에서 시작하면 5(2-7-3-4-0)이다. 그냥 visited 배열을 활용한 backtracking으로 했는데 1.2초 걸려서 통과했다. import sys def input(): return sys.stdin.readline().rstr..

https://www.acmicpc.net/problem/17472 [17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net](https://www.acmicpc.net/problem/17472) 풀이 1. 섬을 구분하기 2. 섬과 섬 사이의 거리에 따른 다리건설 가능 여부 + 연결 가능여부를 확인 3. 탐색을 통해 가장 짧은 거리를 찾기 1. 섬 구분하기 섬의 입력은 0과 1로 이루어진 NxM형태이다. 여기에 STR 0으로 둘러싸줌 각 섬을 딕셔너리 형태로 넘버링한 것을 key로 넣고 섬의 in..