무럭무럭 성장코딩

아무생각 없이 문제만 풀 수 있어서 참 좋은 별찍기...

중간중간 새로운 별 모양을 만들어 내면 갱신하도록 하자!

찍으려는 별모양을 각 코드 위에 주석처리 해놓았다.

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

이 문제는 2가지 방법으로 풀 수 있다.

1. 별 찍기하듯이

2. 델타 탐색

먼저, 문제에서 농작물을 수확할 수 있는 정사각형 마름모 형태의 별을 찍어보면,

이를 이용해 문제를 풀어보자. 농작물 수확해서 얻는 이익을 profit이라는 변수라고 하였다.

이번엔 델타 탐색을 통해 문제를 풀어보도록 한다.

먼저 N=5일때, 수확이 가능한 부분을 색칠해서 나타내면(노란색 부분)

N*N 2차원 배열의 중앙을 기준으로 생각해보자.

중앙을 기준으로 2칸 이동을 한 경우에만 수확이 가능함을 알 수 있다.

즉, 위로 두칸이든 위로 한칸 오른쪽 한칸이든 이동한 횟수 또는 칸수가 2이기만 하면 된다.

이를 이용해서 풀어보자.

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

델타 탐색을 이용하여 풀어본다.

숫자가 시계방향으로 이루어져 있으므로,

탐색 방향은 (오른쪽, 아래, 왼쪽, 위) 순서대로 반복될 것이다.

아래 N = 4일 경우, 달팽이의 모습을 보자.

N*N의 2차원 배열에서 원소 1이 존재하는 위치를 기준으로 탐색해나가면서 숫자를 입력해줘야 하는데,

중요하게 생각할 포인트는 "언제 방향을 바꾸는가" 이다.

처음 위치부터 생각해보자. 처음 위치(배열의 [0][0] 위치)에 1을 지정하고 시작하도록 한다.

처음위치에서는 아래 화살표 방향과 같이 오른쪽으로 탐색해 나가면서 숫자를 1씩 더해 입력한다.

그런데, 아래와 같이 4까지 입력하고 나면, 5를 입력하기 위해서는 탐색 방향을 오른쪽이 아닌 아래 방향으로 바꾸어야 한다.

일단 어떤 조건을 통해 방향을 바꾸었다고 가정하고, 진행해보면서 어느 지점에서 방향이 바뀌어야 하는지 살펴보면, 

1. 같은 방향으로 탐색시 다음 차례에서 배열의 범위를 벗어날 때,

2. 같은 방향으로 탐색시 다음 차례에 숫자가 존재할 때, (다음 차례에 숫자가 존재한다는 것을 어떻게 처리?)

이제, 각 조건에 대해 어떻게 코드를 작성할지 살펴보자.

1번 조건에 대해서는 다음 탐색 위치(인덱스)가 0이상이고 N-1을 초과하면 안되므로, 인덱스 값이 N보다 작아야 한다는 조건을 이용하도록 한다.

2번 조건에 대해서는 다음 탐색 위치에 숫자가 존재한다는 조건을 달기 위해 그 위치의 값이 0이면 방향을 바꾸어야 한다는 조건을 이용한다.(왜냐하면 int배열을 생성하면 기본적으로 원소들이 0이기 때문이다)

아래 코드와 주석을 살펴보자.

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

문제를 푸는 것에 있어서 가장 핵심은 배열의 index의 활용이다.

점수는 0점~100점, 점수들 중에서 최빈값을 구하는 것.

예를들어, 각 점수마다 임의로 빈도수를 나타낸다고 가정해보자.

0점 1점 2점 3점 4점 ...  98점 99점 100점

1번 4번 6번 2번 5번 ...  3번   20번     1번

위 두 줄을 보면 뭐가 떠오르는가? 

"배열의 원소와 각 원소에 대한 인덱스"

즉, 점수마다의 빈도수를 원소로 갖고, 인덱스 번호가 0부터 100까지 존재하는 배열을 이용하면 되지 않을까?라는 생각.

이제 작성한 코드를 살펴보자.

1. 첫번째 풀이(비효율적인 부분이 있으나 생각의 흐름이 모두 드러나있는 풀이)

2. 비효율적인 부분을 줄인 풀이

Binary Search란 정렬되어 있는 데이터에서 원하는 값을 찾는 방법이다.

대상 데이터의 중앙값과 찾고자하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 찾는데, 

이때 자료는 반드시 정렬된 상태여야 한다.(예를 들면, 오름/내림차순)

정렬방법에 대해 먼저, 대략적으로 얘기해보면,

1. 자료 중앙에 있는 원소를 고름

2. 중앙 원소의 값과 찾고자 하는 값을 비교

3. 찾고자 하는 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 데이터에 대해서 새로 탐색하고,

크다면 자료의 오른쪽 데이터에 대해 새로 탐색한다.

