알고리즘

그리디 알고리즘이란?, 백준 설탕배달

탐욕 알고리즘(Greedy Algorithm)이란? Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다. 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다. 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다. 최..

트리와 힙 (파이썬 네이티브 코드로 구현하기)

트리란? 뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조. 트리는 비선형 구조다. 비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있다. 선형구조와 비선형구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 많다. 선형구조는 자료를 저장하고 꺼내는데에 초점이 맞춰져있고 비선형구조는 표현에 초점이 맞춰져 있다. 아래 폴더 구조가 대표적인 트리의 형태다 트리의 용어 Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 상위 레벨에 연결된 노드 Child Node: 어떤 노드의 하..

1. 알고리즘 공부 배열, 리스트 (파이썬 네이티브 코드로 구현하기)

1. Array (배열) 배열은 크기가 정해진 데이터의 공간. 한 번 정해지면 바꿀 수 없다. 배열은 각 원소에 즉시 접근할 수 있다. 여기서, 원소의 순서는 0부터 시작하고 이를 인덱스라 부른다. 배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 한다. 원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조. 2. Linked List(링크드 리스트) 혹은 리스트(List) 리스트는 크기가 정해지지 않은 데이터의 공간 리스트는 특정 원소에 접근하려면 오래 걸린다. 리스트는 원소를 중간에 삽입/삭제 하기 위해서 앞 뒤의 포인터만 변경하면 된다. 즉 원소 삽입/삭제가 간단하다. 배열과 리스트의 차이 배열 : 배열의 끝에서만 추가/삭제 연산을 하거나 추가/삭제 연산이 없..

백준 1927번 <파이썬> (힙에 대해 공부하기)

1. 힙이란 무엇인가 힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. A가 B의 부모 노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한다 최소 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 이러한 속성으로 인해 힙에서는 가장 낮거나 혹은 가장 높은 우선순위를 가지는 노드가 항상 루트에 오게 되고 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. import heapq heap = [] heapq.heappush(heap, 50) heapq.heappush(heap, 10) heapq.heappush(heap, 20) heap..

스프링 배팅시스템 만들기 (트위치 배팅시스템 참고)

지금 실전프로젝트에서 만드는 기능중에 트위치 배팅시스템처럼 유저가 참가해서 자신의 포인트를 걸고 배팅을 해서 배팅을 이기면 자기가 건 포인트에 비례하여 포인트를 더 얻고 만약 배팅에서 지면 자신의 포인트가 모두 사라지는 기능을 구현하기로 했다. 엔티티 설계는 다음과 같이 진행했다. ChatRoom은 유저가 참여하고있는 채팅 방이다. Vote는 채팅방과 OneToOne으로 채팅방 생성시 자동으로 그 방에 해당하는 Vote가 생긴다. 이 Vote에는 각각 유저가 투표한곳의 카운트 수와 누가 제일 많이 투표했는지, 그리고 각각 투표한곳의 totalPoint가 칼럼으로 존재한다 SaveVote는 Vote와 ManyToOne, ChatRoom과 ManyToOne, 유저와 ManyToOne으로 연결되어 있어 Cha..