코딩하는 해커

[Data Structure] 배열로 구현된 리스트 테스트

배열로 구현된 리스트 테스트 https://pythontutor.com/render.html#mode=display array = [None] * 10 size = 0 def isEmpty(): if size == 0: return True else : return False def isFull(): return size == 10 def insert(pos, e): global size if not isFull() and 0

[Data Structure] 스택(Stack) / 큐(Queue)

스택(Stack) / 큐(Queue) 스택과 큐는 모두 데이터를 임시 저장할 때 사용하는 자료구조이다. 깃허브 스택: https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/%5BData%20Structure%5D%20Stack.ipynb 큐: https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/%5BData%20Structure%5D%20Queue.ipynb 스택(Stack) 먼저, 스택은 가장 마지막에 들어온 값이 가장 먼저 나가는 후입선출(LIFO: Last In First Out) 구조로서 예로는 함수의 호출과 반환하는 과정이 있다. 예시로는 프링글스를 생각해보자. 스택에 데이터..

[Algorithms] 그리디 - 1이 될 때까지

본 문제는 '(나동빈) 이것이 코딩 테스트다 with 파이썬, p.96'의 내용이다. 실전 문제 - 1이 될 때까지 난이도: 하 | 시간 제한: 1초 | 메모리 제한: 128M | 기출: 2018 E 기업 알고리즘 대회 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. N에서 1을 뺀다. N을 K로 나눈다. 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 ..

[Algorithms] 그리디 - 숫자 카드 게임

본 문제는 '(나동빈) 이것이 코딩 테스트다 with 파이썬, p.96'의 내용이다. 실전 문제 - 숫자 카드 게임 난이도: 하 | 시간 제한: 1초 | 메모리 제한: 128M | 기출: 2019 국가 교육기관 코딩테스트 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 ..

[Algorithms] 탐욕법(Greedy)

탐욕법(Greedy)탐욕법(greedy): 그리디는 단순하지만 강력한 알고리즘이다. 탐욕법이라는 이름에서 알 수 있듯이 어떠한 문제가 있을 때 탐욕적으로 문제를 해결하는 알고리즘이다. 이때, '탐욕적'이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 이러한 탐욕법 유형은 사전에 외우고 있지 않아도 풀 수 있을 가능성이 매우 높으며 문제를 풀기 위한 최소한의 창의력만 있으면 해결이 가능하다. 그리디 알고리즘은 기준에 따라서 최적의 방법을 선택하는 알고리즘이므로 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디와 정렬 알고리즘은 자주 짝을 이뤄 출제된다. 이제 기본적인 문제 유형을 알..

[Algorithms] 셰이커 정렬(Shaker Sort)

깃 허브: https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/Sorting%20algorithm.ipynb GitHub - PSLeon24/DataStructure-Algorithms: Do it! 자료구조와 함께 배우는 알고리즘 입문(Python) Do it! 자료구조와 함께 배우는 알고리즘 입문(Python). Contribute to PSLeon24/DataStructure-Algorithms development by creating an account on GitHub. github.com 셰이커 정렬(Shaker Sort) 셰이커 정렬을 버블 정렬의 변형된 정렬 알고리즘 중 하나이다. 예를 들어, [9, 1, 3, 4, 6, 7, ..

[Data Structure] 원형 이중 연결 리스트(Circular Doubly Linked List)

Add 부분 손 로직 전체 구조가 너무 복잡하므로 기본적으로 아래의 구조적 특징은 외우는 것이 편하리라 판단된다. head가 가리키는 dummy 노드의 prev는 항상 꼬리 노드(마지막 노드)를 가리킨다. head가 가리키는 dummy 노드의 next는 항상 더미노드를 제외한 머리 노드(시작 노드)를 가리킨다. 더미 노드가 아닌 머리 노드의 prev는 더미 노드를 가리키고, next는 다음 노드를 가리킨다. 꼬리 노드(마지막 노드)의 prev는 이전 노드를 가리키고 next는 더미 노드를 가리킨다. 파이썬 구현 https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/Circular_Doubly_Linked_List.py GitHub - PSLeon..

[Algorithms] 4퀸 문제 및 8퀸 문제 (4-Queen problem & 8-Queen problem)

4퀸 문제 및 8퀸 문제 (4-Queen problem & 8-Queen problem) 4퀸 문제(4-Queen problem) 및 8퀸 문제(8-Queen problem)는 재귀 알고리즘을 설명할 때 자주 나오는 예제로 흔히 n-Queen으로 알려진 문제이다. 간단하게 살펴보면, n개의 퀸이 서로 공격하여 잡을 수 없도록 n x n 체스판에 배치하는 것이다. 이때, 퀸은 자신과 같은 열, 행, 대각선에 위치한 다른 퀸을 공격할 수 있다. 예를 들어 4퀸 문제를 해결하고자 할 때, 체스판은 총 16칸(4*4)이 된다. 이때 첫 번째 퀸의 경우 아무 곳이나 배치할 수 있으므로 16가지, 그 다음 퀸을 배치하는 것은 15가지, ... 이런식으로 총 16*15*14*13 = 43680가지의 수가 만들어지는데..

[Algorithms] KMP 문자열 검색 알고리즘(Knuth-Morris-Pratt Algorithm)

깃허브: https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/KMP_Algorithm.ipynb KMP 문자열 검색 알고리즘(Knuth-Morris-Pratt Algorithm) 문자열 검색의 가장 기초가 되는 알고리즘이 지난 포스팅에서 학습한 브루트 포스법(https://psleon.tistory.com/53)이었다. 하지만 브루트 포스법의 경우, 검색하고자 하는 패턴과 검색 대상인 텍스트가 동일한지 검사하는 과정에서 만약 하나라도 일치하지 않는 경우 이미 검사한 위치를 기억하지 못해 현재 검색하고 있는 텍스트의 첫 문자의 바로 다음 텍스트 문자부터 검색하게 되어 시간 복잡도가 O(n·m)가 되는 비효율적인 알고리즘이라고 설명하였다. 따라서 ..

[Algorithms] 하노이의 탑(Tower of Hanoi)

깃허브: https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/hanoi.ipynb 하노이의 탑(Tower of Hanoi) 하노이의 탑(Tower of Hanoi)는 위 그림과 같이 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원반들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원반들이 위에 순서대로 쌓여 있다. 그리고 이동 시킬 때 아래의 두 가지 조건을 만족시키면서 이동 시켜야 한다. 1) 한 번에 하나의 원반만을 옮길 수 있다. 2) 큰 원반이 작은 원반 위에 있어서는 안된다. 이러한 하노이의 탑을 해결하는 데 있어서 가장 기초적인 아이디어는 재귀(recursion)이다. 먼저 예를 통해 어떻게 풀어야 할지 감을 잡아보자. 1. ..