[ 자료구조 기초] 내가 뒤늦게 자료구조와 알고리즘 공부를 다시 하는 이유..

시작하게 된 동기..

그렇다... 나는 iOS 신입 개발자 취업 준비생이다..

어느 정도 해서는 취업이 안된다..신입에게 어느 정도의 수준을 요하는지 항상 채용공고를 볼 때면,,난감하다..

(사실 거의 신입 수준의 채용 자격 요건이 없다는 게 함정,,기본 3년 이상인듯하다..) 

이제는 코딩테스트로 채용하는 케이스들도 많이 생겨나는 것 같다.

나는 귀에 피날정도로 다들 입버릇 처럼 뱉어내는 비전공자다..완전 문과 어문학계열..(영어, 프랑스어..하지만 난 0개국어..)

 

비스무리한 이과 공학계열도 아니다..

코딩테스트를 위해서도 공부해야겠지만, 프로그래밍을 시작하고 개발자로서 업을 삼으려면 

알고리즘과 자료구조는 필요한 것이라고들 하더라.. ( 물론 이것 없이도 개발 잘하시는 현직자 분들도 많이 계실거라고 생각한다.) 

 

어찌 되었든,, 나는 뒤늦게 나마 다시 알고리즘과 자료구조를 시작하려고 하며, 이 글을 쓴다..

 

사설이 참 길었지만

 

 

자료구조의 중요성

자료구조란 무엇일까..?  데이터를 조직하는 방법이라 한다.

컴퓨터 코드를 작성하면 프로그래밍은 데이터를 주로 다루는 것임을 깨닫는다. 

데이터를 입력받아 조작, 그리고 반환

 

데이터 : 보통은 기초적인 수, 문자열로 이뤄져 있다한다.

x = "Hello!"
y = "How are you"
z = "today?"

print(x + y + z)

문자열 세 개를 하나의 메세지로 이어 출력하는 매우 간단한 프로그램

 

개발자가 추구해야 할 작업 마인드? 

단순히 데이터를 조직하는 방법이 아닌, 어떤 데이터 조직이 코드의 실행 속도에 미치는 영향이 다른지..큰지 파악 

 

기초 자료 구조 : 배열 

배열 : 단순 데이터 원소들의 리스트 

array = ["apples","bananas","cucumbers","dates","elderberries"]

• 배열의 인덱스는 특정 데이터가 배열의 어디에 있는지 알려주는 숫자임. 대부분의 프로그래밍은 인덱스가 0에서부터 시작인게 기본임 
  • apples 는 index 0 , elderberries 는 index 4임 
• 배열같은 자료 구조 성능 파악시 조건 : 
  • 코드가 자료 구조와 일반적으로 어떻게 상호 작용하는지 분석해야한다고 함
• 자료 구조의 4가지 방법 
  • 읽기 : 자료 구조 내 특정 위치를 찾아보는 것, 배열에서는 특정 인덱스의 값을 찾아보는 것을 뜻함 
  • 검색 : 자료 구조 내 특정 값 찾기. 배열에서는 특정 값이 배열에 들어 있는지, 만약 그렇다면 어떤 인덱스가 있는지 알아보는 것
  • 삽입 : 자료 구조 내 새로운 값 추가. 배열이라면 배열 내 슬롯을 더 만들어 새 값을 추가
  • 삭제 : 값을 제거. 배열 : 배열의 값 중 하나를 제거 

읽기

검색

삽입

배열의 처음 or 중간에 삽입하는 문제는 달라짐

• 중간이라면 그림과 같이 뒤에서 부터 인덱스 위치를 하나씩 하나씩 옮겨야함 
• 배열 삽입에서 최악의 시나리오 => 가장 많은 단계가 걸리는 시나리오 
  • 데이터를 배열의 맨 앞에 삽입할 때  : 배열 내 모든 값을 한 셀씩 오른쪽으로 옮겨야 하기 때문임
  • 원소 N 개 포함하는 배열에서 최악의 시나리오일 때 N+1 단계가 걸림

 

삭제는 삽입과 비슷하나 반대 방향임.

 

집합

• 집합 : 중복 값을 허용하지 않는 자료구조. 
  • 집합의 종류는 실제 다양하나 배열 기반 집합 내에서만 살펴볼거임 
  • 배열 기반 집합은 값들의 단순 리스트로 배열과 거의 흡사 , 배열 기반 집합과 일반적 배열 간 차이점은 집합은 중복 값의 삽입을 절대 허용하지 않음.
  • 집합은 중복 데이터가 없어야할 때 유용함

ex) 온라인 전화번호부를 만들 때 같은 번호 두 번 이상 나옴 안됨 

집합의 읽기,검색

배열읽기,검색과 똑같음 

집합의 삽입

배열과 다름. 배열에서 최선의 시나리오와는 반대로 집합의 맨 끝에 삽입하는 방법을 생각, 

• 배열 삽입:  컴퓨터 1단계로 값을 끝에 삽입
• 집합 삽입: 먼저 이 값이 이미 집합에 들어 있는지 결정해야함

집합 ["apples","bananas","cucumbers","dates","elderberries"] 일 때 "Pigs" 를 삽입하려면, 먼저 검색을 1번 수행 후 다음 단계 거쳐야 함 

1단계~5단계 : 인덱스 0 ~ 4에서 "Pigs" 검색  

6단계 : 없으면 마지막 집합의 끝에 "Pigs" 삽입 해야함 

 

[출처]: 누구나 자료구조와 알고리즘 - 도서 

누구나 자료 구조와 알고리즘 - 교보문고

[참고자료]: http://www.codenlearn.com/2011/07/simple-insertion-sort.html

A Simple Insertion Sort

 

reference : https://www.geeksforgeeks.org/data-structures/

Data Structures - GeeksforGeeks