![]()
모듈로 연산? 모듈로 연산은 어떠한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로 나머지 연산(mod)라고 한다(프로그래밍 언어에서 %연산자를 의미한ㄷ.). 정수론에서 모듈로 연산이라는것이 있는데, 이는 정수의 합과 곱을 어떤 주어진 수의 나머지에 대해 정의하는 방법이다. 모듈로 연산은 아래 세가지를 충족시킨다고 한다. 나머지는 이 공식에 부합하지 않는다고 한다. (A + B) % C = ((A % C) + (B % C)) % C (A - B) % C = ((A % C) - (B % C)) % C (A * B) % C = ((A % C) * (B % C)) % C 유도해보기 A,B를 각각 위와 같이 정의하고 유도해보면 아래와 같다. 이 원리를 이용해 풀었던 문제이다. https://www.acmicp..
![]()
동적 계획법이란? 동적계획법은 Dynamic Programming, DP라고도 불린다. 동적계획법은 하나의 문제를 "단 한번만" 푸는 문제이다. 분할정복과 비슷한 성격을 띄고있다. 단 다른 점이라면, 분할정복같은 경우에는 동일한 문제를 여러번 푼다는 점에 있어서 동적계획법과 차이가 있다. 동적계획법을 사용하는데에 있어 아래 두가지 조건을 만족해야한다. 큰 문제를 작은 문제로 나눌 수 있어야 한다 작은 문제에서 구한 정답이 큰 문제에서도 동일한 정답으로 적용해야한다. 동적계획법은 메모이제이션(Memoization)기법을 사용하면서 값을 구하게 된다. 메모이제이션이란, 이미 구한 답을 잠시 배열에 기록해두고, 나중에 동일한 연산을 할 때 사용한다는 기법이다. 분할정복에서의 비효율성 분할정복법의 비효율성은 대..
![]()
재귀란? 재귀란 자기 자신을 재참조하는 형태의 알고리즘을 의미한다. 재귀의 장점 1. 피보나치수열, 팩토리얼과 같이 재귀적 표현이 자연스러운 해결에 대해서는 도움이 된다.(가독성) 2. 함수를 단순하게 만들어 준다 3. 변수사용을 줄여준다. 재귀의 단점 1. 메모리를 많이 차지하며 성능이 반복문에 비해 느리다.(함수 스택 call이 반복적으로 이루어지므로) 2. StackOverflow가능성이 크다 3. CPU 크래쉬를 발생시키기도 한다. 재귀의 대표적인 예시들 - Factorial def factorial(n : int) -> int: if n > 0: return n * factorial(n - 1) else: return 1 if __name__ == "__main__": n = int(input(..
![]()
Queue란? 큐는 스택과 동일하게 데이터를 임시 보관하는 자료구조이다. 다만 스택과 달리 선입선출(FIFO, First In Frist Out)구조를 가지고 있다. 큐에서 가지는 기본적인 작업은 아래 두개가 있습니다 인큐(Enqueue) : 데이터를 추가하는 작업 디큐(Dequeue) : 데이터를 빼내는 작업 그리고 스택의 구조에 쓰이는 용어도 두가지가 있습니다. 프런트(Front) : 데이터를 꺼내는 쪽 리어(Rear) : 데이터를 빼내는 쪽 Ring Buffer로 원형 큐 구현하기 일반적으로 배열형태로 큐를 구현하게 되면, 만약 디큐를 하게 되면 그 뒤 원소들을 모두 앞쪽으로 땡겨주어야합니다. 이 작업에서는 시간복잡도 O(n)이 추가적으로 들어가게 됩니다.디큐의 시간복잡도가 O(1)인데 이 작업으로..
![]()
스택(Stack이란?) 스택은 데이터를 임시저장할때 사용하는 자료구조이다. 기본적으로 후입선출(LIFO,Last In First Out)방식이다. 스택의 동작은 두가지가 있다 푸시(Push) : 데이터를 넣는 작업이다. 팝(Pop) : 데이터를 꺼내는 작업이다. 그리고 푸시, 팝을 하는 윗부분을 top, 아랫부분을 bottom이라고 한다. 스택 구현하기 스택을 구현해 보자. 우선 기본적으로 Fixed-Stack으로 구현해 보자. 스택을 구현하는데 있어 기본적으로 아래 세가지가 필요로 하다 스택배열 : stk - 데이터를 저장하는 본체이다 스택크기 : capactiy - 스택의 최대 크기를 나타내는 정수이다 스택포인터 : ptr - 스택에 쌓여있는 데이터 개수를 나타내는 정수값이다. 비어있으면 0, 차있으..
![]()
버블 정렬은 이웃한 두 원소의 관계를 비교해, 필요에 따라 교환을 반복하는 알고리즘입니다.버블정렬은 '단순 교환 정렬' 이라고 부르기도 합니다. 우선 버블 정렬의 교환 방식을 그림으로 살펴보겠습니다 버블정렬은 기본적으로 이웃된 원소들간의 비교, 교환이 일어나기 때문에, 안정적인 정렬이라고 할 수 있습니다. 이제 한번 그림을 같이 보겠습니다.총 길이 6인 리스트가 있습니다. 이 리스트에서 한번의 정렬을 위해서 (총 길이) - 1번만큼의 비교, 교환이 이루어 지는것을 볼 수 있습니다. 그리고 참고로 버블 정렬에서 일어나는 비교,교환 과정을 '패스'라고 부릅니다. 자 그럼 일단 코드를 작성해 봅시다. 우선 총 길이에 대해 -1 번만큼 교환이 일어난다고 했죠? 아래와 같이 작성해 줍니다. from typing ..
![]()
프로그래머스 문제를 풀었다. https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 결론적으로 내가 작성한 코드는 아래와 같다 from typing import Any, Sequence from collections import deque from random import randint class PriorityPrint(object): def __init__(self,seq,location): self.location..
![]()
1. 유클리드 호제법이란? -> 유클리드 호제법이란 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 여기서 '호제법' 이란 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 의미한다. 예를 들어 a > b라고 할때 a를 b로 나눈 나머지를 r이라고 하면 b와 r의 최대공약수는 a와 b의 최대 공약수와 같다. 15와 6 라고 가정을하면 나머지는 3이된다 15와 6의 최대 공약수는 3, 6과 3의 최대공약수는 3이된다. 다시 b와 r을 나는 나머지인 r'이라고 하면 b와 r의 최대 공약수는 r r'의 최대 공약수와 같아진다(6,3 과 3,0 -> GCD : 3) 결론적으로 맨 마지막에 나오는 r r'의 나누기 나머지가 0이 될때 a와 b의 최대공약수가 나오는 것이다. 2. 관련 문제 UR..
![]()
이진검색(Binary Search)에 대해 알아보자. 이진검색 또한 검색 기법중 하나이다. 단 전제조건이 하나가 존재한다. 이진검색을 사용하기 위해서는 해당 배열의 데이터가 정렬(sort)되어있어야 한다. * 결론적으로 이진검색인 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있도록 도와주는 알고리즘이라는 것이다. 예시를 하나 들어 [5,7,15,28,29,31,39,58,68,70,95] 라는 리스트가 있고, 나는 여기서 39라는 값을 검색하고 싶다고 가정하자. 가정하자. 우선 검색 범위의 시작 인덱스를 pl, 끝 인덱스를 pr, 중간 인덱스를 pc라고 부르기로 약속하자. 과정에 대한 사진은 다음과 같다. 1) 우선 초기 검색범위는 당연히 처음(index 0)부터 끝(index ..
![]()
선형 검색 알고리즘(Linear Search Algorithm)에서 종료조건은 두가지가 존재한다. 1) 검색할 값을 찾지 못하고 배열의 맨 끝을 지나갔는가? -> 검색실패조건 2) 검색할 값과 같은 원소를 찾았는가? -> 검색 성공 조건 종료를 위해 이 두가지를 항상 검색하는데, 이 과정을 계속해서 반복하다 보면 종료조건을 검사하는 '비용(cost)'를 무시할 수 없다. 우선 기본적으로 검색 대상인 sequence가 있다면 그 sequence 맨 끝에는 검색하고자 하는 key값을 넣어준다. 여기서 sequence맨 끝에 넣어주는 이 검색하려는 key값을 '보초'라고 한다. 만약 원래 seqeunce에 자신이 찾으려는 key값이 존재하지 않는다면, 스캔 인덱스는 원래 sequence의 길이와 동일해 질 것..
![]()
코드 링크는 아래에 있습니다(queue.ipynb) https://github.com/J-hoplin1/Python-DataStructure/blob/master/Queue.ipynb 큐(Queue)란 스택과 달리 항목이 들어온 순서대로 접근이 가능한 FIFO(First In First Out, 선입선출)구조이다. 큐 또한 배열 인덱싱을 통한 접근이 불가능하다. 가장 쉽게 생각하면 우리가 줄서는 것을 생각해보면 된다. 큐 또한 스택과 동일하게 다양한 동작들이 있으며 이 또한 O(1)의 시간복잡도를 가지게 된다. - enqueue : 큐 뒤쪽에 항목을 삽입한다. - dequeue : 큐 앞쪽의 항목을 반환 후 제거 - peek : 큐의 앞쪽 항목 조회 - empty : 큐가 비었는지에 대해 확인 - siz..
![]()
파이썬에서 만약 배열 원소들을 역순으로 나열해서 작성해야하는 문제가 있다고 가정하자. 필자는 이와같은 문제를 풀다가 Extended Slice라는 기본 개념을 놓쳤기에 이 포스팅을 통해 바로 잡고 가려고한다. 형태는 다음과 같다. ARR[q:w:e] : index q부터 index w 까지 e간격으로 만들겠다 이러한 형태를 띄고 있는것이 Extended Slice라고 한다. 이를 직접적으로 연계시켜 생각할수 있는 문제는 밑에 링크를 참조하자. https://www.acmicpc.net/problem/2908 2908번: 상수 문제 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 ..