4. 이를 반복한다.

핵심은 탐색의 범위를 반복적으로 반으로 줄이는 것이다.

이제 자세히 알아보자.

오름차순으로 정렬된 배열 arr = {2, 4, 7, 9, 11, 19, 23}이 있고, 이중 7을 검색하려고 한다.

먼저, 배열의 중앙 원소는 9이다.

직관적으로 중앙 원소가 무엇인지 알 수 있긴 하나, 그 값을 찾는 방법을 다시 말하자면,

맨 처음 index = 0, 마지막 index = 배열의 길이 - 1이므로 중앙 원소가 존재하는 index는 (0+ 배열의 길이 - 1) / 2가 된다.

즉, 배열 arr는 배열의 길이가 7이므로 중앙 원소가 존재하는 index는 (7-1) / 2 == 3.

따라서 중앙값은 arr[3]인 9이다.

이제 중앙 원소의 값(9)과 찾고자 하는 값(7)을 비교해보자.

찾고자 하는 값이 중앙값보다 왼쪽에 있으므로, 중앙값의 왼쪽 데이터에 대해 새로 탐색해야 한다.

이제, 맨 처음 index는 0, 맨 마지막 index는 2가 됐다.

이때의 중앙값은 index 1의 위치의 값인 4가 된다.

중앙값(4)와 찾는 값(7) 중에서 찾는 값이 더 크므로,

즉 찾는 값이 중앙값보다 오른쪽에 있으므로, 중앙값의 오른쪽 데이터에 대해 새로 탐색해야 한다.

그런데, 탐색 범위가 인덱스가 2인 값뿐이고, 찾는 값과 중앙값이 일치하므로 탐색을 성공한 것이다.

이제 코드를 작성하여 알아보도록 하자.

위와 같은 순서로,

1. 탐색의 대상이 되는 자료들이 정렬되어 있는 배열 arr[low]부터 arr[high]사이에 들어있다고 하자.

 - 배열의 길이가 N이라고 하면, low는 0번 인덱스, high는 N-1번 인덱스이다.

2. 중간값의 인덱스를 mid라고 하자. 

 - mid == (low+high) / 2이다.

3. 찾는 값(key값)이 arr[mid]보다 큰지, 작은지를 비교한다.

 - key < arr[mid]: 찾는 값이 중간값의 왼쪽에 존재하는 경우이므로 high를 mid-1로 만든다.

 - key > arr[mid]: 찾는 값이 중간값의 오른쪽에 존재하는 경우이므로 low를 mid+1로 만든다.

 - key == arr[mid]: 찾는 값을 찾음. 중간값을 return해주면 됨

4. low > high가 될 때까지 반복하면서 key값을 찾는다. 

< 코드 작성++ >

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

풀이를 하면서, 문제를 푸는 것 외에 확장된 생각을 함께 정리한다.

문제를 푸는 흐름은

1. 최댓값, 최솟값을 구한다.

2. 배열의 원소들의 총 합에서 최댓값, 최솟값을 빼준다.

3. 뺀 결과를 8(전체 원소 개수 - 최댓값 1개 - 최솟값 1개)

라고 생각을 했고, 

출력을 위해서

1. int를 double로 형변환하기 위해 8로 나누는 것이 아닌 8.0(8.0은 double, 8.0f는 float이므로)으로 나눠줬다.

2. 소수점 첫째자리에서 반올림 하기 위해, 반올림 하기 위한 변수에 0.5를 더하고 int로 형변환하여 버림을 해줬다.

(예를 들어, 13.4라면 0.5를 더해 13.9가 되고, int형변환을 통해 13이 되지만,

13.5라면 0.5를 더해 14.0이 되고, int형변환을 통해 14가 되기 때문이다.)

그 Solution은 다음과 같다.

하지만, 

위의 생각에서 좀 더 자세히 파고들면,

최댓값과 최솟값을 각각 1개씩만 가지는 배열만 input 데이터에 포함되어 있다는 확신이 있는가? 라는 생각이 들게 된다.

즉, 어떤 배열이 {1,2,3,4,5,6}여서 최댓값이 6, 최솟값이 1이라고 했을 때, 위와 같은 Solution대로 결과를 출력할 수 있지만, 

어떤 배열이 {1,1,2,3,4,5,6,6}이라면 최댓값, 최솟값이 2개씩 존재하게 되므로 단순히 전체 배열 원소의 개수에서 2를 빼준 값을 통해 평균을 구하려고 접근해서는 안된다.

따라서, 아래 Solution은 최댓값, 최솟값이 중복해서 존재하는 경우 그 개수를 고려해준 결과이다.

위, 아래 둘다 동일한 출력 결과가 나타나지만, 이것은 input 데이터가 중복된 최댓값 혹은 최솟값이 존재하지 않았기 때문이었을 뿐이다. 

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

