growing pear

[스택이란?] 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조. [컴퓨터인터넷IT용어대사전] LIFO(Last In First Out) 이런 자료구조가 왜 필요한가? 넣은 순서를 쌓아두고 있기 때문 그 순서가 필요한 경우가 있음 ex) 되돌리기(Ctrl + Z) [스택의 기능] push(data) : 맨 앞에 데이터 넣기 pop() : 맨 앞의 데이터 뽑기 peek() : 맨 앞의 데이터 보기 isEmpty() : 스택이 비었는지 안 비었는지 여부 반환해주기 스택은 데이터 넣고 뽑는 걸 자주하는 자료 구조! 링크드 리스트와 유사하게 구현할 수 있음!! [push 함수] stack = [4] 스택에 3을 push 하면 [3] → [4] 가 되어야 함 링크드 리스트에서 새로운 head를 지정하려면 새로운 ..

*** 면접에서 직접 구현해보라고 하는 구현 방법!! *** [병합 정렬 - merge] 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘 [1, 2, 3, 5] # 정렬된 배열 A [4, 6, 7, 8] # 정렬된 배열 B [] # 두 집합을 합칠 빈 배열 C ↓ 1단계 : [1, 2, 3, 5] ↓ [4, 6, 7, 8] 1과 4를 비교 1 < 4 이므로 1을 C 에 넣음 C:[1] ↓ 2단계 : [1, 2, 3, 5] ↓ [4, 6, 7, 8] 2와 4를 비교 2 < 4 이므로 2를 C 에 넣음 C:[1, 2] ↓ 3단계 : [1, 2, 3, 5] ↓ [4, 6, 7, 8] 3과 4를 비교 3 < 4 이므로 3을 C 에 넣음 C:[1, 2, 3] ↓ 3단..

[삽입정렬] 전체에서 하나씩 올바른 위치에 "삽입" 하는 방식 선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꾸지만 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식임 [4, 6, 2, 9, 1] # 정렬되지 않은 배열 1단계 : [4, 6, 2, 9, 1] 4는 현재 정렬되어 있는 원소입니다. 그럼 이제 새로운 원소 6을 받습니다. 4, 6 이 되는데 4 < 6 이므로 그대로 냅둡니다. [4, 6, 2, 9, 1] 이제 한 바퀴를 돌린 상태입니다. 이 과정에서 새로운 원소인 4, 6은 현재 정렬된 상태입니다. 이처럼, 삽입 정렬은 한 바퀴가 돌 때마다 정렬된 상태가 됩니다. 2단계 : [4, 6, 2, 9, 1] 4, 6 은 현재 정렬되어 있는 원소입니다. 그럼 이제 새로..

[선택정렬] 전체에서 최솟값을 "선택" 하는 것 말 그대로 선택해서 정렬한다고 생각하면 됨 [4, 6, 2, 9, 1] # 정렬되지 않은 배열 1단계 : [4, 6, 2, 9, 1] 4와 6과 2와 9와 1을 차례차례 비교합니다. 그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다! [1, 6, 2, 9, 4] 이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다. 가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요 그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다. 2단계 : [1, 6, 2, 9, 4] 6과 2와 9와 4를 차례차례 비교합니다. 그 중 가장 작은 2와 두번째 앞 자리인 6을 교체합니다 [1, 2, 6, 9, 4] 3단계 : [1, 2, 6, 9, 4] 6과 9와 4를 차례차례 비교..

[정렬이란?] 데이터를 순서대로 나열하는 방법을 의미 정렬은 알고리즘의 굉장히 중요한 주제임 데이터를 조금 더 효율적으로 탐색할 수 있게 만들기 때문 컴퓨터에 정렬을 시키기 위해서는 명확한 과정을 설명해줘야함 [버블정렬] 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, ... (마지막 - 1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬하는 방식 작은 숫자, 큰 숫자 순서로 있으면 냅두고 큰 숫자, 작은 숫자 순서로 있으면 둘의 위치를 변경 [문제] 다음과 같이 숫자로 이루어진 배열이 있을 때, 오름차순으로 버블 정렬을 이용해서 정렬하시오. 풀이) input = [4, 6, 2, 9, 1] def bubble_sort(array): #O(N^2) for i in range..

[문제] 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [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이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오 numbers = [1, 1, 1, 1, 1] target_number = 3 [먼저 모든 경우의 수 구하는 함수 만들기] No. 연산 결과값 타겟여부 연산자 1 +2 +3 +1 6 + ..

[문제] 배달의 민족 서버 개발자로 입사했다. 상점에서 현재 가능한 메뉴가 ["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때, 유저가 ["오뎅", "콜라", "만두"] 를 주문했다. 그렇다면, 현재 주문 가능한 상태인지 여부를 반환하시오. menus = ["떡볶이", "만두", "오뎅", "사이다", "콜라"] orders = ["오뎅", "콜라", "만두"] shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"] shop_orders = ["오뎅", "콜라", "만두"] def is_available_to_order(menus, orders): # 이 부분을 채워보세요! return True result = is_available_to_order(shop_me..

[문제] 링크드 리스트의 끝에서 K번째 값을 반환하시오. [6] -> [7] -> [8] # 이러한 링크드 리스트가 입력되었을 때, # 끝에서 2번째 값은 7을 반환해야함 class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self, value): self.head = Node(value) def append(self, value): cur = self.head while cur.next is not None: cur = cur.next cur.next = Node(value) def get_kth_node_from_last(self, k): # 구현해보세요! return ..

[팩토리얼] 팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것 5! = 5 * 4 * 3 * 2 * 1 Factorial(n) = n * Factorial(n - 1) Factorial(n - 1) = (n - 1) * Factorial(n - 2) .... Factorial(1) = 1 의 구조임 def factorial(n): if n is_palindrome("bcb") -> is_palindrome("c") -> is_palindrome(string[1:-1]) string[1(첫번째글자):-1(뒤에서첫번째글자)] [탈출 조건] 문자열의 길이가 1보다 작거나 같을 때(문자열이 한글자일 때: 한글자여도 앞으로 읽거나 뒤로 읽어도 같으니 회문임) -> 참 맨 첫번째 문자와 맨 뒤의 문자..

" 주어진 범위 안에서 특정 숫자 찾기 " 방법1) 숫자를 일일이 다 비교하면서 찾기(순차탐색) 방법2) 이진탐색으로 찾기 [이진탐색] 이진탐색은 Up&Down 게임과 같음! Up&Down 게임 : 특정 숫자를 맞추는 게임. 정답인 숫자가 더 높다면 "UP", 낮다면 "Down" 을 부르는 게임 위의 게임을 할 때 숫자의 범위를 최대한 줄이는 게 가장 효율적임 만약 1~100 사이의 숫자를 찾아야 한다면, 50을 먼저 외쳐 범위를 1~49 또는 51~100으로 줄이고 게임을 하는게 좋음 이처럼 범위를 절반씩 줄여가면서 찾는게 가장 빨리 찾을 수 있음 이 방법이 바로 "이진탐색" " 그럼, 방법 1이랑 방법 2 둘 중 뭐가 더 효율적일까??! " [1~16까지 오름차순으로 정렬되어있는 배열 중에서 14 찾..