[딩코딩코 2025 코딩테스트 필수 알고리즘] - 1. 최댓값, 최빈값

본 글에 사용된 코드와 이미지의 일부는
딩코딩코 님의 『38군데 합격 비법, 2025 코딩테스트 필수 알고리즘』 강의를 참조하여 발췌·활용하였습니다.

[본 게시물은 파트너스 활동의 일환으로 소정의 수수료를 받을 수 있습니다.] https://inf.run/tXMrp

---

알고리즘은 코딩테스트를 위해 항상 준비해야지 하는 마음이 있었지만, 다른 것을 공부해야 한다고 계속 미뤄왔다. 제목이 “알고리즘과 친해지기” 인 만큼 알고리즘과 친해지고 코테를 통과할 수 있을 만큼 성장했으면 좋겠다.

본격적으로 1주차 강의를 시작해보자.

---

알고리즘과 친해지기 - 최댓값 찾기

문제 링크 - https://www.acmicpc.net/problem/2562

문제

Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 이 배열 내에서 가장 큰 수를 반환하시오.

[3, 5, 6, 1, 2, 4, 3, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 43, 5, 6, 1, 2, 4]

---

풀이

우리는 눈으로 어떤 숫자가 제일 큰 수인지 파악할 수 있다. 하지만 컴퓨터한테 이해시키기 위해서는 코드로 이해시켜야 한다.

딩코딩코님은 무작정 코드를 쓰기보다는 어떻게 하면 정답을 찾아낼 수 있을지에 대해서 아이디어를 글로 한번 써본 다음에 코드를 작성하는게 좋다고 했다.

그럼 위와 같은 문제를 해결하기 위해 어떻게 풀면 좋을까?

1. 하나의 원소를 다른 원소들과 비교해서 최대값인지 분석하는 방법
2. 하나의 변수를 잡아서 그 변수와 비교하며 가장 큰 수를 찾는 방법

두 가지 방법이 있을 수 있다.

첫 번째 방법

첫번째 방법은 아래와 같다.

1. 3 → 5,6,1,2 … 비교
2. 5 →6,1,2… 비교
3. 6 → 1,2 … 비교

동작 방식은 아래와 같다.

1. 배열에서 숫자를 순회한다.
2. flag 변수를 선언한다.
3. 숫자 비교를 위해 이중 for 문을 순회한다.
4. 첫 숫자와 이후 숫자를 비교한다.
   1. 비교하는 숫자가 크면 flag 변수는 False
   2. 원래 숫자가 크면 flag 변수는 True
5. flag 변수가 True 면 반환한다.

이 방법으로 코드를 작성해보자.

def find_max_num(array):
	for num in array:
		is_max_num = True
		for compare_num in array:
			if(num < compare_num):
				is_max_num = False
		if is_max_num:
			return num
			
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))

비교하기 위해서 배열의 값들을 하나씩 돌아가는 작업들을 순회한다, Iterate 한다라고 표현한다. 파이썬에서 Iterate 하는 기본적인 코딩 방식 for 문을 이용해서 arrary 에서 뽑아오는 방식이다. 여기서 is_max_num 은 flag 변수 로 특정 사실에 대한 여부를 저장하기 위한 변수이다.

두 번째 방법

두번째 방법의 예는 아래와 같다.

max_num = 3 이라고 가정 후 ,다음 숫자 5를 max_num 이랑 비교 → 5 > 3 → max_num = 5 이런식으로 반복하면 된다.

동작 방식은 아래와 같다.

1. 가장 큰 수를 저장할 변수를 만듬
2. 배열을 순회하면서 변수와 비교
3. 비교한 변수의 값이 더 크면 큰 수를 저장할 변수에 대입

위 방법으로 코드를 작성해보자.

def find_max_num_2(array):
   max_num = array[0]
   for num in array:
       if num > max_num:
           max_num = num
   return max_num
   
