[프로그래머스💯] 코딩테스트 연습 > 탐욕법(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..
2019. 11. 24.
[알고리즘] Minimal Spanning Tree 와 그리디 알고리즘
그리디 알고리즘 해결 방식으로 MST(Minimal Spanning Tree) 를 구해낼 수 있다. Minimal Spanning Tree(최소신장트리) 란? 한국말로하면 최소신장트리 로 그래프를 연결하는 가장 최적의 트리라 생각하면 된다. 모든 정점들을 포함해야하며, 사이클을 포함하면 안된다.(공간을 만들면 안됨) 가장 중요한 것은, 모든 간선의 가중치가 최소가 되는 트리를 Minimal Spanning Tree 라고 한다. 안전한 엣지(Safe edge)란? 안전한 엣지란, 우리가 MST를 구하는 과정에서, 현재 선택할 수 있는 엣지를 뜻한다. 예를들어 우리가 MST 를 구하고 있는 중인 어떤 상황일 때, A 엣지를 선택해서 MST를 만드는 경우도 있고 B 엣지를 선택해서 MST를 만들 수 있지만, ..
2019. 11. 19.
[알고리즘] 허프만 코드와 그리디 알고리즘 / 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진법으로 표현할때에는 아래와 같..
2019. 11. 14.
[알고리즘] Greedy Algorithm 이란?
왜 Greedy일까? // Greedy = 욕심부리는, 탐욕스러운 // 필자는 Greedy 가 전체 문제에 대해 생각하기 귀찮고, 게으르기 때문에 현재 상황에 대한 답만을 구해서 최종 결과를 도출하는 알고리즘 이라고 생각하고 암기하고 있다 (현재만 생각하는 욕심을 부린다는 의미이다.) 그리디 알고리즘은 현재 놓여진 상태에서의 최적의 답만을 찾는다. Locally 한 최적의 답만을 찾기 때문에 항상 Global Solution (전체문제의 답) 을 찾아준다고 확신할 수는 없다. 하지만, 우리는 현재 상황만 생각하면 되기 때문에 속도면에서는 빠르게 해결 할 수 있다. 예제) 위 그래프에서 goal까지의 최저비용 거리를 구해보자. 1) start 에서 출발. start 에서 가장 낮은 비용은 b 로 가는 3 ..
2019. 11. 7.
[프로그래머스💯] 코딩테스트 연습 > 탐욕법(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..
[알고리즘] Minimal Spanning Tree 와 그리디 알고리즘
그리디 알고리즘 해결 방식으로 MST(Minimal Spanning Tree) 를 구해낼 수 있다. Minimal Spanning Tree(최소신장트리) 란? 한국말로하면 최소신장트리 로 그래프를 연결하는 가장 최적의 트리라 생각하면 된다. 모든 정점들을 포함해야하며, 사이클을 포함하면 안된다.(공간을 만들면 안됨) 가장 중요한 것은, 모든 간선의 가중치가 최소가 되는 트리를 Minimal Spanning Tree 라고 한다. 안전한 엣지(Safe edge)란? 안전한 엣지란, 우리가 MST를 구하는 과정에서, 현재 선택할 수 있는 엣지를 뜻한다. 예를들어 우리가 MST 를 구하고 있는 중인 어떤 상황일 때, A 엣지를 선택해서 MST를 만드는 경우도 있고 B 엣지를 선택해서 MST를 만들 수 있지만, ..
[알고리즘] 허프만 코드와 그리디 알고리즘 / 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진법으로 표현할때에는 아래와 같..
[알고리즘] Greedy Algorithm 이란?
왜 Greedy일까? // Greedy = 욕심부리는, 탐욕스러운 // 필자는 Greedy 가 전체 문제에 대해 생각하기 귀찮고, 게으르기 때문에 현재 상황에 대한 답만을 구해서 최종 결과를 도출하는 알고리즘 이라고 생각하고 암기하고 있다 (현재만 생각하는 욕심을 부린다는 의미이다.) 그리디 알고리즘은 현재 놓여진 상태에서의 최적의 답만을 찾는다. Locally 한 최적의 답만을 찾기 때문에 항상 Global Solution (전체문제의 답) 을 찾아준다고 확신할 수는 없다. 하지만, 우리는 현재 상황만 생각하면 되기 때문에 속도면에서는 빠르게 해결 할 수 있다. 예제) 위 그래프에서 goal까지의 최저비용 거리를 구해보자. 1) start 에서 출발. start 에서 가장 낮은 비용은 b 로 가는 3 ..