패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

자료구조와 알고리즘

• 프로그래밍에서 데이터를 구조적으로 표현하는 방식과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초이론
• 효율적인 자료구조란 프로그램의 실행시간 효율과 저장공간 효율을 의미한다. (효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다.)
• 각 자료구조의 장단점을 숙지하고 상황별로 적합한 자료구조를 선택하는 능력이 중요하다.
• 자료구조 : 데이터를 어떤 구조로 저장하고, 탐색하고, 삭제해야 가장 효율적일까? (어떻게 메모리를 가장 효율적으로 사용할 수 있을까? -> 실행속도 영향)
• 알고리즘 : 문제를 해결하는 방법론
• 참고 - 자료구조 위키백과

알고리즘

알고리즘 이란 어떤 값을 입력으로 받아 원하는 값으로 출력하는 잘 정의된 계산 절차 를 말한다. 따라서 알고리즘은 어떤 입력을 어떤 출력으로 변환하는 일련의 계산 과정이라 할 수 있다.

자료구조

자료구조 란 데이터에 편리하게 접근하고, 변경하기 위해서 데이터를 저장하거나 조직하는 방법 을 말한다. 모든 목적에 맞는 자료구조는 없다. 따라서 각 자료구조가 갖는 장점과 한계를 잘 아는 것이 중요하다.
자료구조는 언어별로 지원하는 양상이 다르다. 따라서 각각의 언어가 가진 자료구조의 사용방법도 중요하지만, 무엇보다 각 자료구조의 본질과 컨셉을 이해하는 것 이 중요하다. 컨셉을 알고 있다면 기억해야 할 것이 현저히 줄어들게 된다.

자료구조의 미션 : 메모리의 효율적인 사용

• 컴퓨터에는 3가지 중요한 부품이 존재하며 다음과 같은 특성을 가진다.
  • CPU : 중앙정보처리장치, 레지스터, 데이터를 연산/처리하는 가장 중요한 부분, 아주 빠름 (기억 떠올리기)
  • 메모리 : RAM(Random Access Memory), CPU에서 직접 접근이 가능, 사용자가 자유롭게 내용을 읽고 쓰고 지울 수 있다. 휘발성 기억장치, 빠름 (책에서 특정한 내용 찾아 읽기)
  • 스토리지 : HDD, SSD, 비휘발성 기억장치, 용량이 아주 크지만 느림 (지구를 한바퀴 돌아서 찾기)
• 상기와 같은 이유로 데이터는 기본적으로 스토리지에 저장된다.
• 하지만 스토리지는 매우 느리기 때문에 CPU와 함께 일하기에는 속도면에서 부족하다.
• 따라서 어떤 프로그램을 실행하면 해당 프로그램과 데이터는 메모리로 옮겨진다.
• CPU는 메모리에 로드된 데이터를 이용해서 여러가지 일을 하게 된다.
• 그러므로 실행속도를 결정하는 것은 대체로 메모리 이며, 자료구조를 배우는 이유는 메모리의 효율적인 사용 이라고 할 수 있다.

자료구조와 알고리즘의 관계

• 자료구조를 구현하기 위해서 알고리즘이 필요하다.
• 자료구조의 알고리즘 : 데이터를 저장하고 탐색하는 방법에 대한 고민들
• 자료구조를 이용한 알고리즘 : 자료구조를 활용하여 어떤 문제를 해결하는 것

자료구조의 구성

• Insert : 데이터를 어떻게 저장 할 것인가
• Search : 데이터를 어떻게 탐색 할 것인가
• Delete : 데이터를 어떻게 삭제 할 것인가

자료구조의 분류

• 단순구조 : 프로그래밍에서 사용되는 기본 데이터 타입
• 선형구조 : 저장되는 자료의 전후관계가 1:1 (리스트, 스택, 큐 등)
• 비선형구조 : 데이터 항목 사이의 관계가 1:n 또는 n:m (트리, 그래프 등)
• 파일구조 : 서로 관련된 필드들로 구성된 레코드의 집합인 파일에 대한 자료구조

