어디까지 갈 수 있을까?

문제링크 www.acmicpc.net/problem/1038 ※※답 보기 전에 알고가기※※ n이 1022이면 x가 9876543210이 돼서 n이 1023일 때부터는 감소하는 수가 없게 된다. 이 때 부터는 무조건 -1을 출력하면 된다 시간 복잡도를 최대한 줄였는데 왜 시간초과가 나는지 생각하고 있었는데 이거 때문이었다 [답코드] import sys input=sys.stdin.readline n=int(input()) arr=[i for i in range(10)] i=1 while True: if i>1022: break back=arr[i]%10 for j in range(back): arr.append(arr[i]*10+j) i+=1 arr.sort() # print(arr) if n>len(ar..

문제링크 www.acmicpc.net/problem/3190 사과를 먹으면 몸이 길어지는 뱀이 몇 초부터 이동을 못하게 되는지 구하는 문제이다 [답코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 import sys input=sys.stdin.readline n=int(input()) #보드의 크기 board=[[-1]*n..

문제링크 programmers.co.kr/learn/courses/30/lessons/60057 카카오 문제는 예제외에 다른 테스트케이스들도 많이 생각하고 돌려야하는 것 같다 [답코드] 시도 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 def solution(s): #시뮬레이션 문제? answer = len(s) if len(s)==1: return 1 #반복 문자열 갯수 for i in range(1, (len(s) // 2)+1): simul_answer=0 #인덱스 re=0 #반복 횟수 for j in range(0, len(s)-i, i): if s[j:j+i]==s[j+i:j+2*i]:..

문제링크 programmers.co.kr/learn/courses/30/lessons/42891 [답코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import heapq def solution(food_times, k): q=[] #(시간, 인덱스) for i in range(len(food_times)): heapq.heappush(q, (food_times[i], i+1)) pre_food=0 now_food=q[0][0] n=len(food_times) while True: #바퀴수당으로 생각하기 if k - (now_food - pre_food) *n

문제링크 www.acmicpc.net/problem/10775 고통의 시간을 거치고 드디어 맞았다!! 🎉👏🎉👏 [답코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import sys input=sys.stdin.readline sys.setrecursionlimit(10**6) # 최대 재귀 깊이 제한 늘림 # 특정 원소가 속한 집합을 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent..

2. 플로이드 워셜 알고리즘 모든 노드 간 최단 거리를 구하는 알고리즘 출발노드에서 도착노드로 바로 가는 거리와 중간노드를 거쳐가는 거리 중 짧은 거리를 선택한다 2차원 배열을 생성해 중간노드를 갱신하는 횟수를 노드 갯수만큼 반복한다 시간복잡도는 O(N^3)이다 ① 테이블 초기화 ② 1번 노드를 거쳐 가는 경우 1번 노드와 관련된 노드, 출발노드와 도착노드가 같은 칸을 제외하고 확인해야한다. 1번 노드를 제외한 2번, 3번, 4번 노드에서 2개의 노드를 뽑는 경우를 고려해야 한다. 그러므로 고려해야할 칸은 모두 6 = 3P2 개다(주황색) D23=min(D23, D21+D13) D24=min(D24, D21+D14) D32=min(D32, D31+D12) D34=min(D34, D31+D14) D42=m..

알고리즘 문제를 접했을 때 '서로 다른 개체가 연결되어 있다' = '여러 개의 도시가 연결되어 있다'와 같은 내용이 나오면 그래프 알고리즘을 의심해보자 1. union-find(합집합 찾기, 서로소 집합) 차후 크루스칼 알고리즘과 위상 정렬에서 사이클이 발생했는지 판별할 때 사용한다 union-find 연산을 통해 최종 부모노드를 찾아가는 알고리즘이다 union(A, B)를 한다면 둘 중 부모노드의 값이 더 작은 노드로 합쳐진다 ① 그래프 생성 부모 노드 배열을 만들고 자기자신을 가리키는 것으로 초기화한다 union(4, 5) -> union(3, 4) -> union(2, 3) -> union(1, 2) 순으로 진행하기로 한다 ② union(4, 5) union(4, 5)가 진행되면 4와 5번 노드 중..

문제링크 www.acmicpc.net/problem/2224 [답코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (52) for _ in range(52)] for..