print("정답 = 6 / 현재 풀이 값 = ", find_max_num2([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num2([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num2([6, 9, 2, 7, 1888]))

---

알고리즘과 친해지기 - 최빈값 찾기

 

문제 링크 - https://school.programmers.co.kr/learn/courses/30/lessons/120812

 

문제 설명

Q.  다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오. **(단 최빈값을 가진 알파벳이 여러개일 경우 알파벳 순서가 가장 앞에 위치한 알파벳을 출력하시오)
"hello my name is dingcodingco"**

 

풀이

문제를 풀기 전에 몇가지 알고 들어가자.

먼저 문자인지 확인하는 방법이다. 파이썬의 내장 함수 str.isalpha() 를 이용하면 해당 문자열이 알파벳인지 확인할 수 있다.

다음으로 알파벳 별로 빈도수를 리스트에 저장하는 방법이다.

1. 알파벳 별 빈도수를 저장하기 위한 길이가 26인 0 으로 초기화된 배열을 만든다.
   • alphabet_occurrence_array = [0] * 26
2. a 일 때는 0번째 원소에 1을 추가한다.
   • 아스키코드(컴퓨터가 표현할 수 없는 정보를 컴퓨터에 저장하는 방법으로 문자를 숫자들로 표) 사용
   • ord() 함수 사용
     • print(ord(’a’)) = 97
     • print(ord(’b’)) = 98
     • print(ord(’a’) - 97) = 0
     • print(ord(’A’)) = 65

마지막으로 chr() 함수이다. chr() 은 숫자를 문자로 변환해주는 함수이다.

이제 위 힌트를 사용해서 문제를 풀어보자.

첫 번째 방법

1. 각 알파벳마다 문자열을 돌면서 몇 글자가 나왔는지 확인한다.
2. 그 숫자가 저장한 알파벳 빈도 수보다 크다면, 그 값을 저장하고 제일 큰 알파벳으로 저장한다.
3. 이 과정을 반복하다보면 가장 많이 나왔던 알파벳을 알 수 있다.

def find_max_occurred_alphabet(string):
    alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s",
                      "t", "u", "v", "x", "y", "z"]
    max_occurrence = 0
    max_alphabet = alphabet_array[0]

    for alphabet in alphabet_array:
        occurrence = 0
        for char in string:
            if char == alphabet:
                occurrence += 1

        if occurrence > max_occurrence:
            max_alphabet = alphabet
            max_occurrence = occurrence

    return max_alphabet

print("정답 = i 현재 풀이 값 =", find_max_occurred_alphabet("hello my name is dingcodingco"))
print("정답 = e 현재 풀이 값 =", find_max_occurred_alphabet("we love algorithm"))
print("정답 = b 현재 풀이 값 =", find_max_occurred_alphabet("best of best youtube"))

두 번째 방법

1. 각 알파벳의 빈도수를 리스트에 저장한다.
2. 각 문자열을 돌면서 해당 문자가 알파벳인지 확인한다.
3. 알파벳을 인덱스 화 시켜 각 알파벳의 빈도수를 업데이트 한다.
4. 이후 , 알파벳의 빈도수가 가장 높은 인덱스를 찾는다.

def find_max_occurred_alphabet(string):
    alphabet_occurrence_array = [0] * 26

    for char in string:
        if not char.isalpha():
            continue
        arr_index = ord(char) - ord('a')
        alphabet_occurrence_array[arr_index] += 1

    max_occurrence = 0
    max_alphabet_index = 0
    for index in range(len(alphabet_occurrence_array)):
        alphabet_occurrence = alphabet_occurrence_array[index]
        if alphabet_occurrence > max_occurrence:
            max_occurrence = alphabet_occurrence
            max_alphabet_index = index

    return chr(max_alphabet_index + ord('a'))

result = find_max_occurred_alphabet
print("정답 = i 현재 풀이 값 =", result("hello my name is dingcodingco"))
print("정답 = e 현재 풀이 값 =", result("we love algorithm"))
print("정답 = b 현재 풀이 값 =", result("best of best youtube"))

이렇게 두 가지 풀이 방법을 알아봤다. 여기서 드는 의문점은 “그럼 어떤 게 효율적일까?” 라는 점이다.

그걸 알기 위해서는 시간 복잡도 & 공간 복잡도를 알면 해결 된다.

시간 복잡도 와 공간 복잡도에 대해서 알아보자.