맛대의 블로그

https://www.acmicpc.net/problem/1456로직소수를 구하기만 하면 해결 가능한 문제루트 B 범위 까지의 소수를 구함해당 범위의 소수를 제곱해 나가며 범위에 해당하는 값을 확인import mathdef createPrimeNumberArr(maxValue:int): numbers = [False]*2+[True]*(maxValue-1) for num in range(2,maxValue): if numbers[num] == False: continue for multiple in range(2*num,maxValue+1,num): numbers[multiple] = False primeNums = list() for i in range(2,maxVa..

https://www.acmicpc.net/problem/4991 로직 bfs 활용 먼저 로봇청소기가 있는 지점에서 bfs를 통해 각 먼지까지의 거리를 구함 방문할 수 없는 더러운 곳이 있다면, 이 때 거리를 통해 알 수 있음 그 후 먼지 위치에서 bfs를 통해 각 먼지까지의 거리를 구함 이렇게 구한 로봇청소기,먼지 사이의 거리를 2중 배열 graph[r][c]형식으로 graph로 만들어 기록 로봇청소기 위치를 시작지점으로 브루트포스 방식으로 먼지들을 방문하며 합계 거리를 계산 (함수명 recur) 이 때 이미 최단 거리 보다 합계 거리가 멀어질 경우 백트레킹 from collections import deque import sys input = sys.stdin.readline def makeGraph..

https://www.acmicpc.net/problem/9421 로직 2부터 n까지의 소수를 구한다 primeNumList 함수(에라토스테네스의 체 활용) 소수가 상근수인지 확인 재귀 방식을 이용하여 확인 재귀 도중 같은 수가 여려번 나올 수 있으니 기존에 계산했던 경우 그 값을 활용(변수명 checkList) 무한 루프에 빠질 수 있으므로 재귀 전에 현재의 수를 상근수가 아니다로 표기 후 재귀 def primeNumList(n): check = [False,False]+[True]*(n-1) for num in range(2,(n+1)//2): if check[num]: for multiNum in range(2*num,n+1,num): check[multiNum] = False value = lis..

https://www.acmicpc.net/problem/9370 로직 다익스트라 알고리즘을 이용하여 최단거리를 구함 g -> h 혹은 h -> g로 이동할 때를 찾아야 함 시작점 -> g -> h -> 목적지 시작점 -> h -> g -> 목적지 시작점에서 목적지까지의 최단거리가 위의 방법과 거리가 같다면 g-h 도로를 이용하여 이동 할 수 있음을 알 수 있음 만약 같은 길이의 다른 경로가 존재 하더라도, g-h 도로를 이용하여 갈수도 있으므로 가능성이 있는 목적지 만약 더 짧은 길이의 다른 경로가 존재한다면, 시작점-목적지 까지의 최단거리가 위의 방법과 같을 수가 없음 그렇기에 시작점에서 g,h,목적지 까지의 최단거리 // g->h, g->목적지 까지의 최단 거리 // h->g,h->목적지 까지의 최..

https://www.acmicpc.net/problem/11780 로직 최단 거리는 플로이드 워셜 알고리즘 활용 모든 노드에 관하여 3중 반복문 활용(중간점, 시작점, 끝나는 점) 기존의 시작점-끝난점 거리보다 중간점에 들리는 경우가 더 짧은 경우 갱신하는 알고리즘 경로를 파악하기 위해 플로이드 워셜 알고리즘으로 갱신되는 경우 중간 지점을 기록 기록해둔 중간지점을 이용하여 병합하는 형식으로 루트를 파악 1번에서 10번 지점까지의 경로를 찾는다고 가정 1번에서 10번 가려는데 최단거리를 위해 중간에 거치는 경로가 5번이라고 하면 1 .... 5 ...... 10번 경로를 통해 최단 거리가 될 수 있음을 알 수 있음 이제 1에서 5번까지의 경로를 확인하고, 5번에서 10번까지의 경로를 확인 마찬가지로 1에..

