자료구조11 [알고리즘] convex hull(컨벡스 헐) 계산 기하 2/3차원 공간상에서 점, 선, 도형 간의 관계를 다루는 문제 실생활에 매우 밀접하게 응용된다. 일단 2차원 공간/정수 좌표/정수 연산으로 가정한다. → 가급적 +,-,*,>,=, 2023. 5. 2. [백준/6236] 용돈 관리 | 이진 탐색 트리 | 분할 | 파이썬 https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 이진 탐색 / 이진 탐색 트리를 공부하고 첫 활용 문제를 풀어봤다. 이 문제가 왜 이진 탐색이냐면 N일 동안 사용하려고 계획한 금액에 맞게 최소 K 값을 구해야 하는데, 이때 K원은 M번에 맞춰서 출력이 해야 하기 때문에 분할 개념으로 최소 K가 나올 때까지 탐색을 하기 때문이다. 분할(partition) 분할은 말 그대로 여러 개로 나눈다는 뜻인데, 이산수학에서의 분할은 보통 집합의 분할을 뜻한다. .. 2023. 2. 14. [Python] 파이썬 딕셔너리 개요 '코드트리'에서 파이썬 딕셔너리를 공부한 내용이다 코드트리 자료가 생각보다 이해하기 정말 쉽게 되어있고, 중요한 부분을 잘 집어줘서 기록하고 두고두고 볼 예정 파이썬 딕셔너리(Python Dictionary) 파이썬 딕셔너리는 검색/삽입/삭제에 유용한 HashMap 자료구조이다. * HashMap: (key, value) 쌍으로 이루어져 있고, 순서와 상관없이 빠른 검색/삽입/삭제(시간복잡도 O(1))가 가능한 자료구조 딕셔너리 선언 파이썬 딕셔너리는 다음과 같이 선언한다. d1 = dict() d2 = {} d3 = { 'apple' : 1, 'banana' : 2, 'grape' : 3 } key와 value 딕셔너리의 기본적인 구조는 dic_name[key] = value 이다. key 값을 .. 2023. 2. 13. [백준/1021] 회전하는 큐 | python deque | dequed의 rotate() 파이썬 deque deque는 문제풀이에서 종종 사용했었지만 주요 내용을 다시 한번 정리해보았다. 알고리즘 파이썬 deque 자료구조를 알고있다면 어렵지 않게 해결할 수 있다. 최종코드 from collections import deque n,m = map(int, input().split()) que = deque(range(1,n+1)) idx = list(map(int, input().split())) cnt = 0 for i in idx: # 다 찾을 때까지 수행 while True: # 찾고자 하는 값의 위치가 중간보다 왼쪽인 경우 if que.index(i) 2023. 2. 12. [자료구조] 트리(Tree) 트리 트리란? 회사의 조직도, 가계도와 같이 나무처럼 뻗어나가는 모양의 사이클이 없는 그래프다. 노드 간선 루트 노드: 트리의 맨 꼭대기 부모 노드/자식 노드 리프 노드: 자식이 없는 노드 차수와 깊이 그리고 높이 차수: 특정 노드의 자식 수 깊이: 특정노드로부터 루트노드와 떨어져있는 정도 높이: max깊이 + 1 이진트리 트리의 자식을 2개로 한정하면, 이진트리 배열로 나타내기 좋다. 부모는 i, 왼쪽 자식은 i2, 오른쪽 자식은 i2+1 만약 모든 자식이 꽉 차있지 않다면 배열도 같이 비워줘야한다. 이진트리는 한번 알면 여러모로 편하다.. 자식이 2개로 제한되어 있기 때문에 구현도 좋다… 그러니 확실하게 알아둘 것! 트리의 순회 트리를 탐색하는 순회 방법은 3 가지가 있다. 전위 순회(왼>뿌>오) 중.. 2023. 1. 24. [백준/11179] 2진수 뒤집기 이 문제는 2진수 -> 10진수 변환과 10진수 -> 2진수 변환 모두를 구현해야 하는 문제이다. 파이썬 내장 함수와 문자열 인덱싱을 통해 쉽게 구현할 수도 있지만, 직접 코드를 작성해보았다. 💻 최종 코드 n = int(input()) b = [] x = 0 ans = [] c = 0 while n != 0: if n % 2 == 0: b.append('0') else: b.append('1') n //= 2 # 뒤에서부터 append 되니까 어차피 뒤집혀 나옴 s = ''.join(b) for i in range(len(s)-1,-1,-1): x = int(s[i]) * 2 ** c ans.append(x) c += 1 print(sum(ans)) while 문은 10진수를 이진수로 변환한 코드이다... 2023. 1. 12. [백준/2947] 나무 조각/정렬/두가지 풀이 💻 내 풀이 직관적인 풀이라고 생각하지만 정석보다 우회해서 푼 느낌이라 코드를 더 찾아봤다. t = input().split() tmp = 0 s = sorted(t) while True: for i in range(1,len(t)): if t[i-1] > t[i]: tmp = t[i-1] t[i-1] = t[i] t[i] = tmp print(*t) if t == s: break 💻 다른 풀이 t = input().split() for j in range(len(t)): for i in range(1,len(t)): if t[i-1] > t[i]: t[i-1], t[i] = t[i], t[i-1] print(*t) 내 기억상 이게 버블소트랑 가장 가까웠던 것같다. 출처: https://it-garden.. 2023. 1. 11. [자료구조] Deque와 파이썬의 collections ✔ 덱(deque)이란? double ended: 양 끝이 닮은, 앞뒤가 없는..이라는 뜻이다. 따라서 데큐는 양 끝 모두가 출입구가 되므로, 양방향으로 push&pop이 가능하다. (stack은 한쪽으로만 입출력!) 데큐는 큐의 일종으로, FIFO(First In First Out: 먼저 넣은 데이터가 먼저 나오는) 구조이다. 선착순을 떠올리면 직관적으로 이해할 수 있다. 📝 덱(deque)의 성질 덱은 가장 앞부분을 가리키는 front와 가장 뒷부분을 가리키는 back이 구성되어있다. 따라서 push_front push_back, pop_front pop_back 을 모두 활용할 수 있다!! 데큐를 쓰는 이유는 https://wiki.python.org/moin/TimeComplexity 를 읽어보면.. 2022. 12. 24. [백준/1927] 최소 힙 문제를 잘 이해하면 구현은 어렵지 않다. ✍️ 첫번째 시도 import sys n = int(sys.stdin.readline()) heap = [] # 자연수라면 in heap 0이라면 출력 + out heap for _ in range(n): x = int(sys.stdin.readline()) if x == 0 and len(heap) != 0: print(min(heap)) heap.remove(min(heap)) elif x != 0: heap.append(x) else: print(0) 혼자서 문제에 따라 잘 구현한 것같은데,, 시간 초과ㅠㅠ 구글링 후 알게된 점은 파이썬에서 따로 heappush, heappop을 제공한다는 것이었다..! (from heapp 모듈) 📝 파이썬 heapq 모듈.. 2022. 12. 23. [백준/2747] 피보나치 수 with 동적 계획법 이 내용은 알고리즘 수강 시간에 배웠던 내용이라 눈치를 챌 수 있었다. def fibo(n): if n == 0: return 0 elif n == 1 or n == 2: return 1 else: result = fibo(n-1) + fibo(n-2) return result print(fibo(int(input()))) 단순히 이렇게 재귀형식으로 피보나치 수열을 만들 수 있지만, 이렇게 되면 fibo(10)을 구하기 위해 fibo(9)와 fibo(8)을 구해야 한다. fibo(9)를 구한 다음, fibo(8)을 구하려면 다시 처음부터 구해야 한다. 따라서 시간 복잡도는 T(n) = T(n-1) + T(n-2) 결국 T(n) >= 2^n/2T(1)으로, 지수 시간이 걸리게 된다. 😱 이를 해결하기 위해.. 2022. 12. 22. [python] 리스트에 대해서 알아보자. 프로그래밍을 공부하는 사람이라면 한번 쯤은 알고리즘과 자료구조에 대해 들어보았을 것이다. 알고리즘은 특정 문제를 해결하기 위한 단계를 뜻하고, 자료구조는 컴퓨터 내에서 자료를 구조화하는 특별한 방식이다. 우리는 알고리즘과 자료구조를 통해 효율적인 프로그래밍을 할 수 있다! 자료구조의 한 종류인 리스트에 대해 알아보자. 1. 리스트란? 리스트는 기본적으로 리스트 상수이며, 어떤 변수에 할당된다. friends = ['Amy', 'Jack', 'Effy'] fruits이라는 변수는 3개의 문자열을 가지고 있는 것이다. 리스트는 컬렉션의 한 종류이다. 컬렉션: 하나의 변수에 여러 값을 넣는 것이 가능하도록 하는 것! 2. 리스트 선언 리스트의 각 항목들은 '[]'로 둘러싸이게 되며, 항목들에 대한 구분은 ,(.. 2022. 8. 13. 이전 1 다음