Arrary (배열)

• 참고 생활코딩 - 배열
• 데이터가 많아지면 그룹 관리의 필요성이 생긴다. 이럴 때 프로그래밍에서 사용하는 것이 배열
• 여러 데이터를 하나의 이름으로 그룹핑해서 관리 하기 위한 자료구조
• 배열을 이용하면 하나의 변수에 여러 정보를 담을 수 있고, 반복문과 결합 하면 많은 정보도 효율적으로 처리할 수 있다.
• 배열 인덱스는 값에 대한 유일무이한 식별자 (참고로 리스트에서 인덱스는 몇 번째 데이터인가 정도의 의미를 가짐)

java array 예시

• 배열은 정의와 동시에 길이를 지정하며 길이를 바꿀 수 없다.

// array 정의
int[] numbers1 = new int[4];

// array에 값 저장
numbers1[0]=10;
numbers1[1]=20;
numbers1[2]=30;

// array의 길이 확인
System.out.println(numbers1.length); // 4

• 처음 정의시 크기를 4로 지정하였기 때문에 3개의 값이 설정되었어도 결과는 4이다.
• 바로 이런 이유에서 자바에서는 ArrayList나 LinkedList와 같은 리스트를 사용한다.
• 리스트는 자동으로 엘리먼트를 수용할 수 있는 크기가 조정되고 또 리스트 내의 엘리먼트의 실제 개수를 알려준다.

자바의 배열은 기능적으로 한계가 많습니다. 배열의 크기를 배열을 생성할 때 지정하는 것이나, 배열의 크기를 변경할 수 없는 것은 몹시 불편한 일입니다. 또 배열에서 설정된 엘리먼트의 개수를 알아낼 수 없는 것도 불편합니다. 그렇다고 배열이 쓸모가 없는 것은 아닙니다. 데이터의 크기가 확정적일 때 배열을 사용하는 것이 메모리나 처리속도 면에서 좋습니다. 또한 배열은 다른 데이터 스트럭쳐의 부품이 되기도 합니다. 기능이 최소한일수록 좋은 부품이 될 수 있습니다. 기능이 많으면 사용하기는 좋아도 그것을 사용할 수 있는 용도가 제한되기 때문입니다. 그럼 배열의 이런 한계를 극복하려면 어떻게 해야할까요? 조금 더 개선된 기능의 데이터 스트럭쳐를 고안할 필요가 있습니다. 그런 데이터 스트럭쳐가 바로 list입니다 (출처 : 생활코딩)

배열의 특징

• 크기가 정해져 있다 / 기능이 없다
  (이는 배열의 장점이자 단점으로 배열은 다른 자료구조의 좋은 부품으로 사용될 수 있다.)
• 인덱스 를 가지며, 엘리먼트의 인덱스는 변경되지 않는다.
  (현실세계의 주민번호, 학급에서 학생에게 부여하는 번호)
• 유관 데이터를 메모리에 순차적으로 (인덱스) 나열할 수 있다.
• 인덱스를 활용하여 빠르게 조회가 가능하다.
• cache hit 의 가능성이 커져서 성능에 큰 도움이 된다.
• 인덱스를 이용하여 데이터를 가져오려면 데이터에 대한 인덱스 값이 고정되어야 한다. (삭제된 엘리먼트의 공간이 그대로 남는다. -> 메모리의 낭비)

배열의 한계

• 배열은 길이를 바꿀 수 없다. 가변 배열과 같이 길이가 변경 가능한 배열의 경우,
  • 기존의 배열은 그대로 두고,
  • 새로운 길이로 지정된 배열을 따로 할당 후 (메모리가 있는지 탐색 필요)
  • 데이터의 복사를 진행하고,
  • 기존의 배열을 삭제한다.
  • 총 3번의 작업 + 메모리 탐색 이 필요하기 때문에 리소스 낭비가 크다.
