Daim's blog

Python으로 구현하는 자료구조 : Queue (1) Queue

이번 포스팅에서는 자료구조 큐(Queue)에 대한 특징을 살펴보고 파이썬으로 큐에 원소를 삽입, 삭제, 조회하는 코드를 짜보도록 하겠습니다. # Queue란? 큐란 목록 한쪽 끝에서만 자료를 넣고 다른 한쪽 긑에서만 자료를 빼낼 수 있는 자료구조 입니다. 먼저 집어넣은 데이터가 먼저 나오는 (FIFO : First in, First out) 구조로 데이터를 저장합니다. 데이터가 입력한 순서대로 처리되어야 할 경우에 사용합니다. 큐에 새로운 데이터가 들어오면 큐의 끝에 데이터가 추가되며(enqueue), 반대로 삭제될 때는 첫번째 위치의 데이터가 삭제됩니다(dequeue). # Queue의 종류는? 선형큐, 환형큐, 우선순위큐가 있습니다. 여기서는 기본적인 큐의 형태만 살펴보고 그 외의 큐는 다른 포스팅에..

Data structure 2019. 5. 12. 09:30

Python으로 구현하는 자료구조 : Heap

Python으로 Heap을 구현해보고 Heap 자료구조의 특징과 데이터의 삽입과 삭제에 대해 알아보도록 하겠습니다. # Heap이란 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조입니다. 힙에는 두가지 종류가 있으며, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙을 '최대 힙', 부모노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙을 '최소 힙'이라고 부릅니다. 원소 값의 대소 관계는 오로지 부모 노드와 자식 노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않습니다. 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리 노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적..

Data structure 2019. 5. 11. 09:00

Python으로 구현하는 자료구조 : Linked List (3) Circular linked list

이 포스팅에서는 Circular linked list의 특징을 알아보고 파이썬으로 Circular linked list의 삽입, 삭제, 조회를 구현해보도록 하겠습니다. # Circular linked list란 환형 연결 리스트라고도 부르는 이 연결 리스트는 머리와 꼬리가 연결되어 순환 구조를 지닙니다. 환형 연결 리스트라는 것은 Node에 포인터 공간이 두 개 일수도 있고, 한개 일수도 있으며 포인터 공간의 개수가 중요한 것이 아니라 노드의 Next가 None인 경우가 없이 끊임 없이 이어진다는 의미입니다. 따라서 노드가 한개인 경우에도 무한대로 순환할 수 있습니다. # Circular linked list 구현하기 # 삽입 # 삭제 # 파이썬 코드 1 2 3 4 5 6 7 8 9 10 11 12 13..

Data structure 2019. 5. 10. 09:30

Python으로 구현하는 자료구조 : Linked List (2) Doubly linked list

이 포스팅에서는 Doubly linked list의 특징을 알아보고 파이썬으로 Doubly linked list의 삽입, 삭제, 조회를 구현해보도록 하겠습니다. # Doubly linked list 란? Doubly linked list는 각 노드에 자료 공간과 두 개의 포인터 공간이 있고, 각 노드의 포인터는 이전 노드와 다음 노드를 가리킵니다. # 이중 연결 리스트의 특징, 장점, 단점은요 단순 연결리스트와 이중 연결 리스트의 차이는 prev를 가리키는 포인터 공간이 추가되면서 이전 노드에 대한 정보를 알 수 있다는 점입니다. 이로인해 단순 연결 리스트로는 할 수 없는 역으로 출력하는 것이 가능하고, 특정 노드의 이전 노드를 삭제하거나 특정 노드의 이전에 삽입하는게 가능해졌습니다. 그러나 단순 연결 ..

Data structure 2019. 5. 9. 19:00

Python으로 푸는 프로그래머스 오픈채팅방((2018년)KAKAO BLIND RECRUITMENT)

