전체 글(121)
-
백준 10815_ 숫자카드
1, 분류: binary search 언어: python 2, 코드
2021.07.04 -
백준 11047_동전0
1, 분류: 그리디 알고리즘 언어: 파이썬 2, 코드 3. 실패의 원인 indentation: 파이썬 같이 indentation이 중요한 언어는 더더욱 신경을 써야 한다. 시간 초과 : while문을 이용해 k 가 0이 아닌 경우에만 계산을 하는 조건을 걸었다. i =1인 경우 : 단위가 1인 동전의 경우를 배제했다. 이 경우는 특수한 경우로 꼭 신경을 써줘야 한다.
2021.07.04 -
HEAP(힙)
1. 힙: 힙 성질(heap property)을 만족하는 이진 트리 - 힙은 자식이 꽉꽉 채워져 있어야 한다. 그렇다면 힙성질이란? - 힙 성질: 모든 부모 노드의 key값은 자식 n노드의 key값 보다 작지 않다. 즉 부모님이 자식보다 더 크다! 그렇다면 root노드의 값이 가장 크다! 2. 트리를 표현하는 방법 중 리스트를 이용하여, 모든 노드를 빈 곳도 다 작성하는 방법 사용시 - 단점: 메모리 낭비가 심하다.(비어있는 곳도 None으로 저장) - 장점: 자식 노드와 부모 노드의 위치를 알 수 있다. ex) H = [a, b, c, None, d, e, f] 일때, H[k]의 왼쪽 자식 노드 : H[k*2+1] H[k]의 오른쪽 자식 노드 : H[k*2+2] H[k]의 부모 노드 : H[(k-1)/..
2021.06.29 -
TREE (트리)
1. 부모 자식 관계의 자료구조 - tree(트리) 2, 트리의 구성 - node: 구성요소 - root node: 가장 맨 위에 있는 node, 부node가 없다 - link, edge : node와 node사이를 연결 - leaf node: 가장 마지막 끝에 있는 node - height: root node 부터 leaf node 까지의 높이. 주로 h라고 한다. - 경로(path): 출발노드 ~ 경유노드~ 도착노드 / 경로 길이 3, 트리의 표현법 리스트 - level0, level1 .... A = [ a, b,c, None,d,e,f ] - 각 레벨마다 꽉 차있다고 생각. 빈 노드도 왼쪽부터 비어있음을 표시 - 나는 지금 각 level별로 분류를 해보았다. - 단점: 메모리 낭비가 심함 리스트 ..
2021.06.29 -
순차적 자료구조 - QUEUE
1. QUEUE란? FIFO(FIRST IN FIRST OUT) 규칙의 순차적 자료구조 2. QUEUE의 연산 enqueue(val): 값을 큐의 오른쪽에 삽입(push와 같다) dequeue(): 가장 왼쪽에 저장된 값을 삭제 후 리턴 front(): 가장 왼쪽에 저장된 값을 라턴. 삭제하는 dequeue()는 다르다 3. 큐의 활용 - Josephus Problem n 명의 사람이 원형 테이블에 앉아 있다. 매 k번째 사람을 죽이는데, 최종 살아남는 사람은 누구인가!! ex) 1,2,3,4,5,6,7,8,9 사람이 있고, 3번째 마다 죽인다 -> 1,2, 4,5, 7,8 -> 1,2, 5, 7, -> 1,2,7-> 1,2-> 2 출처 https://namu.wiki/w/%ED%81%90(%EC%9E%..
2021.06.28 -
순차적 자료구조 - STACK
1. STACK이란? 리스트와 다르게 제한된 접근만 허용. 즉, 삽입, 삭제만 허용하는 선형(linear)자료구조 LIFO(LAST IN FIRST OUT)의 원칙을 따른다 2. STACK의 연산 삽입: push() 삭제: pop() - 가장 위에 있는 항목을 삭제 peak() - 가장 위에 있는 항목을 리턴, 항목을 삭제하는 pop과는 다름 isEmpty() - 스택이 비어 있다면, True를 반환 java로 구현 Node public class Node { //데이터 필드 public String data; //링크 필드 //참조변수에 저장되는 객체 타입으로 타입을 선언 public Node link; public Node(String data) { super(); this.data = data; }..
2021.06.28