• 위와 같은 한계를 해결하기 위해서 linked list 자료형을 활용할 수 있다. (탐색, 할당, 복사, 삭제 등의 리소스 낭비가 없다.)
• 배열은 인덱스에 따라서 값을 유지하기 때문에, 엘리먼트가 삭제되어도 빈자리(null)가 남게 된다. (불필요한 메모리 차지)
• 조건문을 통해서 빈 엘리먼트를 제외할 수 있으나, 조건문을 많이 사용하는 것은 좋지 않다.
• 삭제한 데이터를 뒤에 위치한 엘리먼트로 메꾸면, 데이터가 순서에 따라서 빈틈없이 연속적으로 위치하며 이를 list(리스트) 라고 한다.
• 인덱스가 중요한 경우는 배열을 사용, 인덱스가 중요하지 않은 경우에는 리스트를 사용한다.

list (리스트)

• 참고 생활코딩 - 리스트
• 리스트는 배열이 가지고 있는 인덱스라는 장점을 버리고 대신 빈틈없는 데이터의 적재 라는 장점을 취한 데이터 스트럭쳐
• 리스트 자료구조의 핵심은 엘리먼트들 간의 순서. 따라서 리스트를 다른 말로는 시퀀스(sequence) 라고도 부른다. 즉 순서가 있는 데이터의 모임이 리스트이다.
• 리스트에서 인덱스는 몇 번째 데이터인가 정도의 의미를 가진다. (배열-Array에서의 인덱스는 값에 대한 유일무이한 식별자)
• 빈 엘리먼트는 허용하지 않는다.
• 순차성을 보장하지 못하기 때문에 spacial locality 보장이 되지 않아서 cash hit가 어렵다.
• 데이터 갯수가 확실하게 정해져 있고, 자주 사용된다면 array가 더 효율적이다.
• 리스트에 대한 효용은 어떤 언어를 사용하느냐에 따라서 달라진다. 특히 많은 언어가 리스트를 기본적으로 지원하기 때문에 리스트를 직접 구현하는 경우는 줄고 있다.

list 자료구조의 대표 기능 (operation)

자료구조에서 가장 중요한 점은, 해당 자료구조가 어떠한 기능을 가지고 있느냐는 것이다.

• 처음, 끝, 중간에 엘리먼트를 추가/삭제 하는 기능
• 리스트에 데이터가 있는지를 체크하는 기능
• 리스트의 모든 데이터에 접근할 수 있는 기능

언어별 list 지원 비교

• data-structure를 직접 구현할 수도 있지만, 대부분의 경우 이미 누군가가 구현한 라이브러리를 사용하는 경우가 더 많다.
• 최근의 언어는 리스트를 기본적으로 지원한다.
• data-structure는 언어마다 다른다.

C

• 리스트를 지원하지 않는다. 대신 배열을 지원한다.
• 리스트를 사용하려면 직접 만들거나 라이브러리를 사용해야한다. (따라서 리스트에 대한 깊은 이해와 안목이 필요함)

JavaScript

• C 패밀리 랭귀지
• 자바스크립트에서는 배열에 리스트의 기능이 포함되어 있다.

numbers = [10, 20, 30, 40, 50];

numbers.splice(3, 1); // 인덱스 3에서부터 1개의 값을 삭제한다.

for(i = 0; i < numbers.length; i++){
	console.log(numbers[i]);
	// 10, 20, 30, 50
}

Python

• 기본적으로 리스트를 제공하며, 배열은 제공하지 않는다.
• 파이썬에서는 리스트가 배열이다.
• 파이썬의 리스트는 크기가 가변적이고, 어떤 원소 타입이던 저장할 수 있다는 장점을 가진다. 대신 C의 array 보다 메모리를 더 많이 필요로 한다는 단점이 있다.