오픈 채팅방 카카오 블라인드 채용에 나왔던 문제이다. 오픈 채팅방에 들어오는 사람들은 각각 고유 번호가 부여되며 닉네임은 여러 명이 중복해서 사용할 수 있다. 닉네임을 변경하기 위해서는 채팅방을 나갔다가 다시 들어오거나, change 명령어로 변경하면 된다. 닉네임이 변경되면 기존에 남겨진 메시지에서도 변경된 닉네임으로 표시되도록 해야 한다. 채팅방의 사람들이 어떻게 동작했는지에 대한 정보가 주어졌을 때, 모든 동작이 완료되었을 경우 메시지가 어떻게 표시되고 있는지 반환할 수 있도록 코드를 짜시오. 프로그래머스에서 문제 보기 Github에서 코드 보기 문제 풀이 채팅방에 입장하는 사람들의 고유 Id를 Key로 하고 이름을 Value로 하는 Dictionary를 선언한다. 메시지에 보여질 행동은 'Leav..

온라인 코딩 테스트 문제 풀이/프로그래머스 문제 풀이 2019. 5. 8. 16:00

Python으로 푸는 LeetCode 599. Minimum Index Sum of Two Lists (Easy)

LeetCode 599. Minimum Index Sum of Two Lists 주어진 두 리스트의 공통 부분을 찾아서 각각의 리스트에서 위치한 Index의 값의 합이 최소인 결과값을 리스트로 반환하시오. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 Github에서 코드 보기 문제 풀이 이 문제는 Hash Table로 문제를 풀 경우에 쉽게 풀 수 있다. 주어진 두 리스트 중 하나를 기준으로 잡은 다음, 리스트의 원소와 index를 Key, Value로 하는 hash table을 구성한다. (파이썬에서는 dictionary 컨테이너를 활용한다) 두번째 리스트를 순회하면서 dictionary에 해당 원소를 key로 하는 값이 있는지 확인하고, 있다면 value와 현재 원소의 in..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 5. 7. 22:30

Python으로 푸는 LeetCode 917. Reverse Only Letters (Easy)

알파벳이 아닌 문자(-,!,? 등등)를 제외한 알파벳 문자를 뒤집어서 반환하는 코드를 짜시오. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 Github에서 코드 보기 문제 풀이 문제를 푸는 방법은 다양하다. 처음 풀었던 방식은 문자열의 맨앞(start_index)와 맨뒤(last_index)의 index를 하나하나 확인하면서 앞뒤 모두 알파벳 문자열인 경우에만 두 자리를 바꿔주는 방법이다. 방법 1. 포인터를 이동하며 문자열 교환 만약 알파벳이 아니라면 index를 낮추거나 높여서 가리키고 있는 index를 문자열의 가운데로 점점 이동하며 문자열을 바꿔준다. start_index와 last_index가 서로 만나면 문자열 교환을 중지하고 str()으로 변환하여 결과값을 반환한다..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 5. 6. 23:40

Python으로 푸는 백준 10799. 쇠막대기

괄호로 표현된 쇠막대기와 레이저가 있다. 긴 쇠막대기 위에 작은 쇠막대기를 층별로 쌓았을 때, 레이저를 수직으로 쏘게되면 몇개의 쇠막대기 조각이 나오는지 알아보는 프로그램을 짜시오. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 github에서 코드 보기 문제 풀이 문자열을 순회하면서 어디서부터 레이저이고, 막대기의 시작과 끝인지를 구분할 수 있어야 한다. '(' 의 뒤가 ')'이면 레이저이다. '('의 뒤가 '('이면 막대기의 시작이다. ')'의 앞이 ')'이면 막대기의 끝이다. 레이저를 발견하면 아직 끝이 닫히지 않은 막대기들은 레이저에 영향을 받아 쪼개질 수 있다. 막대기가 레이저 1개의 영향을 받으면 2개로 쪼개진다. 막대기가 레이저 2개의 영향을 받으면 3개로 쪼개진다. 즉, 레이저 N개의 ..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 5. 5. 21:30

