알고리즘

bisect정렬된 배열에서 특정 원소를 찾을때 사용bisect_left(a, x)\-> 정렬된 순서를 유지하면서 리스트 a 에서 삽입할 x의 가장 왼쪽 인덱스arri 가 dp의 마지막 원소 즉 앞에 봤던 원보다 가장 클 경우dp에 마지막 위치에 추가함arri 가 dp의

입력을 받을때 개행문자(\\n)이 같이 들어와서 strip으로 제거해주었다.for문에서 i 값이 안바껴서 while문으로 순차적으로 진행 하였다.ai번째 문자부터 i+bc(b의 문자열의 길이) 까지의 문자랑 b의 문자랑 같을경우 cnt를 1개 더해주고 i + bc를 해

접근한 방법은 처음 '-' 가 나오기 전까지는 다 더하고 그 이후에는 다 빼면 되는 것이다.예를 들어보면 10+20-30+20+30-20+30-20+30 이라고치면 괄호를10+20-(30+20+30)-(20+30)-(20+30) 이렇게 만들면 된다.즉 마이너스가 한번

배열을 거꾸로 뒤집어서 i번째 인덱스값이 i-1보다 클 경우에는 i번째 값 -1을 만들면 최소한으로 감소하게 할수있으므로 결과값 cnt에는arri - (arri-1-1) 만큼 i번째 값을 감소시키면 되므로 이 값을 저장한다.그리고 arri 를 arri-1-1 값을 저

arrlen 에는 다음 주요까지 가는 길이(km) 가 들어 있고 arr에는 현재 주유소 기름값이 저장되어있다.초기값으로는 처음 주유소에서 무조건 한번은 넣어야하니 arr0 \* arrlen0 을 넣었다.주유소에서 기름을 무제한으로 넣을 수 있다고 했으므로 가장 싼곳에서

우선순위 큐 , 힙을 사용해서 문제를 풀었다.입력받은값을 최소힙으로 다 넣어주고heap크기가 1일때까지 pop을 2번 실행해서그값을 더하고 cnt , 결과값에 저장해주고 그값을 다시 heap에 넣어준다.우선순위 큐 , 힙을 사용하여 알고리즘은 처음 풀어봤는데많이 편한것

간격사이 값을 최소로 하면서 통나무를 배치하는 최적의 구조는 아래와 같은 그림이여야 한다.결과값은 배열을 sort하고 i랑 i-2 의 차이가 가장 큰 값을 출력하면 된다.이번에도 힌트를 얻었는데 그리디 문제를 더 풀어봐야할것같다.

입력 값이 1일경우 곱하면 오히려 다음수에 곱하지 못해서 괄호를 하지않고 바로 결과값에 1을 더하고0보다 크면 parr 에 넣고0보다 같거나 작을경우에는 marr에 넣는다parr는 오름차순 정렬을 해서 젤끝에부터 , pop을 2번 실행해서 곱해주고parr의 길이 len

입력 조건에 mvp 등급이 떨어질 경우는 없기때문에 떨어지는 경우는 빼고 코드를 짰다.2개월 동안 합친 과금액이 그 달의 mvp 등급이기 때문에전에 달에 과금액 + 이번달에 과금액이 현재 달에 mvp등급즉 BS 이고 30 60 일경우에는1번째 달에는 29만원 2번째 달

값을 구하는 방식은 위에 주석에 있다.주사위 구조는 마주보는 면 빼고는 모든 면이 붙어있기때문에마주보는 면 3개 중에서 가장 작은것들 선택하면 최소값이 된다.그리디 알고리즘이라기 보단 그냥 단순 수학문제를 푸는 기분이였다.가장 작은 3면을 찾는것이 좀 어려웠다.

처음엔 크레인 입력 받는 부분이 정렬되어 입력 받는줄 알아서 조금 문제가 있었던것 같다.우선 입력을 받고 weight , crain 을 내림차순으로 정렬을 한다.내림차순으로 정렬하는 이유은 큰 무게부터 없애기 위해서 이다.그리고 weight의 최대무게가 crain의 최

처음 접근을 그리디로 접근을 했어서 답이 틀렸었다.dp로 풀면 간단하게 풀리는 문제였다.dp로 현재값 - arri , 10원이 현재값이면 10원 - 현재동전값이 3원 이면 7원 일때 개수 +1 아니면 10원을 전에 만들었던 값과 비교해서min을 사용해서 더 작을것을 선

우선 간단한 ? DFS 문제이다. 리프 노드까지 내려가서 양이 몇마리가 올라오는지 체크를 하면 된다.우선 리프노드까지 내려가서 양이면 부모노드에 올라가는 양을 return 해주고양이 아닐경우에는 0 을 부모노드에 return 해준다.해당 노드마다 자식노드에서 올라온 양

