본문 바로가기

두두의 알고리즘

 (145)
[힙] 백준 11286번 '절댓값 힙' (Python) https://www.acmicpc.net/problem/11286 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 1. 최솟값이라는 우선순위대로 출력하므로 힙 사용 #내코드 #17분/40분 import heapq import sys input = sys.stdin.readline result = [] queue = [] n = int(input()) for i in range(n): x = int(input()) if x != 0: heapq.heappush(queue,[ab..
[손코딩] 문제 1~3 1. 회문은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미함. 회문을 판별할 수 있는 함수를 리스트 슬라이싱을 활용해서 만드세요 ex) rumur 질문 ex) string 변수에 null(None)이 올 수 있는지, null이 왔을 때 함수의 리턴값이 무엇이 되어야 하는지 2. 특정 기간 동안의 가격 변화가 주어졌을 때, 그 주식 한 주를 한번 사고 팔아 얻을 수 있는 최대 수익을 계산하는 알고리즘을 만들어 보세요 질문 ex) 가격 변화가 어떻게 주어지는지 : 파이썬 리스트 형태로 원화 형태로 가격(숫자)이 주어짐 (0번 인덱스가 가장 이전 시간, 그리고 순차적으로 해서 마지막 인덱스가 가장 나중 시간) output : [최대수익, 언제 샀는지, 언제 팔았는지에 대한 인덱스 번호] de..
[자료구조/알고리즘] 주요 지식 1. 배열과 링크드 리스트의 장단점에 대해 간략히 설명해주세요 2. BST의 최악의 시간 복잡도와 최악의 시간이 걸리는 케이스에 대해 설명해주세요 3. 해쉬 테이블에 대해 설명해주세요 4. Fibonacci 공식을 recursive와 dynamic programming으로 구현시 차이점에 대해 설명해주세요 5. DFS와 BFS에 대해 간략히 설명해주세요
[알고리즘] 백 트랙킹(Back Tracking) - N Queen 문제 백 트래킹 (backtracking) 백트래킹 (backtracking) 또는 퇴각 검색 (backtrack)으로 부름 제약 조건 만족 문제 (Constraint Satisfaction Problem) 에서 해를 찾기 위한 전략** 해를 찾기 위해, 후보군에 제약 조건을 점진적으로 체크하다가, 해당 후보군이 제약 조건을 만족할 수 없다고 판단되는 즉시 backtrack (다시는 이 후보군을 체크하지 않을 것을 표기)하고, 바로 다른 후보군으로 넘어가며, 결국 최적의 해를 찾는 방법 실제 구현시, 고려할 수 있는 모든 경우의 수 (후보군)를 상태공간트리(State Space Tree)를 통해 표현** 각 후보군을 DFS 방식으로 확인** 상태 공간 트리를 탐색하면서, 제약이 맞지 않으면 해의 후보가 될만한..
[자료구조] 힙(Heap) - 기본코드 / 라이브러리 1. 힙 (Heap) 이란? - 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) - 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 - 힙을 사용하는 이유 - 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림 - 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, $ O(log n) $ 이 걸림 - 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 5. 힙 (Heap) 시간 복잡도 - depth (트리의 높이) 를 h라고 표기한다면, - n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제시, 최악의 경우 root 노드에서 le..
[자료구조] 트리(Tree) - 이진 탐색 트리 1. 트리 (Tree) 구조 - 트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 - 실제로 어디에 많이 사용되나? - 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨 2. 알아둘 용어 - Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) - Root Node: 트리 맨 위에 있는 노드 - Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 - Parent Node: 어떤 노드의 다음 레벨에 연결된 노드 - Child Node: 어떤 노드의 상위 레벨에 연결된 노드 - Leaf Node (Termin..
[자료구조/알고리즘] 연결 리스트(Linked List), 더블 연결 리스트(Double Linked List), 트라이 구조(Trie) 리스트란? 데이터를 인덱스 값에 따라 저장 대량의 데이터에서 추가와 삭제 시 성능이 저하된다. 연결 리스트란? 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 데이터를 저장하는 자료 구조 [링크드 리스트 (Linked List) 구조] * 연결 리스트라고도 함 * 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 * 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 본래 C언어에서는 주요한 데이터 구조이지만, 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원' [링크드 리스트 기본 구조와 용어] - 노드(Node): 데이터 저장 단위 (데이터값, 포인터) 로 구성 - 포인터(pointer): 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보..
[자료구조 / 알고리즘] 개념, 연습 방법 자료구조란? 용어: 자료구조, 데이터 구조, data structure 대량의 데이터를 효율적으로 관리할 수 있는 데이터의 구조를 의미 현실세계 정보를 어떻게 데이터로 변환해서 구조를 만드느냐 코드상에서 효율적으로 데이터를 처리하기 위해, 데이터 특성에 따라, 체계적으로 데이터를 구조화해 야 함 어떤 데이터 구조를 사용하느냐에 따라, 코드 효율이 달라짐 [효율적으로 데이터를 관리하는 예] 우편번호: 5자리 우편번호로 국가의 기초구역을 제공 학생 관리: 학년, 반, 번호를 학생에게 부여해서, 학생부를 관리 [대표적인 자료구조] 배열, 스택, 큐, 링크드 리스트, 해쉬 테이블, 힙 등 현실 세계의 가장 대표적인 데이터 구조? - 사전 알고리즘이란? 용어: 알고리즘, algorithm 어떤 문제를 풀기 위한 ..
LIST

티스토리툴바