오름차순으로 정렬하는 것이므로 두 가지 방식으로 풀어보고자 한다.

1. 버블 정렬

2. 선택 정렬

Theme. 버블 정렬 Solution

Theme. 선택 정렬 Solution

선택 정렬(Selection Sort)는 배열의 원소 중에서 원하는 위치에 놓을 데이터를 찾아 선택하는 것

어떤 배열을 오름차순으로 정렬하고 싶다고 가정하고 설명하도록 한다.

int[] array = {5, 9, 1, 7, 2}; 인 배열 array가 있다고 하자.

정렬을 할 때마다 배열의 맨 앞부터의 위치들에 최솟값들이 하나씩 이동하게 되므로

이미 최솟값을 이동시킨 위치는 고려하지 않고, 그 다음 위치들 중에서 최솟값을 찾는다.

즉, 전체적인 과정을 설명하면,

1. 배열의 각 원소 중에서 최솟값을 찾고, 이를 array[0]과 자리를 바꾼다. (swap)

2. array[0]을 제외한 나머지 원소들 중에서 최솟값을 찾아 array[1]과 자리를 바꾼다.

3. array[2], array[3]....도 위의 방법대로 반복한다.

이때, (배열의 길이 - 1)만큼만 최솟값을 찾는 cycle을 진행하면 되는데, 

위의 예시에서 총 5개의 데이터 중에서 4개의 데이터를 정렬했다는 것은 이미 마지막 데이터는 정렬이 되었다는 의미이기 때문이다. (최솟값을 찾고 나머지 값들과 비교하여 정렬했으므로 2개씩 비교가 되었기 때문) 

이를 코드를 작성하여 비교해보자.

두 개의 인접한 원소(값)을 비교하여 정렬하는 것

버블 정렬에 대해 알아보기 위해 배열을 오름차순으로 나타내는 것을 기준으로 한다.

간단하게 말하면, 두개씩 값을 비교하고, 조건에 맞게 swap하는 것이다.

1. array[0]에서부터 비교(첫번째 cycle)

int[] array = { 1, 5, 9, 3, 7, 1, 0}; 인 배열 array을 오름차순으로 정렬하는 것을 예로 들어 설명하도록 한다.

먼저, array[0]과 array[1]을 비교했을 때, array[0] < array[1]이므로 swap할 필요가 없다.

같은 방식으로, array[1]와 array[2] 또한 swap할 필요가 없다.

이때, array[2] > array[3]이므로 두 원소를 swap해야 한다.

같은 방식으로 진행한 결과는 다음과 같다.

첫 번째 cycle 결과 배열 array는 { 1, 5, 3, 7, 1, 0, 9 }가 되었다.

2. 두번째 사이클

3. 세번째 사이클

4. 네번째 사이클

5. 다섯번째 사이클

6. 여섯번째 사이클

최종적으로 버블 정렬을 통해 오름차순 정렬을 한 결과는 {0, 1, 1, 3, 5, 7, 9}이다.

이제 코드를 작성하여 결과를 비교해보자.

동일한 결과가 나타난다. 

내림차순으로 정렬하는 경우는 오름차순 정렬과 같은 논의이므로 부등호의 방향만 달리하면 된다.

결과는 { 9, 7, 5, 3, 1, 1, 0}.

Theme. 배열의 최댓값/최솟값 구하기

1. 최댓값

먼저, 배열 arr = {1, 5, 9, 3, 7, 1, 0}이 있다고 하자.

결론부터 말하면 배열의 첫번째 값을 최댓값이라고 가정하고, 이후 index마다의 값들과의 비교를 통해 더 큰 값이 존재하면 그 값을 최댓값으로 대입해주며 배열의 끝까지 비교해보는 것이다.

이제 자세히 알아보자.

int max = array[0];을 통해 배열의 첫번째 값을 max(최댓값)라고 가정해보자.

이제, 배열의 첫번째 값과 두번째 값을 비교해보자.

그 결과 array[1]인 5가 더 크므로 max의 값에 5를 대입해준다.(최댓값이 5인 상태)

같은 방식으로 한번더 진행한 결과는, 다음과 같다.

array[2]인 9가 5보다 크기 때문에 max의 값에 9를 대입해준다.(최댓값이 9인 상태)

이후 진행상황은, 

배열의 끝까지 비교한 결과 최댓값은 최종적으로 9가 된다.

이제 코드를 작성하여 결과를 확인해보자.

최댓값은 9가 나온다. 

2. 최솟값

최댓값을 구하는 방식과 같은 논의이나 단, 부등호의 방향이 바뀌는 것뿐이다. 

최댓값을 구할 때와 동일한 배열을 가지고 최솟값을 구하는 코드를 작성해보면,

최솟값은 0이 나온다.

Theme. SWEA 2068. 최대수 구하기

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

< Solution >