문제   이 문제를 처음 봤을때는 쓸 수 있을 법한 알고리즘이 쉽게 생각나지는 않았다. 그나마 생각난게 스택 또는 큐를 활용하면 될려나 하는 생각만 들었다. 그래서 일단 주어진 예시대로 차근차근 계산해가면서 규칙을 찾아보았다.   이 예시를 기준으로 생각해보자 앞에 시작 부분은 막대기가 주어지지 않은채 () 레이저가 왔으므로 0 그다음에 ((( 이렇게 막대기가 3개가 오는 것을 알 수 있다. 그리고 그 후에 () 레이저가 와서 기존에 있던 3개의 막대기를 자른 다는 것을 알 수 있다. 그리고 또 레이저가 와서 현재 기준 3개인 막대기를 또 자른다 그러고 ) 가 와서 이 이후에는 막대기가 두개가 된다. 결론은 () 이렇게 오는 레이저 말고 ((( 이런식으로 여는 괄호만 올 때 =  막대기가 시작될 때 이므..

문제   이 문제를 보면 일단 엄청 큰 범위가 가장 중요하게 고려해줘야 하는 부분이다.  건널 수 있는 사람수의 최댓 값은 모든 stone이 200,000,000인 경우이므로 200,000,000 이 된다. 이렇게 범위가 굉장히 큰 경우에는 일단 "이분 탐색"을 먼저 떠올려 주는게 좋다. 이분탐색을 이 문제에 적용하게 된다면 target은 정답이 되는 건널 수 있는 사람 수 가 되어야 한다.  더 자세한 부분은 작성한 코드를 바탕으로 설명하자면  def solution(stones, k): left = 1 right = 200000000 while(left= k: break #못건너는 다리의 길이가 k보다 길다는건 현재 인원이 건널 수 있는 ..

문제  이 문제를 처음 봤을 때는 대체 어떤 알고리즘을 활용해서 풀어야할 지 감이 쉽게 잡히지 않았다. combination을 통해서 조합을 구해서 합의 최솟값을 구하는 방식으로 할까 했지만 문제를 보면 알다시피 범위가 굉장히 크기 때문에 시간초과가 발생할 확률이 높다. 그렇게 계속 고민하던 찰나에 어라..? 범위가 큰 상태에서 두수의 합을 구하는 거라면.... 투포인터 ??  하면서 불현듯 떠올랐다.  이 문제는 두개의 포인터를 배치해서 조건에 따라 포인터를 이동시켜가면서 답을 찾아주면 된다.  그리고 중요한 것은 투포인터 알고리즘을 적용하기전 하기전 꼭 오름차순 정렬을 해주는 것이다. (투포인터의 전제조건)  그래서 이 문제는 투포인터를 활용할 때 3가지 포인트를 생각해주면 된다.  1. 최솟값이 업..

문제   이 문제를 보면 일단 최단거리라는 단어가 나오기 때문에 BFS일 확률이 높다.  다만 이 문제는 육지에 해당되는 모든 지점에서 다른 지점까지의 최단거리의 값중 최댓값을 구해주는 것이므로 육지를 만날때마다 BFS함수를 실행해주는 형태로 해주면 된다.   정답 코드import sysfrom collections import dequeinput = sys.stdin.readline# 첫 번째 줄에서 n과 m을 읽음 (행의 수와 열의 수)n, m = map(int, input().split())# n개의 행을 지도 배열로 읽어들임arr = [list(input().strip()) for _ in range(n)]def bfs(a,b): ans = [[0]*m for _ in range(n)] ..

문제  이 문제를 딱 보는 드는 생각은 변형된 미로 문제 같다는 생각이다. 뱀과 사다리와 같은 요소가 추가되긴 했지만 본질은 미로에서 최단경로 찾기와 같다.  그렇기 때문에 BFS를 사용해서 문제를 풀어주었다.  이 문제의 까다로운 점은 뱀과 사다리 요소의 처리, 그리고 입력값이 2차원 배열에 맞게 주어지지 않는다는 것이다. 거기다가 0부터 시작이 아닌 1부터 시작이기때문에 이에 대한 처리도 해주어야한다. 이때 나는 입력값-1 한 것을 인덱스로 변환해주는 방법을 선택했다. 나중에 처리하게되면 값을 사용할 때마다 처리를 해주어야돼서 복잡해지기 때문에 입력값-1을 해준 후 10의 자리는 1의자리를 그대로 활용해서 인덱스로 써주었다.코드from collections import dequen, m = map(i..

문제   이 문제는 특이하게도 메모리제한이 굉장히 작다.항상 숫자의 범위만 확인했는데 덕분에 앞으로 메모리제한도 신경써야한다는 것을 깨닫게 되었다.  틀린코드n =int(input())nums = [list(map(int,input().split())) for _ in range(n)]dp_max = [[0]*3 for _ in range(n)]dp_max[0][0] = nums[0][0]dp_max[0][1] = nums[0][1]dp_max[0][2] = nums[0][2]dp_min = [[0]*3 for _ in range(n)]dp_min[0][0] = nums[0][0]dp_min[0][1] = nums[0][1]dp_min[0][2] = nums[0][2]for i in range(1,len..

문제  이 문제를 보면 dfs로 풀어야한다는 감이 온다 왜냐하면 삭제해야하는 노드의 끝까지 방문해서 차례대로 삭제를 해주어야 하기 때문이다. 이때 삭제를 실제로 하게 되면은 인덱스 번호를 수정해야 해서 복잡해지므로 삭제를 해야할 노드의 값을 변경해주는 방식으로 업데이트를 해주었다. 실제 코드from collections import dequen = int(input())nodes = list(map(int, input().split()))d = int(input())def dfs(d): nodes[d] = -10 for i in range(n): #d번 노드를 부모로 가진 자식노드 재귀통해 삭제 if d == nodes[i]: ..

문제 dfs/bfs 문제이기는 한데 평소에 풀던 방식과는 조금 다르게 풀어야해서 애를 먹었다.... 일단 이 문제의 관건은 numbers 배열을 돌면서 상위노드의 값에 아래의 노드값을 계산하는 방식으로 내려가 주어야 한다. 전체코드def solution(numbers, target): answer = 0 leaves = [0] for num in numbers: tmp =[] #leaves는 이전의 노드 for leaf in leaves: tmp.append(leaf-num) tmp.append(leaf+num) leaves = tmp a..

문제    이 문제를 처음 봤을 때는 솔직히 도대체 어떻게 풀어주어야할 지 감이 안잡혔다....a번 번호를 기준으로 오름차순 정렬은 해봤는데 그 이후로 진도가 안나가서 구글링을 해봤고 LIS알고리즘에 대해서 알게 되었다.  LIS알고리즘 관련 내용https://4legs-study.tistory.com/106 최장 증가 수열 (LIS, Longest Increasing Subsequence)최장 증가 수열 (LIS, Longest Increasing Subsequence) 최장 증가 수열, 정확히 최장 증가 부분 수열은 어떠한 수열에서 오름차순으로 증가하는 가장 긴 부분수열을 의미한다. 이 때, 부분 수열의 각 수는4legs-study.tistory.com     이 설명을 보면 뭔가 이해는 되는데 그래..

문제   이 문제는 구현하는 알고리즘을 생각하는게 까다롭다기보다는 조건이 너무 많아서 구현하는게 까다로운 문제이다. 일단 반시계방향 시계방향으로 돌게 하는 함수부터 따로 만들어주는 것으로 시작하였다. 이때 검색해보니 deque를 활용해서 roatate함수를 활용하신 분이 많던데 나는 이 방법을 몰라서 직접 구현했다... 내장함수 쓰는게 훨씬 간편할듯,,, 그리고 처음에 헷갈린 부분이 한번 회전을 할 때 하나의 톱니바퀴가 움직이면 한번의 회전 내에서 톱니바퀴를 바로 움직여서 옆의 톱니바퀴는 회전된 톱니바퀴를 기준으로 하도록 했는데 문제를 보면 알겠지만 k번의 회전중 한 번의 회전을 하는 동안에는 내부의 톱니바퀴가 움직이지 않은 값을 기준으로 맞닿은 부분을 확인해주어야한다.그렇기 때문에 한번 회전할 때 어떤..