링크 : https://www.acmicpc.net/problem/2661 문제 : 아이디어 : N-Queen이랑 비슷해보인다 입력 길이만 주고 → 결과를 리턴 제한조건(동일한 숫자가 연속해서 나타나면 x ) 를 보고 → 백트래킹해서 가지치면서 진행해야겠다 까지생각했음 DFS를 써야겠다 BFS로 하면 안될거라고 생각했던게, 애초에 백트래킹할때 DFS로밖에 못한것도있고, 메모리제한이 128메가라서 1, 2, 3 순서대로 재귀 진행하면, 길이가 n 인상태에서 리턴되는 제일빠른 숫자가 정답 이라고 생각했다 망한코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) N = int(input().strip()) words = ['1', '2',..

링크 : https://www.acmicpc.net/problem/2661 문제 아이디어 : N-Queen이랑 비슷해보인다 입력 길이만 주고 → 결과를 리턴 제한조건(동일한 숫자가 연속해서 나타나면 x ) 를 보고 → 백트래킹해서 가지치면서 진행해야겠다 까지생각했음 DFS를 써야겠다 BFS로 하면 안될거라고 생각했던게, 애초에 백트래킹할때 DFS로밖에 못한것도있고, 메모리제한이 128메가라서 1, 2, 3 순서대로 재귀 진행하면, 길이가 n 인상태에서 리턴되는 제일빠른 숫자가 정답 이라고 생각했다 망한코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) N = int(input().strip()) words = ['1', '2', '..

링크 : https://www.acmicpc.net/problem/2661 문제 : 아이디어 : N-Queen이랑 비슷해보인다 입력 길이만 주고 → 결과를 리턴 제한조건(동일한 숫자가 연속해서 나타나면 x ) 를 보고 → 백트래킹해서 가지치면서 진행해야겠다 까지생각했음 DFS를 써야겠다 BFS로 하면 안될거라고 생각했던게, 애초에 백트래킹할때 DFS로밖에 못한것도있고, 메모리제한이 128메가라서 1, 2, 3 순서대로 재귀 진행하면, 길이가 n 인상태에서 리턴되는 제일빠른 숫자가 정답 이라고 생각했다 망한코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) N = int(input().strip()) words = ['1', '2',..

링크 : https://www.acmicpc.net/problem/10826 문제 그냥 간단한 DP다 n은 10000까지 주어지는데, 일반적인 방법으로 피보나치수를 구하게 되면 F(10000) = F(9999) + F(9998) = F(9998) + F(9997) + F(9997) + F(9996) = … 이런식으로 쭉쭉쭉 늘어가면서 결국 메모리제한256MB를 넘길것이다. 그래서 우린 DP를 해야한다 dp[2] = dp[1] + dp[0] 코드 import sys input =sys.stdin.readline n= int(input().strip()) dp = [ 0 for _ in range(n+1)] dp[0] = 0 if n < 2 : print(n) else : dp[1] = 1 for i in ..

문제링크 : https://leetcode.com/problems/trapping-rain-water/ 비슷하지만 비교적 쉬운 백준 링크 : https://www.acmicpc.net/problem/14719 문제 빗물이 고이는 원리 빗물이 고이려면 현재위치의 높이를 기준으로 왼쪽과 오른쪽이 ‘현재 높이보다 높아야’ 한다 이때, 쌓이는 양은 min(왼쪽, 오른쪽) - 현재 위치의 높이 가 된다 height 전체를 확인하지않고, 결과를 확인할수 있는 방법이 있을까? 결론은 안될것같다. 빗물의 양을 구하는 곳에서는 총 3곳의 블록값을 보는데 ‘내 위치, 왼쪽, 오른쪽' 이 되는데 주어지는 height 블록의 리스트 값이 모두 다르기 때문에 각 좌표의 블록값에 맞추어서 찾는것이 맞는것같다 백준에선 뚫리고, 리..

