맛대의 블로그

https://www.acmicpc.net/problem/13913로직bfs 활용방문 체크를 dict를 활용하여 경로 추적까지 처리방문 체크(record)를 dictionary로 생성key값이 있으면 방문했던 지점, value는 해당 지점을 어디서 왔는지1 -> 2 -> 4로 이동했다고 가정{1:-1, 2:1, 4:2}로 기록됨, -1은 시작점을 체크하기 위한 것코드from collections import dequedef path(S:int, dictionary:dict)->str: path_list = [] point = S while point != -1: path_list.append(str(point)) point = dictionary[point] ..

https://www.acmicpc.net/problem/2469로직구현문제모르는 줄(?????)을 기준으로 그 위에선 어떻게 진행되는지, 그 아레에선 어떻게 진행되는지 계산(check함수)사다리의 정보를 기준으로 이동을 기록예를들어 [A,B,C,D] 로 출발하여 [B,A,C,D] 로 완성될 경우 [1,0,2,3] 으로 기록됨[1,0,2,3]의 경우 0번 인덱스가 1번으로, 1번 인덱스 0번으로, 2,3번은 그대로를 의미이렇게 위 아래를 계산 후 col이 0번부터 현재 사다리에 가로막대가 없을 경우 값을 계산계산된 값이 결과와 다르면 사다리가 있어야함을 의미이 때 사다리가 있을 경우 +1번과 자리가 변경됨전에 이동이 필요해서 -를 두었는데, 또 이동이 필요한 경우 해당 문제에선 불가능한 경우의 수def ..

https://www.acmicpc.net/problem/1495로직dp 활용i번째 곡을 연주해야 할 떄 가능한 볼룸을 기록중복 제거를 위해 set 자료구조 활용i번쨰 곡을 연주할 때 가능한 볼룸들을 기록def solution(N:int,S:int,M:int,volume:list[int])->int: volume = [0]+volume dp = [set() for _ in range(N+1)] dp[0].add(S) for i in range(1,N+1): for v in dp[i-1]: if v+volume[i]=0: dp[i].add(v-volume[i]) if dp[N]: return max(dp[N]..

https://www.acmicpc.net/problem/2602로직dp 문제, 조금 복잡다리의 왼쪽부터 오른쪽으로 순회다리의 종류(천사,악마) 별로 적혀진 알파벳이 다름다리에 적혀진 알파벳이, 만들어야 하는 문자열에 어디에 쓰이는지 확인예를 들어 "RIRNRGRS" 라는 문자열에서 R은 [0,2,4,6]에서 사용됨다리에 적힌 알파벳이 R이라면 0번, 2번, 4번, 6번에서 사용 될 수 있음2,4,6번의 경우 조건이 완성된 경우에 사용이 가능2번을 예시로 들면 그 전에 R과 I가 완성 되어 있는 경우 사용 가능다리를 idx번 지났을때, 문자열의 완성 정도를 기록다리4칸을 건넜을 때, 문자열이 1번까지 완성되는 경우의 수 3개, 2번까지 완성된 경우의 수 1개 ....예시예제 1번 문자열:RGS, 악마: ..

https://www.acmicpc.net/problem/1099로직dp 문제단어 경우의 수?글자의 순서를 바꿔서 만들 수 있는 경우의 수는 L! (글자의 길이:L)'abc'를 바꿔서 만드는 경우의 수는 3! = 6, [abc,abc,bac,bca,cab,cba]단어의 경우의 수를 구할경우 최대 50개의 단어 * 단어의 길이!(50!)즉 단어의 경우의 수를 구하는 것은 연산이 너무 많음문장 경우의 수그렇기에 문장을 분해해서 이를 만들수 있는 단어가 있는지 확인하는 것이 무난문장을 slicing 해서 앞, 뒤 문장을 만들 수 있는지 확인'abcd'라는 문장을 'a'+'bc', 'ab'+'c' 등으로 분해분해한 문장이 만들수 있는지 확인분해된 문장을 만들수 있는지는 해당 문장을 정렬하고, 이를 주어진 단어들..

https://www.acmicpc.net/problem/1756로직구현문제화덕의 깊이, 피자의 크기는 30만피자가 들어올 때 마다 화덕을 탐색시 최대 30만 * 30만 = 900억번의 연산화덕의 구조가 밑이 아무리 넓어도 위가 좁으면 그 크기를 이용 불가(특징 a)그렇기에 현재 위치에 들어갈 수 있는 크기는 시작부터 현재까지의 최소값한번 위에서 피자를 집어 넣게되면 밑은 사용이 불가능한 구조(특징 b)피자를 넣은 후 그 밑에 있는 값들은 필요 없음최소값의 변화를 기록하는 list 생성(변수명 minList)해당 최소값을 몇칸 사용 가능한지 기록(변수명 cnt)피자를 순회 돌며 지름과 minList의 마지막 값과 비교마지막 값은 그 전값보다 항상 작음(특징 a)마지막 값보다 피자가 작으면 해당 층을 사용..

https://www.acmicpc.net/problem/14719로직처음에는 그리디하게 생각해서 기존 높이를 기록해서 계산 하는 방식으로 구현하려고 했으나, 고려해야 할 점이 많다고 생각됨가로 세로가 500 * 500이면 그냥 2중 배열로 지도를 그려도 문제가 없다는 생각이 들어 시도전체 지도에 블록이 해당 위치에 있으면 1, 없으면 0을 기록row와 col의 2중 반복문을 순회현재 높이에서 왼쪽, 오른쪽에 블록이 있다면 그 사이 공간만큼은 빗물이 차게됨을 이용H,W = map(int,input().split())blocks = list(map(int,input().split()))arr = [[0]*W for _ in range(H)]for c in range(W): block = blocks[..

https://www.acmicpc.net/problem/2174javascript(node.js)로 푼 문제를 python 코드로 변경하여 다시 풀어봄로직구현문제땅의 현 상태를 저장하기 위해 2중 리스트 생성(arr)각 로봇의 현재 좌표를 저장하기 위한 리스트(robotPosition)각 로봇의 현재 방향을 저장하기 위한 리스트(robotDirection)로봇의 명령왼쪽, 혹은 오른쪽으로 4번 돌게 되면 같은 방향을 보게 됨 => 명령 수를 4로 나머지 연산한 값만큼 수행회전을 구현하기 쉽게 하기 위해 { 'N':0, 'E':1,'S':2,'W':3 } 으로 저장 => 오른쪽 회전 시 1씩 증가, 왼쪽 회전시 1씩 감소왠 리팩토링?프론트엔드 코딩테스트에서 javascript를 이용하여 풀어야 할 경우가..

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/16118로직다익스트라 문제Python의 경우 다익스트라 구현 방식에 따라 시간초과가 발생하는 문제처음에는 graph[a][b] = c방식으로 하려 했으나, N이 너무 커서 문제가 됨두번 이상 사용되는 계산일 경우 한번만 계산후 할당하는 방식으로 처리 (next_length 등)늑대의 경우 소모 시간이 절반 | 2배되는 방식, 그렇기에 기본적으로 2배를 적용하여 절반으로 나눠도 소수점 계산이 안되게 처리늑대의 경우 1번나무로 돌아오는게 더 짧은 경우도 존재1번에서 2번까지 길이가 12번에서 3번까지 길이가 1001번에서 4번까지 길이가 14번에서 5번까지 길이가 15번에서 1번까지 길이가 1이렇게 주어질 경우, 3으로 가는 방법 중 가장 빠른 것은..