분류 전체보기243
[프로그래머스💯] 코딩테스트 연습 > 탐욕법(Greedy) > 체육복
해답) def solution(n, lost, reserve): # 그리디한 알고리즘 이므로 소트를 해줘야한다. reserve.sort() # 여벌이 있는 친구가 도난당한 경우 for i in reserve: if i in lost: lost.remove(i) reserve[reserve.index(i)] = -5 # 체육복을 빌려주는 경우 for i in reserve: if i-1 in lost: lost.remove(i-1) elif i+1 in lost: lost.remove(i+1) return n-len(lost) * 알고리즘 순서 여벌이 있는 친구들을 기준으로 (정렬이 되어있음을 가정) 빌려줄수있는 앞번호 부터 쭈욱 빌려준다. 1. 자신이 잃어버린경우 2. 자신의 앞번호가 잃어버린 경우 3...
[프로그래머스💯] 코딩테스트 연습 > 탐욕법(Greedy) > 조이스틱
해답) def solution(st): res = 0 A_Count =0 A_Max = 0 # 가장 긴 A묶음의 A 수 A_StartIndex = 0 A_EndIndex = 0 vertical_count = 0 start = True for i,v in enumerate(st): # 연속해서 나온 A 횟수 검사 if v == 'A' and start == False : A_Count += 1 if A_Count > A_Max: A_Max = A_Count A_EndIndex = i else: A_Count = 0 # 알파벳이 N보다 크면 위로넘기는게 빠르다 if ord(v) > ord('N'): count = ord('Z')-ord(v)+1 else: count = ord(v) - ord('A') res..
[알고리즘] MST / Disjoint set / 크루스칼 알고리즘
MST 알고리즘크루스칼과 프림 알고리즘은 MST 를 구하는 알고리즘 의 2종류이며, 그리디 알고리즘을 이용한다. MST 와 그리디 알고리즘의 정보는 : https://programming119.tistory.com/78 크루스칼 알고리즘 나무와 숲 -> 크루스칼 알고리즘은 각각의 노드를 나무로 생각하고, 모든 노드의 집합을 숲 이라고 생각한다. 숲에 나무들이 많다. 이 숲은 마법의 숲이라 나무끼리 손을 잡는다. 나무들끼리는 손을 잡을 수 있을 수도 있고, 나무들끼리 손을 잡으려면 마력을 소비하고 각각 나무들끼리 몇의 마력이 드는지는 정해져 있다. 예시) A 와 B 나무는 손을 잡을 때 3의 마력이 들고 , A와 C는 손을 잡을 때 10의 마력이 들고, B와 C는 손을 못 잡는다. 나무 : 노드 숲 : 노..
[알고리즘] Minimal Spanning Tree 와 그리디 알고리즘
그리디 알고리즘 해결 방식으로 MST(Minimal Spanning Tree) 를 구해낼 수 있다. Minimal Spanning Tree(최소신장트리) 란? 한국말로하면 최소신장트리 로 그래프를 연결하는 가장 최적의 트리라 생각하면 된다. 모든 정점들을 포함해야하며, 사이클을 포함하면 안된다.(공간을 만들면 안됨) 가장 중요한 것은, 모든 간선의 가중치가 최소가 되는 트리를 Minimal Spanning Tree 라고 한다. 안전한 엣지(Safe edge)란? 안전한 엣지란, 우리가 MST를 구하는 과정에서, 현재 선택할 수 있는 엣지를 뜻한다. 예를들어 우리가 MST 를 구하고 있는 중인 어떤 상황일 때, A 엣지를 선택해서 MST를 만드는 경우도 있고 B 엣지를 선택해서 MST를 만들 수 있지만, ..
[DB] 비트리와 비트맵 인덱스의 장단점
키의 갱신 비용 B-Tree 인덱스구조 : 데이터를 삽입, 삭제할 때 키를 알맞는 곳에 끼워 넣어주면 되기 때문에 비교적 간편하다. Bitmap 인덱스구조 : 모든 비트맵 인덱스들에 갱신작업을 해주어야 하므로 힘들다. 사용하기 좋은곳 B-Tree 인덱스구조 : 컬럼의 값 종류가 다양한 곳에 좋다. Bitmap 인덱스구조 : 컬럼의 값 종류가 적은 곳에 좋다. ( Ex. 성별 : 남/여 , 국가 : 국민 / 외국인 ) - 값 종류가 다양해지면 그에 따른 bitmap 이 무수히 늘어나게된다. 다중 쿼리문 B-Tree 인덱스구조 : 다양한 컬럼이 이용되는 쿼리문에는 비효율적이다. Bitmap 인덱스구조 : 다양한 컬럼이 이용되는 쿼리문에 좋다. - 그저 비트맵끼리 OR / AND 이런거 해버리면 되기 때문이다.
[알고리즘] 허프만 코드와 그리디 알고리즘 / Huffman code and greedy algorithm
문자열의 코드화 우리가 인터넷 상에서 쓰는 한글, abcd 알파벳. 컴퓨터는 우리처럼 글자 자체로 보지 않고, 결국 2진수 0과 1의 모음으로 이해를 한다! a는 01 로 약속, b는 10 으로 약속하면 ab라는 문자는 컴퓨터 내에 0110 으로 저장이되고 100110 이란 코드를 받아들이면 컴퓨터는 아, 이것은 bab 이구나 로 해석하는 것이다. 우리가 쓰는 문자를 컴퓨터 내에 저장한다고 할 때, 이 약속된 코드의 비트수가 적을 수록 (010101 이런게 짧을수록) 메모리적으로 이득일 것이다! 그렇다면 어떻게하면 문자열을 효율적으로 코드화를 할 수 있을까? Fixed-length codeword / Variable-length codeword abcdef 를 코드화하여 2진법으로 표현할때에는 아래와 같..