문제 : https://www.acmicpc.net/problem/2606 그냥 그래프 연결해서 순회하면 되는문제 진짜 딱 그게 전부다. 인접리스트, 인접행렬 문제에서 신경쓰이는 조건이 있었는데, 메모리제한이 128이다 인접리스트 방식은 ‘연결된 지점'만을 가지고 있고, 인접행렬은 [0,0,0,1,1] 이런식으로 모든 지점에 대한 연결여부를 가지고있는데 주어지는 컴퓨터의 수가 100개니까, 이를 인접행렬 방식으로 구현하게되면 100*100 matrix에 접근해야되는거니까 하면 안되나? 싶었다 근데 생각해보니까, 굳이 인접리스트나 인접행렬 상관없이 해도 겨우 10000칸이고, 한칸에 4바이트 잡아도 4만이다. 굳이 메모리 터지는건 신경안써도 될것같다 소스코드(전체) node = int(input()) ed..

문제 링크 : https://www.acmicpc.net/problem/14888 문제 모든 경우의 수를 구하지않고 하는 방법이 있을까? 이 문제에서는 ‘숫자는 고정' 된 상태에서 ‘연산자 순서를 변경' 해서 최대,최소값을 확인하는것이다 과연 이 문제에서 모든 경우의 수를 구하지않고 하는 방법이 있을까? 쉽지않을것같아서 완탐, BFS, DFS계열로 눈을 돌렸다 굳이 BFS, DFS로 돌려야하나 ? 가만 생각해보니 무조건 모든 연산자를 다 돌려야하는데, 굳이 BFS,DFS로 돌려야 싶었다. BFS나 DFS는 ‘특정 조건이 충족되면 진행' 하는거에 특화되어있는거지, 모든 연산을 확인해야하는 경우에 굳이 써야하는 이유를 모르겠어서 안썻다 완탐 완전탐색. 모든 경우의 수에 하나씩 대입해보면서 결과를 확인한다 연..

링크 https://www.acmicpc.net/problem/11725 문제 DFS DFS의 정의는 깊이우선탐색이며, ‘한 점을 기준으로 파고파고들다가, 끝점에서 다시 복귀하는 과정' 을 거친다는것이 특징이다. BFS에서는 deque()를 써서 구현하지만, DFS에서는 단순 재귀만으로 구현할수 있다. sys.setrecursionlimit(10**7) 재귀방식을 사용하는 DFS의 특성은 Python에서 무한재귀로 빠질 위험이 있다. 따라서 무한재귀를 막기위해, sys.setrecursionlimit(10**7) 를 해주는 것이 일반적이다. DFS(코드) def dfs(v,graph,visit): # print(v) visit[v] = True for i in graph[v] : if visit[i] =..

문제 https://www.acmicpc.net/problem/1260 코드(전체) N, M, start = map(int,input().split()) graph = [ [] * i for i in range(N+1) ] for i in range(M) : v1, v2 = map(int, input().split()) graph[v1].append(v2) graph[v2].append(v1) graph = [sorted(x) for x in graph] #print(graph) #DFS def dfs(graph,v, visited) : visited[v] = True print(v, end=' ') for i in graph[v] : if not visited[i] : dfs(graph,i,visite..

링크 : https://programmers.co.kr/learn/courses/30/lessons/72411 문제 문자열의 부분문자열 부분문자열(substring)이란 쉽게말해서 문자열을 구성하고 있는 문자열이다. 예를들어 ‘abcd’의 경우, 길이가 1인 문자열 [ a, b, c, d ], 길이가 2인 문자열 [ ab, bc, cd ] 길이가 3인 문자열 [ abc, bcd ], 길이가 4인 문자열 [ abcd ] 조합을 사용한 문자열 문제를 잘 읽어보면 ‘부분문자열의 순서' 는 중요하지않다고 말한다. 만약 ab, ba가 있다면 이 두개는 사실 같은문자열으로 취급해줘야한다. 이때 사용하는 라이브러리가 from itertools import combinations 이다. 소스코드(해설) for cour..