개발일지/자료구조
-
자료구조(4) - Queue개발일지/자료구조 2021. 12. 20. 20:37
Queue Queue : Stack과 비슷한 구조로 Stack과의 차이점은 아래가 뚫려있는 바구니이다. 그래서 처음 들어간 데이터가 가장 먼저 나오게 되는 First In, Fist Out 의 구조를 띈다 FIFO(First In, First Out) 문제에 강함, 빨대나 터널, 출입구와 비슷한 모양으로 지나간 갯수를 셀 때 유용 # Stack 기본 메소드 Queue 메소드 설명 return push(x) X원소 데어터 추가 None pop() 가장 처음 넣은 데이터 꺼내기 value peek() pop이 될 데이터 확인 None is_empty 남은 데이터가 있는지 확인 None 구현은 여러가지가 있지만 알고있는 방법들을 나열하자면 3가지 정도 된다. deque 라이브러리 이용 List이용 Linked..
-
자료구조(3) - Stack개발일지/자료구조 2021. 12. 20. 20:36
Stack Stack : List의 자료구조와 비슷하며 데이터를 정렬할 때 사용하기보단 FILO (First In, Last Out)를 활용한 문제가 있을 때 사용된다. 구조는 위의 그림처럼 아래가 막혀 있는 바구니를 생각하면된다. 위의 그림처럼 색깔 순으로 Stack에 넣는다면 처음부터 넣은 남색부터 데이터가 쌓이고 마지막으로 보라색이 넣어진다. 나올때는 반대로 마지막에 넣었던 보라색부터 나오고 맨처음 들어간 남색이 마지막에 나오므로 First In Last Out이 된다. FILO ( First In Last Out ) 넣은 순서를 기억해야 하는 알고리즘 문제 풀 때 유용 Ex) 되돌리기기능, 짝맞추기 기능 등등 #Stack 기본메소드 Stack 메소드 설명 Return Push(valu..
-
자료구조(2) - 재귀 함수개발일지/자료구조 2021. 12. 20. 20:35
재귀 : 자기 자신을 의미 Ex) 재귀대명사( himself - 그자신) 위의 뜻처럼 함수 내부에서 본인의 함수를 호출하는 함수를 재귀함수라 한다. 가장 자주 나오는 예시로는 Factorial(팩토리얼) 이 있다. Factorial의 의미는 해당 주어진 숫자부터 1까지의 곱을 의미한다 표기 !로 한다. # 정의 N! = N x (N-1) x . . . x 3 x 2 x 1 #Example 5! = 5 x 4 x 3 x 2 x 1 7! = 7 x 6 x 5 x 4 x 3 x 4 x 3 x 2 x 1 해당 알고리즘을 단순히 구현하자면 다음과 같이 구현할 수 있다. def Factorial_simple(n): # Factorial - 단순버전 result = 1 # 결과값 지정 for i in range(1,..
-
자료구조 (1) - Array, Linked List개발일지/자료구조 2021. 12. 20. 20:34
해당 글에서는 기본적인 자료구조인 Array. Linked_List를 정리하려고 한다. 사실 실제 기본적인것은 느낌만 있을뿐 처음 배웠던 자료구조이기 때문이다. 우선 둘다 리스트의 형태를 띈다. 여기서 리스트의 형태는 다음과 같은 체크 리스트 처럼 당근 파 댤걀 10개 오리온 초코파이 예감 ... 데이터들을 정렬하는 방법이다. Array와 Linked List 둘다 데어티가 정렬된 형태를 띄지만 저장 방식이 다름 Array는 연속된 순서대로 값이 저장되기 때문에 데이터의 index가 존재하고 공간이 정해져 있다. 공간이 정해져 있기 때문에 너무 큰 사이즈의 경우 다른 자원을 침범할 수 도 있기 때문에 저장공간에 제약이 생김 하지만 Linked List는 이와는 별개로 Index가 존재하지 않..
-
복잡도개발일지/자료구조 2021. 12. 20. 20:33
알고리즘을 작성을 해서 목표하는 기능이 구현되는 것은 가장 우선시 되어야할 사항이지만 같은 기능을 구현하더라도 효율의 차이가 발생한다. 알고리즘에서는 크게 2가지로 효율성을 판단하며 이를 복잡도라고 한다. 복잡도의 종류는 시간복잡도, 공간복잡도가 있다. 시간복잡도 알고리즘을 수행하는 시간을 말하며 입력받은 값에 따라 항상 달라지기 때문에 입력받은 값을 기준으로 표기를 한다. 예를 들어 다음과 같은 알고리즘 이라면 # 배열 생성 a_list = [1,4,2,7,9,4,3,6,3] # 각 리스트원소를 순회하면서 3을 찾아 출력하는 알고리즘 for i in a_list: if i == 3: print(3) break 각 리스트원소들을 모두 꺼내 확인해야하므로 배열의 길이에 따라 값이 시간이 달라진다. 2개면 ..