jenlog

🔍 투포인터(Two Pointers) 리스트에 순차적으로 접근해야 할 때 start point와 end point의 위치를 기록하면서 해결하는 방법 🔍 구간 합(Prefix Sum) ◾ 부분 합 : 0~k 까지의 합 ◾ 구간 합 : i~j 까지의 합 N = 5 lst = [10, 20, 30, 40, 50] # Prefix Sum 배열 계산 tmp = 0 prefix_sum = [0] for num in lst: tmp += num prefix_sum.append(tmp) # 구간 합 계산 left = 3 right = 4 print(prefix_sum[right] - prefix_sum[left-1]) boj 2003 코드 def sol(N, M, a): s, e = 0, 0 subsum = a[0] ..

🚩 heap, 자료구조, 우선순위 큐 thinking input이 10만줄 이상으므로 sys.stdin.readline() 을 사용했고, 파이썬의 heapq 모듈을 사용하여 해결했다. 코드 1927. 최소힙 import sys import heapq N = int(sys.stdin.readline()) heap = [] for _ in range(N): x = int(sys.stdin.readline()) if x == 0: if heap: print(heapq.heappop(heap)) else: print('0') else: heapq.heappush(heap, x) 11279. 최대힙 heapq 모듈은 기본적으로 최소힙만을 지원하기 때문에 최대힙을 구하려면 튜플이나 리스트형식으로 넣어 0번째 인덱스..

🚩 그래프, BFS thinking 큐를 만든다음, 사방 탐색하면서 아직 방문 안했고(==색깔 확인 안했고) 같은 색인 경우 방문체크 후 큐에 넣었다. 적록색약인 경우는 R과 G가 같으므로 하나의 컬러로 통일 시킨다음 BFS과정을 똑같이 반복했다. N이 100까지라 이중 for문 여러번 돌려도 상수*N*N= c*10000 밖에 안되서 시간초과 노걱정 코드 from collections import deque def BFS(x,y): q.append((x,y)) dx = [-1,0,1,0] dy = [0,1,0,-1] visited[x][y] = 1 while q: x, y = q.popleft() for d in range(4): nx = x + dx[d] ny = y + dy[d] # 인덱스 범위 안에..

🚩 브루트포스 thinking 아악 진짜 이거 계속 틀려서 구글링해봤다 나는 N의 최대 범위가 500,000이라 500000까지만 체킹하면 된다고 생각했는데 다른사람들은 다 range를 100만으로 잡는게 진짜 이해가 안갔다. 50만 채널까지 존재하기 때문에 50만보다 크면서 모든 숫자의 경우를 거치는 100만까지를 범위로 잡았다는데 도대체 이게 뭔말이야 😑 뭔말이냐면 내가 이동하고 싶은 채널이 N(0~500,000) 번이라고 했을 때, 0번부터 ++로 이동하는 경우와 999,999번부터 --로 이동하는 경우(누를 수 있는 버튼이 9만 있으면 9밖에 못누르기 때문)를 전부 고려한 것이었다. 가능한 숫자를 하나하나 전부 순회하면서 누를 수 있는 숫자에 해당하는 경우만 조건문 처리를 통해 최소 갭을 계산해줬..

🚩 그래프탐색, BFS thinking queue에다 처음 1인 애들의 좌표를 다 넣고 사방탐색하면서 1로 바꾸고, 바꾼 애들의 좌표를 또 큐에 넣고 이런식으로 해결했다. 그리고 경로 길이를 구해야해서 길이체크할 visited를 만들어줬다. ▶ point 1 처음부터 모두 1이면 0을 출력, 최종적으로 0이 남아있으면 -1을 출력해야 하는데 이걸 어떻게 해야할까 고민하다 파이썬의 all과 any에 대해 알게됐다. 대박사건 all(), any() 함수는 파이썬 빌트인 함수이며 조건 성립 유무에 따라 True / False를 리턴해준다. 인자는 하나만 올 수 있고, 반복가능한 자료형(iterable)이어야한다. 파이썬에서 빈 값, 0, None은 False로 인식한다. All 조건이 전부 True이면 Tru..