로직 동전은 1원, 5원, 10원, 25원이 존재 비싼 동전부터 동전을 최소한으로 사용하는 방식 25원 동전이 d개 만큼은 가지고 있어야 나머지 동전의 합으로 X원을 만들 수 있음 25원 동전이 d개 일 때, 10원 동전은 c개 만큼은 가지고 있어야 나머지 동전의 합으로 X원을 만들 수 있음 위 사항을 반복 위 방식의 문제 위의 식은 비싼 동전을 최소한으로 사용하는 방정식 25원은 1,5,10원 짜리 동전과 다른 특성을 가지고 있음 5원, 10원의 경우 하위 동전의 배수로 만들 수 있지만, 25원은 102 + 51 과 같은 형식으로 하위 동전이 여러 종류가 필요할 수 있음 이로인해 30원을 만드는데 문제가 발생 10원짜리 3개를 이용하여 30원을 만들 수 있지만(5원,1원짜리를 합쳐도 10원이 되지 않는..

https://www.acmicpc.net/problem/25189 로직 방문 여부를 RC(NM)에 개구리밥 무시 여부를 추가하여 RC2로 구성 bfs : 각각의 지점에서 점프할수 있는 4곳을 확인 추가적으로 먹이를 무시하고 뛸 경우도 확인 이 때 먹이를 무시하고 뛰는 경우를 전부 확인할 경우 시간초과가 발생하게 됨 (한 지점에서 무시하고 뛰는 경우의 수가 (N+M), 모든 지점에서 계산시 최대 200010001000 이상의 계산 필요 하여 시간 초과 발생 이를 방지하기 위해 해당 row,Colum 에서 무시하고 뛴 적이 있는지를 확인 (1,1 에서 1,4 로 뛰나 1,2에서 1,4 로 뛰나 어차피 같은 결과 이므로 한번 이후로는 필요 없는 계산, 따라서 r == 1에서 뛴적이 있는지를 확인하는 추가 작..

https://www.acmicpc.net/problem/28103 로직 사람을 한명씩 가진돈과 비교하여 계산할 경우 N이 너무 커서 시간초과가 발생 가격의 경우 10**6으로 반복문을 돌려도 문제가 발생하지 않는 범위 일단 모두 제일 싼 값으로 구매한 후 남은 돈으로 계산 시작 (X -= default*N) 위 방법으로 계산하기 위해 물건의 가격을 제일 값싼 물건과의 가격차이로 변경 가장 비싼물건부터 여유있는 돈의 수만큼 구매, 이 때 현재 남아있는 사람 수(N)와 비교하여 낮은 값으로 계산 현재 가진돈이 물건 값 대비 매우 많을 경우 X//price 계산시 사람 수보다 많은 물건을 사게됨 가장 값싼 물건과의 가격차이로 list를 변경하여 prices[-1]은 0이 되어 X//price 시 zerodi..

https://www.acmicpc.net/problem/16958 주의 알고리즘 분류에 플로이드 워셜로 되어 있음 플로이드 워셜 알고리즘을 이용하여 계산시 전체 노드를 대상으로 할 경우 너무 많은 계산이 발생함 이 문제에서 각 node 사이의 거리는 다른 지점에 들려도 좁아지지 않는 그래프 따라서 텔레포트를 이용하지 않는 한 거리가 좁혀질수가 없음 로직 각 node의 row, colum을 기록 텔레포트가 가능한 node의 경우 따로 기록 저장된 row,colum을 이용하여 node끼리의 거리를 구하고 저장 각 node에서 텔레포트가 가능한 node 중 가장 가까운 곳까지의 거리를 기록 기존의 node1과 node2사이의 거리와 node1에서 텔레포트 지점 + node2에서 텔레포트 지점 중 가까운 값으..

https://www.acmicpc.net/problem/28075 로직 및 코드 해설 재귀 활용 total >= M 판단 일을 하는 도중 M값을 넘어가면 그 뒤로 어떤 일을 선택해도 조건을 충족 하루에 6가지 일을 선택 할 수 있으므로 6^(남은일수) 만큼의 경우만큼 충족 day == endDay일 때 M을 초과하면 return 1, 아니면 return 0을 하는 방법도 존재 해당 방법보다 재귀횟수와 같은 계산이 적게 든다고 판단하여 해당 방법 채택 task_idx 일의 경우 2*3의 배열 처음에는 idx를 0부터 5까지 range(6)를 돌린후 divmod를 이용하여 몫과 나머지를 이용하려고 하였음 0부터 5까지의 숫자를 계속 divmod를 나누는 것 보다 (0,0),(0,1) 형태로 미리 계산 해둔..