본문 바로가기

Python

 (36)
프로그래머스 연습문제 - 두 정수 사이의 합 문제 두 정수 a, b가 주어졌을 때 a와 b 사이에 속한 모든 정수의 합을 리턴하는 함수, solution을 완성하세요. 예를 들어 a = 3, b = 5인 경우, 3 + 4 + 5 = 12이므로 12를 리턴합니다. 제한조건 a와 b가 같은 경우는 둘 중 아무 수나 리턴하세요. a와 b는 -10,000,000 이상 10,000,000 이하인 정수입니다. a와 b의 대소관계는 정해져있지 않습니다. 해설 1. 반복문으로 풀기 def solution(a, b): answer = 0 if (a == b): return a n = b if a > b else a m = a if a > b else b for i in range(n - 1, m): answer += i + 1 return answer 둘 중 작은..
프로그래머스 연습문제 - 정수 제곱근 판별 문제 임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다. n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요. 제한 사항 n은 1이상, 50000000000000 이하인 양의 정수입니다. 풀이 import math def solution(n): answer = 0 x = math.sqrt(n) if (int(x) == x): answer = (x + 1) ** 2 else: answer = -1 return answer 해설 어떤 수 x를 제곱해서 n이 되는 수를 n의 제곱근이라고 한다. 즉, x는 n의 제곱근인지 아닌지를 판단하는 문제이다. 위 문제에서는 양의 정수 x가 n의 제곱근이면..
[좌충우돌, 파이썬으로 자료구조 구현하기] 이진 탐색 트리 구현하기 숫자 맞추기(Up Down) 게임은 이진 검색을 이용한 것이다. 1 ~ 100 사이에 임의의 숫자를 맞추는 놀이를 할 때, 처음 추측하는 값은 50으로 한다. 그러면 이 값보다 크거나 작은지에 따라 Up, Down이라고 얘기하면서 다시 그 사이의 값을 추측하는 방식으로 답을 찾는다. 이러한 방식이 이진 검색이다. Up과 Down을 왼쪽과 오른쪽으로 바꿔서 생각해보자. 이진 트리는 앞서 공부했으므로 이진 트리와 이진 탐색 트리의 차이점을 알아보자. 모든 왼쪽 서브 트리의 노드는 루트 노드보다 작다. 모든 오른쪽 서브 트리의 노드는 루트 노드보다 크다. 왼쪽과 오른쪽 서브 트리도 모두 이진 탐색 트리이다. 중복 노드는 없다. (a)는 이진 탐색 트리이지만, (b)는 이진 탐색 트리가 아니다. 값이 1인 노드..
[좌충우돌, 파이썬으로 자료구조 구현하기] 더 맵게 - 프로그래머스 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 가장 안 매운 스코빌 지수와 두번째로 안 매운 스코빌 지수를 섞는다고 하니 우선순위가 있는 큐 자료구조인 힙으로 구현할 수 있다. 최소 힙 구조를 떠올리면 heappop을 2번하여 나온 결과를 다시 최소힙에 heappush 하는 과정을 반복하면서 루트 노드에 있는 요소가 주어진 K보다 크면 섞은 횟수를 반환한다. import heapq def solution(scoville,K): an..
[좌충우돌, 파이썬으로 자료구조 구현하기] Heapify 구현하기 주어진 배열이나 이진트리를 힙 구조로 재배열 하는 것을 heapify라 한다. h = [] arr = [21, 33, 17, 27, 9, 11, 14] for i in arr: heappush(h,i) print(h) >>> [9,17,11,33,27,21,14] 위 코드처럼 배열의 원소를 차례로 heappush해서 힙 구조의 배열을 별도로 만드는 것은 쉽다. 이제는 주어진 배열 자체를 힙 구조로 만들자. 즉, 배열의 원소를 제자리 교환을 이용하여 힙 구조로 만든다. heappush에서 사용한 방식과 같이 마지막 노드에서 루트 노드로 가면서 힙 구조를 만들 방법을 생각해보자. 마지막 노드 3이 부모 노드보다 크므로 왼쪽 노드로 넘어간다. 값이 1인 노드는 부모 노드보다 작으므로, 서로 교환한다. 위로 올..
[좌충우돌, 파이썬으로 자료구조 구현하기] 힙(heap) 구현하기 큐(Queue)는 선입선출의 자료구조이다. 들어가는 자료에 우선순위를 매겨서 들어간 순서와 관계없이 나갈 때는 우선순위가 높은 자료가 먼저 나가는 구조를 우선순위 큐(Priority Queue)라고 한다. 힙(heap)이란, 우선순위 큐를 구현한 자료구조이다. 힙은 다음과 같은 규칙에 따라 구성한 이진트리이다. 규칙 1. 노드를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간다. (레벨 순서로 노드를 삽입한다.) 위 그림은 모두 이진트리인데, (a)는 힙이지만 (b)는 힙이 아니다. 왜냐하면 (b)는 왼쪽에서 부터 채워져야한다는 규칙을 벗어났다. 규칙 2. 최소 힙은 부모 노드가 자식 노드의 값보다 작거나 같아야 한다. 파이썬의 heapq 모듈은 최소 힙(min heap)이다. (최대 힙은 부모 노드가 자식..
[좌충우돌, 파이썬으로 자료구조 구현하기] 형제 노드가 없는 노드 찾기 문제 이진트리가 있을 때, 형제 노드가 없는 노드의 키를 출력하라. 형제 노드가 없는 노드가 없으면 -1을 출력하라. 37 / 20 / 113 출력: [20, 113] 풀이 형제 노드를 찾으려면 레벨 순서 순회를 해야한다. 레벨 순서 순회를 하면서 left 노드가 있을 때, right 노드가 없으면 결과 리스트에 해당 노드를 추가해준다. 반대의 경우도 마찬가지이다. def find_has_no_sibling(tree): res, q = [], [tree.root] while q: node = q.pop(0) if node.left: q.append(node.left) if not node.right: res.append(node.left.data) continue if node.right: q.appen..
[좌충우돌, 파이썬으로 자료구조 구현하기] 이진 트리에서 키를 삭제하기 문제 크기가 n인 이진트리가 주어질 때, 주어진 값(key)를 삭제하고 레벨 순서상 가작 마지막값으로 대체하는 함수를 만들어라. 풀이 삭제할 키를 가진 노드르 찾아야한다. 마지막 노드와 마지막 노드의 부모 노드를 찾아야한다. 마지막 노드를 찾아야 삭제할 곳에 마지막 노드 값으로 대체할 수 있게 된다. 또한, 마지막 노드의 부모노드를 찾고 마지막 노드가 왼쪽 노드인지, 오른쪽 노드인지 찾아서 알맞게 해당 자식노드를 None값으로 만들어줘야한다. 문제에서 레벨 순서상이라고 했으니, 특정 노드 찾는 것은 레벨 순수 순회를 이용하여 찾는다. 즉, 삭제할 키를 가진 노드를 찾기, 마지막 노드 찾기에서 레벨 순서 순회를 2번 사용해줘야한다. def delete_key(tree,key): q = [tree.root]..

티스토리툴바