numbers = [10, 20, 30, 40, 50]
numbers.pop(3) # 40 / 3번째 인덱스 값 리턴 후 삭제
for number in numbers:
	print(number) # 10, 20, 30, 50

Java

• 자바는 배열과 리스트를 모두 지원하고, 두 가지가 완전히 분리되어 있다.
• 배열은 배열의 장점이, 리스트는 리스트의 장점이 있기 때문에 개발자가 원하는대로 직접 선택가능하다.
• java는 javascript, python에 비해서 자료구조에 대해 더 알아야 할 필요성이 있지만,
  그만큼 개발자에게 더 큰 자유도가 주어진다.
• 자바는 2가지 형태의 리스트를 지원한다.
  • LinkedList / ArrayList
  • 똑같은 기능(메소드)를 가진 리스트가 2가지 존재한다.
  • 각각의 장단점이 분명하다.

// 배열 - 추가, 삭제가 어렵다. 직접 구현해야한다.
int[] numbers = {10,20,30,40,50};

// 리스트 (ArrayList)
ArrayList numbers = new ArrayList();

numbers.add(10); // 추가
numbers.remove(0); // 삭제

// 리스트 (LinkedList)
LinkedList numbers = new LinkedList();

numbers.add(10); // 추가
numbers.remove(0); // 삭제

Java - ArrayList / LinkedList

• Java에서는 배열 (array) 이외에 ArrayList와 LinkedList 2종류의 리스트를 제공한다.
• 인덱스를 이용해서 데이터를 가져오는 것이 빈번하다면 내부적으로 배열을 이용하는 ArrayList가 훨씬 빠르다. 하지만 데이터의 추가/삭제가 빈번하다면 LinkedList가 훨씬 효과적이다.
• 이와같이 처리하고자 하는 데이터에 따라서 어떤 데이터 스트럭쳐를 선택할지를 잘 판단하는 것은 대규모 시스템을 구축하는데는 필수적인 능력이다.
• 이러한 판단을 하기 위해서는 직접 데이터 스트럭쳐를 구현해서 사용하지 않더라도 내부적인 메커니즘을 이해할 필요가 있다.

Array List

• Array List는 배열을 이용해서 리스트를 구현한 것을 의미한다.
• 장점 : 내부적으로 배열을 사용하기 때문에 인덱스를 이용해서 접근하는 것이 빠르다.
• 단점 : 데이터의 추가와 삭제가 느리다.

데이터의 추가

• Array List는 내부적으로 데이터를 배열에 저장한다. 배열의 특성상 데이터를 리스트의 처음이나 중간에 저장하면, 이후의 데이터들이 한칸씩 뒤로 물러나야한다.

데이터의 삭제

• 삭제도 추가와 유사하게 빈자리가 생기면 빈자리를 채우기 위해서 순차적으로 한칸씩 땡겨야 한다.

데이터 조회(가져오기)

• 인덱스를 이용하여 데이터를 가져오고 싶을 때 Array로 구현한 리스트는 속도가 매우 빠르다. (메모리 상의 주소를 정확하게 참고해서 가져오기 때문이다.)

오늘 할 일 (계획)

• 컴퓨터 공학 입문 수업 듣기
• 수업내용 복습하고 노트 정리하기
• 알고리즘 문제 풀기 (재귀호출 사용하여 리팩토링)

오늘 한 일 (회고)

• 컴퓨터공학 입문 수업을 들었다.
  • linked list 를 node를 사용하여 구현해보았다.
  • stack, queue를 python의 list를 사용하여 구현해보았다.
• array, list에 대해서 복습하고 강의 노트를 정리했다.
• 패스트캠퍼스 컴퓨터 공학 입문 수업을 듣기로 결정했다. 수업을 통해서 python을 깊게 이해하고 Django를 능숙하게 다룰 수 있었으면 좋겠다. (만들고 싶은게 생겼는데 하나씩 천천히 해봐야지!)

내일 할 일