Python으로 푸는 LeetCode. 942. DI String Match (Easy)

문제의 조건에 따라 완성한 list를 반환한다. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 github에서 코드 보기 문제 조건 인자값으로 "I"와 "D"로만 구성된 문자열 S를 받는다. N은 S의 길이 값이다. 반환해야 하는 결과값인 리스트 A는 0~N까지의 구성된 원소들로 구성되어 있다. 단, 그 원소들의 순서는 다음과 같은 조건으로 정해진다. 문자열 S의 문자열이 "I"(Increase)이고 그 Index가 1이면 Index 1번째의 리스트 A의 원소는 그 다음번에 나타날 원소들 보다 가장 작아야 한다. 문자열 S의 문자열이 "D"이고 그 Index가 2이면 Index 2번째 리스트 A의 원소는 그 다음버넹 나타날 원소들보다 가장 커야 한다. 문제 풀이 이미 주어진 조건..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 5. 4. 19:00

Python으로 푸는 LeetCode 804. Unique Morse Code Words (Easy)

List의 원소인 단어들이 Morse Code로 바꾸었을 때, 중복되지 않은 모스 코드의 수를 반환하는 프로그램을 짜시오. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 github에서 코드 보기 문제 조건 알파벳 26자에 대응되는 Morse Code가 주어진다. Morse Code에는 각 알파벳에 대응되는 Morse Code가 중복되기도 한다. 문제 풀이 주어진 Morse Code가 어떤 알파벳을 뜻하는지 정의해두기 위해서 파이썬의 dict()에 알파벳을 Key로 하고 모스 부호를 value로 하는 딕셔너리를 만들었다. 알파벳을 순회하여 출력하기 위하여 해당 문자의 아스키 코드 값을 알 수 있는 ord() 메소드를 활용하였다. 알파벳 'a'와 'z'의 아스키 코드 값이 97과 ..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 5. 3. 21:00

Python으로 푸는 LeetCode 929. Unique Email Addresses (Easy)

문제의 조건에 따라 완성한 list를 반환한다. LeetCode에서 푼 문제 리스트 보기 LeetCode에서 문제 보기 github에서 코드 보기 문제 조건 이메일은 @를 기준으로 다음과 같이 구성되어 있다. (local name@domain names) local name 부분에서 '.'이 나올 경우 '.'이 없는 것처럼 취급한다. local name 부분에서 '+'가 나올 경우 '+' 이하의 local name 부분은 없는 것처럼 취급한다. 문제 풀이 여러 이메일 주소가 담긴 List가 주어지고, 이 이메일들을 순회하면서 조건에 따라서 local name 부분을 수정한다. 이때 정정된 이메일 주소는 set()에 담아 중복을 제거한다. List의 모든 이메일 주소를 수정하였을 때 set()에 담긴 이메..

온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 5. 2. 17:00

Python으로 푸는 백준 2309. 일곱 난쟁이

백준 2309. 일곱 난쟁이 백설공주와 일곱난쟁이가 함께 살고 있었다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉명이 돌아왔다. 일곱 난쟁이의 키의 총 합은 100이다. 진짜 난쟁이를 골라내어 오름차순으로 키를 출력하는 프로그램을 짜시오. 백준에서 푼 문제 리스트 보기 백준에서 문제 보기 Github에서 코드 보기 문제 조건 입곱 난쟁이들의 키는 서로 달라야 한다. 입곱 난쟁이의 키는 100을 넘지 않는다. 일곱 난쟁이의 키를 오름차순으로 출력해야 한다. 일곱 난쟁이를 찾을 수 없는 경우는 없으며, 여러 가지 경우가 가능하다면 하나의 경우의 수만 출력한다. 문제 풀이 나는 itertools의 combinations(조합)으로 문제를 풀었다. 입력되는 난쟁이의 키는 9가지이고, 그 가운데 7가지를..

온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 5. 1. 09:00