자라는데 가장 오래걸리는 묘목 부터 심기위해서 배열을 sort가장 작을것을 마지막에 심기 때문에1번째는 -0 , 2번째는 마지막을 심기전에 심었으니 -1 그렇게 for문을 n번 돌리면 가장 오래걸리는 묘목에는 -n 그전에는 -(n-1)여기서 가장 큰값을 고른뒤에 처음심

ord는 파이썬 문자열을 아스키코드로 바꿔주는것이다.아스키코드 표는출처그래서 ord(문자)+13 >90 , > 122 일때 두가지경우에는 a,A에서 더해야 하니까두개의 조건을 넣어주고공백 , 숫자일경우에는 그냥 넘어가야하니 ord해서 65보다 작을경우 continue를

순열을 만들기 위해서itertools permutations함수를 사용했다permutations는 순열을 구해주는 함수이다순열 , 조합이 있는데조합은 combinations 함수를 사용한다순열은 \[1,2] , \[2,1] 이 두개를 다른것으로 취급하고조합은 같은것으로

이분탐색으로 총합이 m보다 작을경우 start 를 mid+1m보다 클경우는 end를 start-1 을 해서 이분탐색을 한다이분탐색을 오랜만에 할려고 하니까 손이 안갔다..arr배열을 정렬하고 가장 작은원소 , arr0 부터 max(arr) 까지 중에서 탐색을 했는데50

완전 하드코딩했다... 오류찾기가 너무 힘들었다조건별로 북,남 서,동 일경우에만 시계,반시계 중에 가까운것으로 return을 해주고 아닐경우에는 시계 , 반시계 중에서 가까운곳을 고정해서 return을 해줬다.하드코딩하는것보다 규칙찾기가 더 귀찮았다..아무튼 맞았습니다

비트마스킹을 어떻게 하는지 몰라서 그냥 풀었다..n = 23 이라고 가정일단은 res에 64를 포함그리고 64를 2로 나눔 -> 3232 >= 23 이기때문에 res에 32를 넣음그리고 32를 pop32 를 2로 나눔 -> 1616 < 23 이기때문에 res에 1

간단한 bfs 문제이다.' 벽을 뚫고 갈 수 있다.'이게 포인트 인데처음에는 드릴을 뚫었나 안뚫었나 이것만 생각해서visited 에는 count값, 오는데 걸린 횟수를 넣고0 , 1 로 뚫고왔는지 안뚫고 왔는지를 체크했다.이렇게 하니 11%에서 막혔다.그래서 visit

위상정렬을 이용하여 풀이를 했다.위상정렬이란 앞에 진입하는 간선노드가 없는경우 실행을 하는 방식이다.res에 연결된 간선노드개수를 삽입을 해주고반복문을 통해서 진입하는 간선노드가 없는경우 큐에 삽입을 노드 번호 , 학기를 삽입을 해준다그리고 해당 노드랑 연결되어 있는

우선 B로 글자전체를 채운다고 가정입력이 10 12 가 들어왔으면 10줄에 12개의 쌍이 필요함B B B B B B B B B B 로 시작한다고 가정A를 하나 삽입B B B B B B B B B A 일경우에는 쌍이 0B B B B B B B B A B 일경우에는 쌍이

예상 등수를 입력을 받고 정렬을 함예상 등수가 낮은것 부터 순서대로 등수를 주는것이 불만도가 가장 작다학생들의 등수가1 1 1 2 3 4 등이면 순서대로1 2 3 4 5 6 등으로 주는데여기서 예상등수 - 등수 를 해주면 1)1,1-2,1-3, 이렇게 음수 가 나오게

sort함수에는 매개변수로 key를 받을 수 있는데arr.sort(key=lambda a:a0)이런식으로 하면 각 배열에서 0번째를 기준으로 정렬을 할 수 있다.(1,2,3),(2,3,4) 이런배열이 있으면 0번째 인덱스 기준으로 정렬이 된다.heapq로 list배열을

n의 개수가 1,00,000개라서 n제곱 복잡도로 하면 시간 초과가 날것같아서O(n) 복잡도로 생각을 해봤다.처음에는 앞에 풍선의 높이보다 1작을경우에 넘어가고 아닐경우에는 화살의 개수를 늘렷다.매우 틀린답..그래서 해당 높이에 화살이 날라가고 있는지 체크하는 배열 r

bfs로 모든 경우의 수를 훑어보면 풀리는 문제예외처리 핵심 부분indexerror -> cur-1 >= 0 , cur \* 2 <= 100000 확인을 먼저 해야함visited에 바로 인덱스 접근을 해버리면 에러가 뜬다.cur-1 >= 0 에서 같거나 클 경우를