• 컴퓨터공학 입문 수업 듣기
• 재귀호출을 사용한 binary search 구현방법 복습
• linked list, stack, queue 복습
• stack, queue node 개념을 활용하여 구현해보기

패스트캠퍼스 컴퓨터공학 입문 수업을 듣고 중요한 내용을 정리했습니다. 개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.

O(n^2)의 성능을 가진 버블정렬, 삽입정렬, 선택정렬에 대해서 알아본다.

• 파이썬으로 정렬 알고리즘 구현하기

bubble sort (버블정렬)

• 인접한 두 원소를 검사하여 정렬하는 방법
• 시간복잡도가 (Big O) O(n^2)로 상당히 느리다. 하지만 코드가 단순하기 때문에 자주 사용된다.
  • 최악의 경우 100개의 데이터가 있을 때 연산을 10,000번 할 수 있다.
• 참고글 - 정렬(Sorting) 알고리즘 O(n^2)
• 참고글 - 정렬알고리즘
• 참고글 - 버블정렬 쉽게 정리하기

구현 1 (버블정렬)

def BubbleSort(li):
    list_length = len(li)

    #length가 4라면
    #바깥 루프는 3번 돌아야 하므로
    #range()는 0, 1, 2까지 즉 range(3)이 되야 하므로
    #range(list_length-1)이 되어야 한다.
    for i in range(list_length-1):
        #안쪽 루프는 1번당 3-> 2-> 1
        #즉 range(4 - 0 - 1) ->
        #range(4 - 1 - 1) ->
        #range(4 - 2 - 1)
        #range(list_leng - i - 1)
        for j in range(list_length-i-1):
            #만약 앞에 있는 값이 크다면 두 개를 교환
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]


if __name__ == "__main__":
    li = [2, 3, 1, 4]
    BubbleSort(li)
    print(li)

def bubble_sort(li):
    length = len(li) - 1
    for i in range(length):
        for j in range(length-i):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]

if __name__ == "__main__":
    li = [10,2,3,4,1,7,0]
    bubble_sort(li)
    print(li)

구현 2 (버블정렬)

• 구현 1 보다 불필요한 반복이 추가된다. (이미 정렬된 부분에 대한 비교)

import unittest

def bubblesort(alist):
    for i in range(len(alist)-1):
        for j in range(len(alist)-1):
            if alist[j] > alist[j+1]:
                alist[j], alist[j+1] = alist[j+1], alist[j]
    return alist


class unit_test(unittest.TestCase):
    def test(self):
        self.assertEqual([1,2,3,4,5,6], bubblesort([4,6,1,3,5,2]))

if __name__=='__main__':
    unittest.main()

selection sort(선택정렬)

• 최소값을 선택하는 과정을 반복해서 선택 정렬이라 부른다고 한다.
• 위키백과
  1. 주어진 리스트 중에 최솟값을 찾는다
  2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass))
  3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

구현 1 (선택정렬)

#맨 왼쪽부터 하나씩 최소값을 선택(selection)해 채운다

def selection_sort(li):
    for i in range(len(li)-1):
        min_idx = i
        for j in range(i+1, len(li)):
            if li[min_idx] > li[j]:
                min_idx = j
        if min_idx != i:
            li[i], li[min_idx] = li[min_idx], li[i]
    return li

if __name__ == "__main__":
    li = [4, 6, 1, 7, 2, 8, 3, 5, 9, 10, 12, 11]
    SelectionSort(li)
    print(li)

구현 2 (선택정렬)

• 구현 1의 방식이 더 일반적이다.

def selection_sort(li):
    for i in range(len(li)-1):
        for j in range(i+1, len(li)):
            if li[i] > li[j]:
                li[i], li[j] = li[j], li[i]
    return li

if __name__ == "__main__":
	li = [4, 6, 1, 7, 2, 8, 3, 5, 9, 10, 12, 11]
	selection_sort(li)
	print(li)

