알고리즘

[자료구조]순열자료구조 Queue 와 Josephus problem

Queue FIFO First In First Out: 먼저들어온것을 먼저내보내는 자료구조 값을 추가하는것을 enqueue라고 하며 내보내는것을 dequeue라고 합니다. class Queue: def __init__(self): self.items = [] self.first_index = 0 def enqueue(self, value): self.items.append(value) def dequeue(self): if self.first_index == len(self.items): # (1) print('Out of Index') else: result = self.items[self.first_index] self.first_index += 1 return result first_index는 q..

[자료구조] 순열자료구조 Stack

Stack이란? LIFO Last In First Out: 마지막에 들어온것을 먼저 내보내는 자료구조 값을 추가할땐 push라고 하며 빼낼땐 pop이라고한다 class Stack: def __init__(self): self.items = [] def push(self, value): self.items.append(value) def pop(self): try: return self.items.pop() except IndexError: print('Stack is empty') def top(self): try: return self.items[:-1] except IndexError: print('Stack is empty') def __len__(self): return len(self.items..

[자료구조]Big-O 표기법

Big-O 표기법 수행시간을 의미하는 T(n)함수값을 결정하는 최고차항만으로 간단하게 표기하는방법 입력값에 대한 증가율을 표기하는것이다.(수행시간이 차이가 있더라도 증가율이 같다면 같은 표기를 한다.) O(최고차항) 최고차항만 남긴다 최고차항 계수(상수)는 생략해준다 Big-O(최고차항)으로 표기한다 상수연산만 하는 알고리즘이라면? def func1(n): return n+1 def func2(n): n += 1 n += 1 n += 1 return n fun1 과 func2 의 T(n)은 각각 1 과 3이다 하지만 두개다 상수이기 때문에 빅오 표기법에서는 아래와 같이 표기한다 O(n**0) = O(1) 증가율이 줄어드는 log의 경우는 어떻게 될까?! def func1(n): count = 0 whil..

[자료구조] 간단한 알고리즘 시간복잡도 구하기

Array 에서 가장 큰 원소 구하기 def array_max(A:Array,n:int): (1) current_max = A[0] (2) 대입연산 for i=1 to n-1: (3) if current_max < A[i]: (4) 비교연산 current_max = A[i] (*) 대입연산 return current_max (1) input으로 A라는 Array와 n이라는 int타입 데이터를 받는다 - 이때 n은 Array의 길이이다 (2) current_max 에 A의 0 번째 값을 할당한다 -(수행횟수 = +1) - 모든 인풋값에 대하여 항상 수행한다 (3) 1부터 n-1까지 반복하여 작업을 수행한다. - 연산은 하지않기에 수행횟수가 추가되지않는다. (4) 반복문을 돌때마다 한번씩 비교연산자를 수행한..

[자료구조] 자료구조의 기본과 최대공약수를 구하는 3가지방법

자료구조란? 자료(Data)를 담는 구조(Structure)를 말한다 어디에 담을까?! Memory(주 기억장치) 어떻게? 효과적인 읽기,쓰기,삽입,삭제,탐색 연산을 제공하도록 프로그래머로 가장 근접한 자료구조는? 배열(Array) a = [1,2,3] # 쓰기연산 print(a) # 읽기연산 a.append(4) # 삽입연산 a.pop() # 삭제연산 변수(variable) a = 5 # 쓰기연산 print(a) # 읽기연산 알고리즘이란? 자료구조에 저장된 자료를가지고 어떠한 문제를 푸는 논리적인 절차 유하한 횟수의 연산들을 반복해서 정답을 도출해 내는것 최대공약수 구하기 (sub 방식- 빼기방식) def gcd(a,b): while a != 0 and b != 0: if a>b: a = a - b ..

[자료구조] 자료구조란?!

자료구조란? 자료구조란 데이터에 효율적으로 접근하고 수정할 수 있도록 저장/조직/관리하는 방법이론이다. 자료구조,알고리즘,프로그래밍,이산수학 관계도 자료구조를 공부해야 하는 이유 효율적인 데이터 관리와 사용을 위해 자료구조와 알고리즘을 공부해야한다. 자료구조를 도구로 빗대어 표현을 많이 하는데 10keyless 키보드와 일반 키보드를 비교하면 좋을것 같다. 텐키리스 키보드 장점 - 마우스의 움직임이 자유로워진다. 단점 - 숫자칠때 불편하다 일반 키보드 장점 - 숫자칠때 편하다 단점 - 마우스 움직임이 상대적으로 불편해진다. 사람의 팔길이는 제한되기에 마우스와 키보드의 거리를 벌리더라도 사용가능한 영역은 제한되어있다. 마우스를 사용하는 게임을 할때는 텐키리스 키보드를 사용한다면 게임에 도움이되겠지만 키보..