growing pear

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

[두 링크드 리스트의 합 계산] 다음과 같은 두 링크드 리스트를 입력받았을 때, 합산한 값을 반환하시오. 예를 들어, 아래와 같은 링크드 리스트를 입력받았다면, 각각 678, 354이므로 두 개의 총합 678 + 354 = 1032를 반환해야 한다. 단, 각 노드의 데이터는 한 자리 수 숫자만 들어갈 수 있다. 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.nex..

[Linked List에서 index번째 원소를 반환하기] 현재의 index(current_index)가 매개변수 index 값과 같아질 때까지 노드를 한 칸씩 이동하면서, 한 칸 이동할 때 현재의 index값을 1씩 증가시킴 def get_node(self, index): current_index = 0 current_node = self.head while current_index < index: current_node = current_node.next current_index += 1 return current_node [내가 만든 get_node 함수] 노드를 한 칸 이동한 즉시 현재index(current_index)와 매개변수 index의 값을 비교하여 값이 같을 때 current_node를..

[Linked List의 생김새] 노드가 연결되어있는 생김새 linked_list = ["노드1"] -> ["노드2"] -> ["노드3"] -> ["노드4"] [노드가 필요한 정보] 1. 칸에 있는 데이터 2. 다음 칸이 뭔지 클래스의 생성자에 data를 인자로 받아서 self.data에 값을 저장 다음 노드가 이어지는게 없기 때문에 self.next에는 None을 넣어두기 class Node: def __init__(self, data): self.data = data self.next = None 노드 생성 및 연결 node = Node(3) first_node = Node(4) node.next = first_node # node의 next 변수에 first_node의 주소값 저장 데이터 3이 들어..

[ Python) 클래스란? ] 분류, 집합 같은 속성과 기능을 가진 객체를 총칭하는 개념 [그럼 객체는..??] 세상에 존재하는 유일무이한 사물 ex) 클래스가 동물이라면, 객체는 강아지가 될 수도 있고, 고양이가 될 수도 있음 클래스가 사람이라면, 객체는 강호동이 될 수도 있고, 이수근이 될 수도 있음 클래스를 이용하면 같은 속성과 기능을 가진 객체들을 묶어서 정의할 수 있음!! [생성자] 생성 시 호출되는 함수 / 객체를 생성할 때 쓰는 함수 class Person: # __init__ : 생성자 설정 # self: 생성자나 함수 만들 때 인자에 자기자신(현재 클래스)을 넘겨주게 됨 def __init__(self): print("Person constructor! ", self) # Person(..

[Array] 1. 배열은 크기가 정해진 데이터의 공간. 한 번 정해지면 바꿀 수 없음 2. 배열은 각 원소에 즉시 접근 가능. 원소의 순서는 0부터 시작, 인덱스라고 부름 -> "즉시 접근 가능하다" : 상수 시간 내에 접근할 수 있음을 의미함. O(1)의 시간복잡도 3. 배열은 원소를 중간에 삽입 또는 삭제하려면 모든 원소를 다 옮겨줘야함 최악의경우 배열의 길이 N 만큼 옮겨야하기 때문에 O(N)의 시간복잡도를 가짐 4. 원소를 새로 추가하려면 새로운 공간을 할당해야함. 아주 비효율적인 자료구조임 [Linked List] (like 화물열차..) 1. 리스트는 크기가 정해지지 않은 데이터의 공간. 포인터(like 연결고리..)로 이어주기만하면 자유자재로 늘어날 수 있음 2. 리스트는 특정 원소에 접근..

[문자열 뒤집기] 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자를 모두 0, 혹은 모두 1로 같게 만들어야 한다. 할 수 있는 행동은 연속된 하나의 숫자를 잡고 모두 뒤집는 것 이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오. "011110" 알고리즘 문제를 풀다보면, 문제 자체를 이해하기 힘들 때가 있습니다. 그럴 때는 다음과 같이 해보세요! 1. 바로 코드를 작성하지 말고, 문제의 다른 예시들을 떠올리면서 규칙성을 생각해보세요. ex) 00000 은 최소 횟수를 어떻게 구할까? 2. 배웠던 자료구조를 활용하면 어떨지 생각해보세요! ex) 스택, 큐를 활용하면 어떨까? 3. 문제의 특징들을 하나하나 ..

[소수 나열하기] 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오. 소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. # 20이 입력된다면, 아래와 같이 반환해야 합니다! [2, 3, 5, 7, 11, 13, 17, 19] 소수는 자기 자신과 1 외에는 나누어 떨어지지 않음 이걸 증명하면 됨 -> 자기 자신과 1 이외의 숫자로 나누어 떨어지면 소수가 아니다 input = 20 def find_prime_list_under_number(number): prime_array = [] for num in range(2, number + 1): for i in range(2, num): if num % i == 0: break else: prime_array.ap..

[반복되지 않는 문자] 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오. "abadabac" # 반복되지 않는 문자는 d, c 가 있지만 "첫번째" 문자니까 d를 반환해주면 됩니다! 각 알파벳이 각각 몇 개 나왔는지 각각의 값을 가지고 있는 배열을 만들고 1번 나온 알파벳들은 새로운 배열에 저장함 문자열과 1번나온 알파벳만 들어있는 배열과 비교해서 배열에 들어있는 문자가 문자열에서 나오는 순간 리턴 input = "abadabac" def find_not_repeating_character(string): alphabet_occurrence_array = [0] * 26 for char in string:..

[곱하기 or 더하기] 문제) 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. 단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다. 무조건 곱하기만 한다고 커지지 않음! - 0과 곱하게 되면 값이 0이 나옴 : 더하는게 나음 - 1과 곱하게 되면 값이 커지지 않고 그대로임 : 더하는게 나음 ∴ 계산하려는 값이 1 이하일 경우 더하기 앞숫자 + 뒤숫자