포시코딩

스택이란? LIFO(Last In First Out)의 성격을 가진 자료구조. 데이터를 쌓고나서 데이터를 빼낼 때 마지막으로 넣은 데이터부터 빼내는 자료구조이다. 참고로 반복문의 무한루프 등으로 메모리의 이 스택 영역이 쌓이고 쌓이다가 터지는 현상을 많이 들어본 스택오버플로우(StackOverflow)라고 한다. 사용예시 웹에서의 뒤로가기 버튼 Undo / Redo React의 Stack Navigator 스택의 대표 기능 Peek 스택의 Top(맨 위) 데이터를 보는 것 Push 스택의 Top에 원소를 삽입하는 행위 Pop 스택의 Top에서 원소를 가져오는 행위. Push로 넣었던 원소가 나오게 된다. Peek, Push, Pop 코드 구현 이전 포스팅에서 배웠던 링크드리스트를 통해 스택을 구현해보자 ..

따로 튜터팀께서 직접 라이브 시연으로 재귀 함수를 응용하는걸 보여주셨다. 정수로 이루어진 배열의 요소들을 더하거나 빼서 특정한 숫자를 만드는 문제에 대한 풀이었는데 듣기는 했으나 이해가 어려워 일단 강의 자료를 기록해둔다.. # Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 '더하거나 빼서' 특정한 숫자를 만들려고 한다. # 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다. # -1+1+1+1+1 = 3 # +1-1+1+1+1 = 3 # +1+1-1+1+1 = 3 # +1+1+1-1+1 = 3 # +1+1+1+1-1 = 3 # 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘거 target_number이 매개변수로 주어질 때 숫..

삽입 정렬 선택 정렬이 전체에서 최솟값을 '선택'하는 정렬이었다면 삽입 정렬은 전체에서 하나씩 올바른 위치에 '삽입'하는 방식이다. 버블 정렬과 선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꿨지만, 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식이라고 할 수 있다. 이번에도 마찬가지로 구해야하는 인덱스의 값부터 for문을 만들어 찾아보자 이런식으로 비교할 인덱스가 어떤식으로 전개될지 쭉 써보고 그 중에 i 값은 뭐가 될지 그에 따른 j 값은 뭐가 되고 어떻게 구해야할지 생각해보면 for문을 어떻게 짤지 대충 감이 온다. arr = [4, 6, 2, 9, 1] # 1 2 1 3 2 1 4 3 2 1 def insertion_sort(arr): n = len(arr) for..

선택 정렬 선택 정렬은 처음부터 끝까지 하나씩 확인하며 제일 작은 값을 찾아 맨 앞으로 보낸 후 다시 두번째부터 끝까지 하나씩 확인하며 이번에 제일 작은 값을 두번째로 보내는 과정을 반복하는 정렬이다. 이번에도 마찬가지로 구해야하는 인덱스의 값부터 for문을 만들어 찾아보자 arr = [4, 6, 2, 9, 1] # 0 1 2 3 4 1 2 3 4 2 3 4 3 4 def selection_sort(arr): n = len(arr) for i in range(n-1): for j in range(n-i): print(i+j) selection_sort(arr) 버블 정렬과 다른점은 '최솟값'을 찾아 변경한다는 부분이다. 인덱스를 하나씩 돌며 제일 작은 값을 찾아 인덱스만 따로 min_i 변수에 저장한 뒤..

정렬이란? 데이터를 순서대로 나열하는 방법을 의미. 이진 탐색을 가능하게도 하고, 데이터를 조금 더 효율적으로 탐색할 수 있게도 한다. 버블 정렬 버블 정렬은 첫 번째 자료와 두 번째 자료, 두 번째 자료와 세 번째 자료, ... 이런식으로 (n - 1) 번째 자료와 n 번째 자료를 비교하여 교환하면서 자료를 정렬하는 방식이다. ex) 첫 루프에서 두 개씩 비교해서 끝까지 가면 제일 큰 수가 마지막에 위치하게 된다. 이제 마지막 수는 고려하지 않아도 되므로 제외하고 다시 처음부터 마지막-1 번째까지 두 개씩 비교하고 다시 마지막-1 번째도 제외하고.. 를 반복해서 정렬시키는 방식이다. 코드로 구현해보자 input = [4, 6, 2, 9, 1] 위와 같은 숫자로 이루어진 배열이 있을 때 버블 정렬을 통해..

