문제 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..

# 데이터 인풋 import sys input = sys.stdin.readline n, m = map(int, input().split()) arr = [] for i in range(n): arr.append(list(map(int, input().split()))) # 각 셀을 기준으로 누적합 dp = [[0] * (n + 1) for i in range(n + 1)] for i in range(1, n + 1): for j in range(1, n + 1): dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + arr[i - 1][j - 1] # 범위 지정하여 구하기 for k in range(m): x1, y1, x2, y2 = map(int..

문제링크 : https://www.acmicpc.net/problem/2109 문제 작성자의 지능이슈(국어) 문제를 읽고, ‘날짜를 Key, 값을 Value로 구성하는 Key-Value를 구성해서 하나씩만 하면 되겠다' 라는 마음에 작성한 소스코드를 먼저 첨부한다 # kv_dict = {1: [20, 2], 3: [10], 2: [100, 8], 20: [5], 10: [50]} import sys input = sys.stdin.readline n = int(input().strip()) kv_dict = dict() for _ in range(n) : v, k = map(int, input().split()) if k in kv_dict.keys() : kv_dict[k].append(v) else ..

문제링크 https://www.acmicpc.net/problem/13913 그래프로 풀면 어떨까? 어떻게 해야하나 싶었는데 BFS, DFS로 접근하면 되지않을까? 에 대한 고민을 했고 다행히 완탐처럼 그래프 돌려서 풀었는데 성공했다 빠르게 연산된경우가, 늦게 연산된 경우보다 무조건 길이가 짧을까? 생각하는게 두가지가 있는데 단순 +1 -1만 사용해서 증감한 경우와 *2 +1 -1 모두를 사용해서 증감을 한경우 중에 특정한 숫자는 무조건적으로 연산횟수가 빠른게 먼저나올까? 에 대한 고민이었다 정답은 옳다. 나는 BFS로 풀었는데, 이때 특정값을 기준으로 +1 -1 *2 값에 접근하는거고 빨리 나온 숫자는 연산횟수가 짧아서, 길이가 짧다. 방문처리를 따로 확인하는 변수가 있어야한다. 경로를 저장해야한다 문..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/92344 무지성으로 풀면 무조건 시간초과난다 이 문제는 정확성과 효율성이 따로 구분되어있다. 무조건 모든 방식에서 생각해봐야한다는거다 시간초과 코드는 하단에 첨부한다 사전지식 : 누적합 보통 구간의 합계를 sum(리스트시작:리스트끝) 이걸로 구하는데 이게 리스트길이만큼의 시간복잡도가 사용된다. 그러면 합산 한번당 O(n)이 걸리는데 당연히 연산 횟수가 많아지면 많아질수록 비례해서 길어질것이다 그런데 누적합을 사용한 방식은 누적합계를 더한다음에 리스트끝원소-리스트시작원소 를 지정해서 계산하는데 리스트인덱싱1개는 O(1)이거든요. 그래서 누적합은 O(1)+O(1) 시간에 구간의 합계를 구할수 있어서 사용한다..

문제링크 https://programmers.co.kr/learn/courses/30/lessons/60057 문자열의 크기는 어떻게 될까? 테케2번 : ababcdcdababcdcd ⇒ 절반인 8개로 압축되면 2ababcdcd → N//2까지 압축 가능함 ⇒ 압축 범위는 1~N//2 압축이 진행되는 범위는 어디일까? 문자열 전역에서 압축이 일어날수 있음 ⇒ 문자열을 훑어야 하는 범위는 N 압축단위가 클수록, 압축문자열의 길이가 길까? 압축길이를 탐색할때 1→ (N//2) 방향으로 하나씩 늘려서 찾는방법과 (N//2) → 1 방향으로 하나씩 줄여서 찾는 방법이 있다. N//2 → 1 방향으로 탐색할때 큰 단위로 압축된 문자열의 압축문자열이 길까? 에 대해서 생각해봤는데 내생각은 ‘아니다’. 2개 단위로 ..

링크 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=584 #testcase # N,M= 3, 3 # X = [[50, 50], [40, 40], [10, 30]] # Y = [[60, 76], [18, 28], [22, 50]] import sys input = sys.stdin.readline N,M = map(int,input().split()) X = [] Y = [] for _ in range(N) : x1, x2 = map(int,input().split()) X.append([x1,x2]) for _ in range(M) : y1, y2 = map(int, input().split()) Y.append([y1,y2]) x_rang..

문제링크 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=623 #testcase # M, N, K = 3, 10, 5 # temp = str(145) # finds = str(3312414514) import sys input = sys.stdin.readline M,N,K = map(int,input().split()) temp = input().strip().replace(' ','') finds = input().strip().replace(' ','') finds = finds.split(temp) if len(finds) >= 2 : print("secret") else : print("normal") finds = finds.spl..

for i in range(1, 11) : N = int(input().strip()) blocks = list(map(int,input().split())) #blocks = [0,0,3,5,2,4,9,0,6,4,0,6,0,0] chomang = 0 for idx in range(2, len(blocks)-2) : left = idx - 2 right = idx + 3 left_side = max(blocks[left:idx]) right_side = max(blocks[idx+1:right]) #우리집이 제일 큰경우 if blocks[idx] > max(left_side, right_side) : chomang += blocks[idx] - max(left_side, right_side) print(..