어서와! 자료구조와 알고리즘은 처음이지? 강의 수강 후 내용을 정리한 글입니다. 자료 구조 정의 Node - Data - Link (next) Head : 리스트의 맨 앞 요소 Tail : 리스트의 맨 끝 요소 of nodes : 연결리스트의 노드 갯수 연결 리스트의 각 원소들이 링크로 연결되어 있다. 배열은 인덱스로 지정되어 있지만 연결 리스트는 임의의 위치에서 연결할 수 있다. 물론 앞에서부터 하나하나 따라가다 보니 선형 탐색과 유사한 점이 있다. 하지만 선형 배열과 비교했을 때, 연결 리스트는 원소 가운데를 끊어 처리할 수 있기 때문에 원소 삽입 또는 삭제가 더 간단하다. 다만 저장 공간(메모리)의 소요가 더 크기 때문에 단점도 존재한다. 연산 정의 특정 원소 참조 (k번째) / 리스트 순회 / 길..

어서와! 자료구조와 알고리즘은 처음이지? 강의 수강 후 내용을 정리한 글입니다. 알고리즘의 복잡도란 문제를 해결하는 데에 있어서 얼마만큼의 자원을 요구하는 가를 파악하는 것이다. 크게 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도 (Time Complexity) 문제의 크기와 이를 해결하는 데 걸리는 시간간의 관계이다. 문제 해결을 위해 입력(input)으로 들어오는 것을 문제의 크기라고 말한다. 평균 시간 복잡도 데이터 입력이 랜덤하게 들어왔을 때, 즉 임의의 입력 패턴을 가정했을 때 걸리는 시간의 평균 최악 시간 복잡도 가장 긴 시간을 소요하게 만드는 입력에 따라 걸리는 시간 (최악의 경우) 공간 복잡도 (Space Complexity) 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 ..

어서와! 자료구조와 알고리즘은 처음이지? 강의 수강 후 내용을 정리한 글입니다. 재귀 함수 (recursive functions) 재귀 함수란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 것을 의미한다. 같은 알고리즘을 반복적으로 적용하여 풀어낸다. 구글에 Recursive를 검색하면 '이것을 찾으셨나요?'라며 또다시 나온다. 이 역시 재귀를 표현한 구글의 유머 감각이다. (방심하고 봤다가 빵 터짐..) 종결 조건 (trivial case) 재귀 함수를 사용할 때에는 알고리즘의 종결 조건이 필요하다. 조건이 없다면 계속해서 무한히 반복하기 때문이다. def sum(n): if n..: ... else: ...sum(..).. 예제 - n! (팩토리얼) def what(n): if n

어서와! 자료구조와 알고리즘은 처음이지? 강의 수강 후 내용을 정리한 글입니다. 정렬 (Sort) 정렬이란, 배열에 있는 원소들을 조건에 따라 정렬한다는 것을 의미한다. 파이썬에서 문자열로 이루어진 리스트를 정렬할 경우, 문자열은 사전 순서를 따르며 길이가 길다고 해서 큰 것이 아니라는 점을 주의해야 한다. 파이썬에서의 리스트 정렬 방법은 2가지가 있다. sorted() 파이썬의 내장 함수 (built-in function) '새로운' 정렬 리스트를 만듦 sort() 리스트의 method 단순히 해당 리스트를 정렬함 L = [3, 8, 2, 7, 6, 10, 9] L2 = sorted(L) L.sort() 역순으로 정렬 reverse=True를 입력함으로써 파이썬의 리스트를 역순으로 정렬한다. 탐색 (S..

어서와! 자료구조와 알고리즘은 처음이지? 강의 수강 후 내용을 정리한 글입니다. 선형 배열 (Linear Array)은 데이터들이 선(=line)처럼 일렬로 늘어선 형태이다. 자바, C에서 볼 수 있듯이 같은 종류의 데이터가 담긴 '배열'과 다르게, 파이썬에서의 리스트는 각 원소가 서로 다른 데이터 타입을 가지고 있어도 된다. 문자열의 경우, 문자열 길이가 다른 것 역시 상관없다. 리스트 길이와 관계없이 빠른 결과 시간 L = ['Bob', 'Cat', 'Spam', 'Programmers'] L.append('New') L.pop() 먼저 리스트 L을 선언하였다. append는 리스트의 가장 마지막 인덱스에 원소를 추가한다. pop은 마지막 인덱스에서 요소를 꺼낸다. append와 pop 모두 가장 마..