[ SWEA ] SW 문제해결 기본 - Array 2 (2차원 배열)

하루입니다.

 

 

---

 

 

1. 2차원 배열

• 2차원 배열은 세로길이(행 갯수), 가로길이(열 갯수)를 필요로 한다.

 

 

1-1.Array 순회

• Array가 n행 m열이라고 할 때, n*m 개의 모든 원소를 빠짐없이 조사하는 방법이다.

1. 행 우선 순회 : 행을 우선으로 배열의 원소를 조사한다.     이중반복문으로 구현한다.

2. 열 우선 순회 : 열을 우선으로 배열의 원소를 조사한다.

3. 지그재그 순회 : 첫 행은 우측으로, 다음 행은 좌측으로 진행하여 Array의 원소를 조사한다.

 

 

 

1-2. 델타를 이용한 2차 배열 탐색

• 2차 배열의 한 좌표에서 네 방향의 인접 배열 요소를 탐색할 때 사용한다.
• 델타란 ? 한 좌표에서 네 방향의 좌표와 x, y의 차이를 저장한 배열이다.

 

 

1-3. 전치행렬

• 행과 열의 값이 반대인 행렬이다. 
• 주의점 : 모든 좌표에 대해 행과 열의 값을 바꾸면 본래의 모습으로 되돌아 온다. (그럼 어떻게 하라는 거지? 주황선 기준 위에 것만 바꾸고 이런 식으로 진행하는 건가?)

 

 

---

 

 

2. 부분 집합

2-1. 부분 집합의 합

• 유한 개의 정수로 이루어진 집합이 있을 때, 이 집합의 부분 집합 중 그 집합의 원소를 모두 더한 값이 0이 되는지를 알아내는 문제이다.
• 만약 {1, 2, 3, -3, 4} 가 있다면, {3, -3}의 결과는 3 + (-3) 이 되므로 답은 true이다.
• 완전 검색기법 : 모든 부분 집합 생성 후 => 각 부분 집합의 합을 계산한다.
•                           : 집합의 원소가 n개라면, 공집합 포함 2^n개이다. (원소가 4개라면 16가지)

 

2-2. 부분 집합 문제 알고리즘

• 반복문을 이용하여 확인하고 부분 집합을 생성한다. 

 

 

 

 

Bit연산자

• 0,1로 이루어진 이진수에 대한 연산을 수행하는 연산자이다. 
• &는 bit 단위로 and 연산을, |는 bit 단위로 or 연산을, <<는 피연산자의 bit 열을 왼쪽으로 이동, >>는 피연산자의 bit열을 오른쪽으로 이동시킨다.

 

 

<< 연산자

 

& 연산자

 

 

 

 

---

 

 

3. 검색

검색이란 저장된 자료 중 원하는 항목을 찾는 작업이다. 

 

3-1. 검색의 종류

순차검색

• 일렬로 되어있는 자료를 순서대로 검색한다.
• 배열, 연결 리스트 등 순차구조로 구현된 자료구조에서 유용한다.
• 구현이 쉽고 직관적이지만, 검색 대상이 많은 경우 수행시간의 증가로 비효율적이다.
• 시간복잡도 : O(n)
•                      : 첫번째 원소를 찾을 때는 1번 비교, 두번째는 2번 비교 ... 

 

정렬되지 않은 자료의 검색 과정

1. 첫 번째 원소부터 순서대로 key값이 같은 원소가 있는지를 비교하여 찾는다.
2. key값이 동일한 원소를 찾으면 그 원소의 index를 반환한다.
3. 자료구조의 마지막까지 검색 대상을 찾지 못하면 검색 실패이다.

 

 

정렬된 자료의 검색 과정

1.  (자료가 오름차순으로 정렬되었다고 가정) 자료를 순차적으로 검색하며 key값을 비교한다.
2. 원소의 key값이 검색대상의 key값보다 크면 원소가 없다는 것이므로 검색을 종료한다.

• 정렬되어 있으므로, 검색 실패를 반환한다면 평균 비교 회수가 반으로 줄어든다.

 

 

 

이진검색

• 효율적인 검색 방법
• 자료의 가운데에 있는 항목의 key값과 비교 후 다음 검색 위치를 결정한다.
• 목적 key를 찾을 때까지 검색 범위를 반으로 줄여가며 빠르게 검색을 수행한다.
• 전제조건 : 자료가 정렬된 상태여야 한다.
•                  : 자료에 삽입이나 삭제가 발생했을 때, 항상 정렬된 상태로 있어야 한다. 재귀함수 사용?

 

이진 검색의 검색 과정

1. 자료의 중앙에 있는 원소를 선택한다.
2. 중앙 원소의 값과 찾고자 하는 목표값을 비교한다.
3. 목표값이 중앙원소값보다 크다면 : 자료의 왼쪽 반에 새로 검색을 수행한다.
4. 목표값이 중앙원소값보다 작다면 : 자료의 오른쪽 반에 새로 검색을 수행한다.
5. 1-4 과정을 반복한다.

 

 

 

인덱싱 (indexing)

• 데이터베이스에서 유래했다.

 

---

 

4. 정렬

4-1. 셀렉션 알고리즘

• 저장된 자료로부터 k번째로 큰 / 작은 원소를 찾는 방법이다.
• 최소값, 최댓값, 혹은 중간값을 찾는 알고리즘이다.
• 정렬 알고리즘을 사용하여 자료 정렬 후 ==> 원하는 순서에 있는 원소를 가져온다.

 

예시

• k번째로 작은 원소를 찾는 알고리즘
• 1번부터 k번째까지 작은 원소를 찾아 배열의 앞쪽으로 이동시키고, 배열의 k번째를 반환한다.
• 시간복잡도 : O(kn)

 

 

4-2. 선택 정렬

• 주어진 자료 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식이다.
• 셀렉션 알고리즘을 전체 자료에 적용한 것이다.
• 시간복잡도 : O(n^2)

 

순서

1. 주어진 리스트 중 최소값 찾기
2. 그 값을 리스트 맨 앞 값과 교환
3. 맨 처음 위치 제외한 나머지 리스트를 대상으로 위 과정 반복