1. 알고리즘의 기본 이해

1. 알고리즘의 기본 이해

알고리즘을 배우는 이유

-> 컴퓨터를 가지고 문제를 해결하기 위해서는 데이터를 받아들여서 가공하여 우리가 원하는 결과로 출력하는 과정을 거친다.
이 과정에서 우리는 컴퓨터 프로그램을 사용하여 문제를 해결하는데 이때 컴퓨터가 이해할 수 있는 프로그래밍 언어를 사용해야 한다.
프로그래밍 언어로 프로그램을 작성하기 위해서는 논리적이고 정형화된 방법으로 표현해야 하고 그 표현법이 바로 알고리즘이다.
알고리즘 설계방법은 그리디, 분할정복, 동적계획 등이 있다.

알고리즘이란?

주어진 문제를 출기 위한 논리적인 절차나 방법이며 프로그램에서 실행 명령어의 순서를 의미한다.

알고리즘의 특성

• 효율성, 정확성, 수행성, 유한성

알고리즘의 표현법

• 자연어, 순서도, 의사코드, 프로그래밍 언어
• 순서도
  기호로 알고리즘의 절차를 표현한 것이다.
  순서도를 사용함으로써 프로그램을 쉽게 이해할 수 있으며 오류를 찾기 수월하고 프로그램을 보관하기 용이하다.
• 순서도 종류
  1) 시스템 순서도 : 자료의 프름을 중심으로 전체의 작업 내용을 도식화한것
  2) 프로그램 순서도: 개략 순서도: 프로그램 전체의 내용을 나타낸 순서도
• 상세 순서도: 코딩시 바로 실행 될 수 있도록 상세하게 그려진 순서도

---

2. 알고리즘의 기술언어

알고리즘의 구성요소에는 변수, 지정문, 함수가 있다.

변수와 지정문

변수란?

변수란 데이터를 저장하는 메모리 공간의 이름이다.
정수, 실수, 참거짓, 문자를 사용한다.
변수를 사용하기 위해선 선언과 초기화가 필요하다.

• 선언: 변수의 사용목적(자료형, 정수 등) 과 이름을 부여하는 과정
• 초기화: 변수가 들어갈 공간을 청소하는 것이다.

지정문(for , while)

* for 문 반복 횟수가 명확할때 사용한다.
-> 문자열, 리스트, 튜플이 들어갈때 안에 있는 요소를 하나씩 반복한다.

 

for 변수 in 문자열(리스트, 튜플):
ex) 음식의 종류 나열, 5명의 시험 점수 합격,불합격 판별

 

* while문 : 반복횟수가 명확하지 않을때 사용한다.
조건식을 기준으로 참이면 반복적으로 수행하고 거짓이면 while문에서 벗어난다.

배열

배열이란 같은 데이터 형태를 모아놓은 집합체다.
차원에 따라 다차원으로 배열도 가능하다( 행렬 형태)

함수

데이터가 주어지면 이를 처리해서 원하는 결과를 얻게 하는 명령어의 집합
표준 라이브러리 함수과 사용자 정의 함수가 있다.

---

3. 선형구조

배열과 리스트

배열

배열은 동일한 자료형의 데이터를 여러개 저장하기 위해 한번에 많은 공간을 만들고 사용하는 일반적인 자료구조다.
배열은 차례대로 순차처기 되기 때문에 데이터를 삽입하거나 삭제하면 전체 데이터를 움직여야 한다.

ex) A 배열에 1,2,3,4,5,6 이 있고 1과 2사이에 10을 삽입한 경우 -> 1,10,2,3,4,5,6 으로 전체 데이터 뒤로 이동
3을 삭제 하고 싶은 경우 1,2,4,5,6으로 전체 데이터가 이동!

이 단점을 보완하기 위해서 리스트 등장!

리스트

데이터를 임의의 공간에 저장하고 포인터를 사용해서 서로 연결시킨 구조다.
자료의 삽입, 삭제가 쉽고 비 연속적이라 서로 분리가 가능하다.
하지만, 포인터를 위한 공간이 필요하고 중간에 노드가 끊기면 다음 노드 찾기 힘들다.

& 리스트 종류

• 1) 단순연결 리스트(singly linked list)
  

  

  
  출처: https://daimhada.tistory.com/72

 

• 2) 이중 연결 리스트(doubly linked list)
  이중 연결 리스트는 단순연결리스트에 PREV를 가르키는 포인터 공간이 추가 되어서 이전 노드에 대한 정보를 알 수 있다.

출처: https://daimhada.tistory.com/99?category=820522

 

• 3) 원형연결 리스트(Circular linkked list)
  리스트의 앞뒤가 연결되어 순환구조를 갖고 있다. 노드의 포인터는 한개일수도 두개일 수도 있으며 노드가 계속 이어진다는 것이 핵심이다

출처: https://daimhada.tistory.com/102

 

• * 4) 이중원형연결 리스트(doubly circular linked list)
  이중연결리스트와 원형 연결 리스트가 합처진 형태다.
  즉, 앞뒤 노드를 연결하는 두개의 포인터를 갖고 있으며 마지막 노드와 처음 노드는 서로를 가르킨다.

 

큐와 스택

 

큐

큐는 줄서기와 같다. 버스 정류장에서 가장 먼저 줄 선 사람이 가장 먼저 버스를 타는 것이다.(first in first out)
큐에 자료를 한개 집어넣는 것을 enqueue, 한개 꺼내는 것을 dequeue라고 표현한다.

스택

스택은 종이컵 꺼내기와 같다. 잘 쌓여진 종이컵을 꺼내는 상황을 생각해보자.
종잌컵을 꺼낼때 맨 위에 있는 종이컵 먼저 꺼낸다. 즉, 마지막에 들어간 종이컵을 가장 먼저 사용한다. (last in first out)
스택에서 자료를 집어넣는 동작을 push라고 하고 꺼내는 동작을 pop이라고 표현한다.