bfs를 두번 사용처음 bfs를 돌면서 섬의 번호를 붙임외곽쪽에 섬의 번호를 -로 마킹을 함섬의 개수만큼 bfs를 돌림섬의 외곽 마킹한곳에서 부터 다른 섬이랑 이어질때까지 bfs를 돌림bfs를 돌렸을때 가장 적은 거리로 갱신을 해줌bfs 할 때 주의큐에서 빼면서 vis

한쪽 방향으로 기울이면 끝까지 보내준다.동시에 빠지면 실패같은위치에 있는 경우면 이동을 덜 한것이 먼저 도착하므로 이동을 많이 한 공 위치를 뒤로 한칸 빼준다.

k번째 수는 최대 k값을 가짐k번째의 수 보다 작은 수의 개수를 찾음mid의 값보다 작은 수의 개수는EX) 3 3 에서 7보다 작은 수의 개수는11 ~ 13 = 3개 = min(n,7/1) = 321 ~ 23 = 3개 = min(n,7/2) = 331 ~ 3\*2

현재 위치에서 \*2 로 이동하는것은 비용이 0 이다.1번에 의해서 큐에 제일 앞에 넣어줘서 \*2로 이동할 수 있는 모든경우의 수 를 dis(거리)에 저장을 해준다.그 이후에 + 1 , -1 거리를 이동하는 경우를 넣어준다.제일 중요한건 \*2로 이동하는 가중치가 0

(예외처리) n == k 일 경우에는 res 0 , 1 이 출력되어야함방문처리 , EX) 10이란 숫자에 방문횟수가 1번 이상일수도 있다.예외처리만 잘 해주면 BFS만 하면 정답이 나오는 것 같다.

이진트리가 아니다 자식 노드가 2개 이상일 경우도 생각해야함일자로 길이를 했을경우가 자식노드 두개를 연결했을 경우 보다 더 길 수도 있다.DFS를 할 때 a -> b노드 의 가중치를 인자로 넣어준다.다음 b의 자식노드를 돌아서 가장 긴 값을 받은 가중치 인자랑 더해서

문제 입력 , 출력 solution 설명 키포인트 > 1. 이분탐색 , 투포인터를 사용해서 풀이 mid값으로 하지 않고 left , right만 사용함 두 값을 더했을 경우 0보다 작은경우 0보다 같거나 큰경우는 오른쪽 포인터에 인덱스를 1씩 더해준다. 두가지

1번 메모리 초과최대힙으로 만들어서n번째를 출력하는 방식으로 구현을 함하지만 메모리초과..n은 최대 1500처음 반복문 에서 nlogn(n = 1500\* 1500 =2250000)4500000log(1500)≈14292410.665750567두번째 nlogn (n =

최소스패닝 트리를 구현만 하면 풀리는 문제이다처음에 parent 배열을 만든 뒤에 자기 자신을 조상으로 만든다.그리고 (a,b) = 연결된 노드 , c = 간선의 가중치간선의 가중치를 기준으로 입력받은 배열로 정렬해준다.사이클 없이 최소한의 가중치로 연결을 하는 것 이

특정 노드를 선택해서 가장 먼 거리에 있는 노드(B)를 찾는다.찾은 노드(B) 에서 dfs로 가장 먼 거리에 있는 노드의 거리가 트리의 지름이된다.해당 알고리즘의 증명트리의 지름 증명트리의 지름을 구하는 방법만 알면dfs를 두번 돌리면 풀리는 간단한 문제

입력 배열의 파싱 , 0번째 인덱스와 마지막 인덱스를 제외하면1,2,3,4 = > 1,2,3,4 로 만들어지므로arr1:-1 로 하면 1,2,3,4 라는 문자열이 만들어진다.여기서 split(',') 하면 '1','2','3','4' 가 만들어진다.R을 할 시에는 배열

그냥 무식하게 2중 반복문을 사용함20 \* 20 \* 20 시간 복잡도로 충분히 가능한 시간인줄 알았는데50점이 나왔다누적합 풀이로소문자 a~z까지 총 26개 \* name의 길이 로 2차원 배열을 생성a~z를 아스키코드로 변환 한 뒤에 -97을 하면 0~25까지 된

공간 복잡도 : v^2시간 복잡도 " v^3소스가 더 간결함간선 수가 많으면 다익스트라 알고리즘보다 빠를 수 있음시작점으로부터 각 정점까지 최단거리만 구할때에 보통 다익스트라가 압도적으로 빠름그래프에 음의 가중치 간선이 있으면 다익스트라 알고리즘은 사용불가 But 플로

여러 개의 데이터가 존재할 경우 구간의 합을 구하는데 사용하는 자료구조트리 종류 중에 하나이고 이진 트리의 형태이며 특정 구간의 합을 가장 빠르게 구할 수 있다. O(logN)tree 의 크기를 할당 할때에는 배열의 개수가 N 일때는 N보다 큰 가장 가까운 N의 제곱수