재귀 함수 재귀란? 재귀(Recursion)은 자신을 정의할 때 자기 자신을 재참조하는 방법을 말한다. 더 나아가 재귀함수란 정의 단계에서 자신을 재참조하는 함수를 뜻한다는걸 알 수 있다. 어디에 쓸까? 60초부터 0초까지 -1을 하며 print()를 해야할 때와 같은 상황에서 간결하고 효율성 있는 코드를 작성할 때 사용한다. 아래의 예시 코드를 보자 #def count_down(number): # print(number) # count_down(number - 1) # #count_down(60) # 이대로 실행하면 무한히 -1이 되어 Recursion Error를 내게 되므로 아래처럼 탈출 조건을 만들어야 한다. def count_down2(number): if number < 0: return pr..

2진 탐색 인덱스가 0부터 16까지 있는 array가 있을 때 그 중 정답이 target인 값을 찾으려면 어떻게 해야할까? for문을 통해 처음부터 하나씩 비교하는 방법이 있겠지만 맨 마지막에 정답이 있으면 O(N) 만큼의 시간 복잡도가 걸리게 될 것이다. 이 때, 2진 탐색이라는 방법을 통해 시도 횟수를 확 낮출 수 있다. 딱 가운데 위치하는 값을 정답과 비교해서 정답이 더 크다면 가운데 위치하는 값 이하의 인덱스를 모두 버리고 정답이 더 작다면 가운데 위치하는 값 이상의 인덱스를 모두 버리는 식으로 구하며 이를 반복하면 된다. 이는 알고리즘 문제에서 UP & DOWN 문제로도 자주 나오는 형태이다. 문제풀이 예시 시간 복잡도 O(log N) 총 숫자가 1 ~ N 까지라고 한다면 1번 탐색하면 반절이 ..

맨 뒤에 노드 추가하기 class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self, value): self.head = Node(value) 저번 포스팅에서 LinkedList를 위해 위와 같은 클래스를 만드는 것 까지 했다. 이번에는 LinkedList의 맨 뒤에 새로운 Node를 붙이는 append 함수를 만들어보자 how? 현재 있는 노드의 가장 맨 뒤에 새로운 값을 가진 노드를 추가하면 된다. 끝 말로는 쉽지만 그러기 위해선 먼저 가장 맨 뒤의 노드까지 이동해야 한다. head [3] -> [5] -> [7] head를 변경시킬 수는 없으니 cur = self.he..

js 또는 java에서의 class에 대한 기초 지식이 있다는 가정하에 작성된 글입니다. class in Python 파이썬에서는 생성자 함수의 이름이 __init__ 으로 고정되어 있다. 생성 시 생기는 self는 객체 자기 자신을 가리킨다. 파라미터를 따로 넣을 필요 없이 알아서 넣어줌 class Person: def __init__(self): print('hi') person = Person()# hi가 출력됨 추가로 아래처럼 self를 사용해서 객체에 데이터를 쌓을 수 있다. class Person: def __init__(self, param_name): self.name = param_name 메소드를 추가할 때도 self가 자동으로 붙는데 만들어보면 다음과 같다. class Person: ..

개요 들어가기에 앞서, 자료구조를 왜 배워야할까? 특정 자료구조는 삽입/삭제가 빠르고 특정 자료구조는 조회가 빠르다. 이처럼, 어떤 경우에는 이 자료구조가 좋고, 어떤 경우에는 저 자료구조가 좋은 것 처럼 경우에 따라 다양한 자료구조와 알고리즘을 사용해야 한다. 이번 포스팅에선 자료구조 중 Array와 Linked list에 대해 알아보도록 하자 특징 어레이(Array) = 배열 배열은 크기가 정해진 데이터의 공간이다. 한 번 정해지면 바꿀 수 없음 배열은 각 원소에 즉시 접근할 수 있다. ex) arr[0] 여기서 원소의 순서는 0부터 시작하고 이를 인덱스라고 부른다. 이 때, 즉시 접근 가능하다는 말은 상수 시간 내에 접근할 수 있음을 의미한다. 즉, O(1) 내에 접근 할 수 있다고 말할 수 있다...