본문 바로가기

알고리즘10

[알고리즘 / Swift] 힙 Heap Heap 이란? 데이터에서 최댓값 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리로 우선순위 큐를 위해 만들어진 자료구조 최대힙(max heap) : 부모노드 ≥ 자식노드 최소힙(min heap) : 부모노드 ≤ 자식노드 💡 완전 이진 트리란? 이진트리 = 자식 노드가 최대 두 개인 트리 완전 이진트리 = 마지막 레벨을 제외한 모든 노드가 2개씩 채워져 있으며, 최하단 레벨 또한 좌측부터 채워져있는 노드를 의미한다. 즉 완전 이진트리는 왼쪽부터 자식 노드를 차례로 채운다. index 성질 heap은 완전 이진 트리 구조이기 때문에 노드 간 인덱스 관계를 나타낼 수 있다. → 완전 이진트리는 무조건 왼쪽부터 채워지기 때문에 채워지는 순서가 있음 = index 부모 노드 index = 자식 노드 index .. 2024. 3. 13.
[Level 1] [python] 기사단원의 무기 문제 https://school.programmers.co.kr/learn/courses/30/lessons/136798 파이썬 풀이 def getMyDivisorLen(n): divisorsList = [] for i in range(1, int(n**(1/2)) + 1): if (n % i == 0): divisorsList.append(i) if ( (i**2) != n) : divisorsList.append(n // i) return len(divisorsList) def solution(number, limit, power): answer = 0 for i in range(1, number+1) : divisorLen = getMyDivisorLen(i) if divisorLen > limit.. 2022. 11. 17.
[Level 1] [python] K번째수 문제 파이썬 풀이 def solution(array, commands): answer = [] for i, j, k in commands : new_arr = array[i-1 : j] new_arr.sort() answer.append(new_arr[k-1]) return answer 배열을 인덱싱을 이용하면 쉽게 풀 수 있는 문제였다. i번째는 인덱스로 i-1이고 인덱싱에서 end는 포함하지 않기 때문에 (j-1) 번째에 +1을 해줘서 j까지로 잘라낸다. 그리고 파이썬의 sort()함수를 이용해 잘라낸 배열을 정렬해주었다. 그리고 k번째(인덱스 k-1) 값을 answer배열에 추가해주었다. 2021. 12. 29.
[python] 2667번 - 단지번호붙이기 문제 파이썬 풀이 2차원 리스트에서의 탐색은 어떤 식으로 해야 하는지 이해하는데 조금 어려웠었다. 여기서의 포인트는 탐색할 방향인 상하좌우를 이동 좌표를 리스트에 담아 for문을 통해 탐색을 진행하는 것이다. 그리고 탐색의 방법도 dfs를 통해 재귀로 탐색하였다. 좌표 리스트 dx=[-1,0,1,0] dy=[0,1,0,-1] 해당 좌표는 dx, dy에서 같은 인덱스끼리 묶어보면 (-1, 0), (0, 1), (1, 0), (0, -1)로 각각 좌(x축으로 -1 이동), 상(y축으로 +1 이동), 우(x축으로 +1 이동), 하(y축으로 -1 이동)를 의미한다. DFS 탐색 함수 def dfs(x,y) : global cnt matrix[x][y] = "0" #방문한 곳 0으로 만들기 cnt+=1 #카운트 .. 2021. 12. 8.

티스토리툴바