구현 3 (선택정렬)

• unittest 를 활용한다.

# 풀이 3

import unittest

def selection_sort(li):
    for i in range(len(li)-1):
        min_idx = i
        for j in range(i+1, len(li)):
            if li[min_idx] > li[j]:
                min_idx = j
        li[i], li[min_idx] = li[min_idx], li[i]
    return li

class unit_test(unittest.TestCase):
    def test(self):
        self.assertEqual([1, 2, 3, 4, 5, 6], selection_sort([4, 6, 1, 3, 5, 2]))
        self.assertEqual([1, 2, 3, 4, 5, 6], selection_sort([6, 4, 3, 1, 2, 5]))
        self.assertEqual([1, 2, 3, 4, 5, 6], selection_sort([6, 5, 4, 3, 2, 1]))

if __name__ == '__main__':
    unittest.main()


#----------------------------------------------------------------------
# Ran 1 test in 0.000s
# OK

insertion sort(삽입정렬)

• 작은 원소를 골라 앞쪽부터 정렬
• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
• 최악의 경우 O(n^2)의 시간복잡도를 가진다.
• 하지만 안쪽 루프에 군더더기가 없기 때문에 삽입 정렬을 입력 크기가 작을 때는 빠른 내부 정렬 알고리즘이다.

31 25 12 22 11 처음 상태

31 [25] 12 22 11 두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.

<25> 31 [12] 22 11 세 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.

<12> 25 31 [22] 11 네 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.

12 <22> 25 31 [11] 마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다.

<11> 12 22 25 31 종료.

구현 1(삽입정렬)

def insertion_sort(li):
    for i in range(1, len(li)):
        j = i - 1
        key = li[i]
        while li[j] > key and j >= 0:
            li[j+1] = li[j]
            j = j -1
        li[j+1] = key
    return li

if __name__ == "__main__":
	li = [4, 6, 1, 7, 2, 8, 3, 5, 9, 10, 12, 11]
	insertion_sort(li)

구현 2(삽입정렬)

#이미 정렬되어 있는 배열에 데이터를 삽입(insertion)한다고 하여 InsertionSort
def InsertionSort(li):
    list_length = len(li)

    for i in range(1, list_length):
        unsortedData = li[i]
        properIdx = 0

        for j in range(i-1, -1, -1):
            if li[j] > unsortedData:
                li[j+1] = li[j]
            else:
                properIdx = j+1
                break

        li[properIdx] = unsortedData

if __name__ == "__main__":
    li = [2, 5, 7, 3, 6, 1, 4, 8]
    InsertionSort(li)
    print(li)

문제출처

문제

수학을 공부하던 민지는 재미있는 사실을 발견하였습니다. 그 사실은 바로 연속된 자연수의 합으로 어떤 숫자를 표현하는 방법이 여러 가지라는 것입니다. 예를 들어, 15를 표현하는 방법은 (1+2+3+4+5) (4+5+6) (7+8) (15) 로 총 4가지가 존재합니다. 숫자를 입력받아 연속된 수로 표현하는 방법을 반환하는 expressions 함수를 만들어 민지를 도와주세요. 예를 들어 15가 입력된다면 4를 반환해 주면 됩니다.

풀이

def expressions(num):
    answer = 1
    for i in range(1,num//2+1):
        test_sum = i
        for j in range(i+1, num//2+2):
            test_sum += j
            if test_sum > num:
                continue
            if test_sum == num:
                answer += 1

    return answer


# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(expressions(15));

다른사람 풀이

def expressions(num):
    answer = 0
    for i in range(1, num + 1):
        s = 0
        while s < num:
            s += i
            i += 1
        if s == num:
            answer += 1

    return answer


# 아래는 테스트로 출력해 보기 위한 코드입니다.
print(expressions(15));

배운점

• for문의 중첩보다 for문 안에 while문을 사용하면 속도가 더 빠른 것 같다.