[알고리즘] 코드트리 알고리즘 입문 - 행복한 수열의 개수

알고리즘, 기초부터 다시

2학기 개강을 맞이하여 매주 동아리에서 진행하는 알고리즘 스터디의 진도를 개편하였다.

원래는 [파이썬 알고리즘 인터뷰]란 책을 교재로 두고, 일주일치 진도를 집에서 공부 후 노션에 기록, 만나서는 백준 두 문제 정도 푸는 루틴이었는데,

스터디장 형님을 제외하고는 나머지 셋이 모두 코린이 수준이었기 때문에 따라가는 것도 벅찼을 뿐더러 진도를 나가도 공부 내용이 완벽히 흡수되지 않아 공부의 효율이 떨어지는 문제가 있었다.

그래서 알고리즘과 자료구조 기초에 대한 갈증이 있던 와중에 학교에서 제휴를 맺은 코드트리 서비스를 활용하자는 아이디어가 나왔고 현재 채택하여 진행하기 시작했다.

사실 지금 내 실력을 0부터 100 사이에 점 찍어보라 하면 20도 안되는 상태고, 또한 자료구조와 알고리즘을 공부해야할 당장의 필요성도 못느끼는 단계이지만, 이번 학기에 자료구조 수업을 듣거니와 이왕 매주 스터디하는데 미리 공부하고 또 제대로 하는 것이 낫겠다는 생각에 많이는 아니어도 조금씩 제대로 알고리즘과 자료구조를 공부해보겠다 다짐했다. 뭐 나중에 일찍 시작하길 잘했다고 생각하는 날이 오지 않을까? ㅋㅋ

---

행복한 수열의 개수

https://www.codetree.ai/missions/2/problems/number-of-happy-sequence/description

내 풀이

n, m = map(int, input().split())
grid = []
for _ in range(n):
    line = list(map(int, input().split()))
    grid.append(line)

def find_sequence():
    sequence = []
    sequence.extend(grid)
    for i in range(n):
        col = []
        for row in grid:
            col.append(row[i])
        sequence.append(col)
    #print(sequence)
    answer = 0
    for line in sequence:
        #print('line')
        #print(line)
        for idx, val in enumerate(line):
            #print(idx, val)
            if idx + m - 1 >= n:
                #print('continue')
                continue
            #print(str(val) * m)
            #print(''.join(str(ele) for ele in line[idx:idx+m]))
            #print(str(val) * m in ''.join(str(ele) for ele in line[idx:idx+m]))
            if str(val) * m == ''.join(str(ele) for ele in line[idx:idx+m]):
                answer += 1
                #print(f"added, answer:{answer}")
                break 
    return answer

print(find_sequence())

위 문제를 풀긴 풀었다. 근데 모범답안과 비교한다면 여전히 알고리드믹하지 않은 풀이긴 하다.

난 3x3 행렬 중 열에 접근하는 방법을 몰라 함수 처음부터 열을 행으로 바꿔주는 작업을 거쳤다.

그렇게 2n개의 행을 만든 다음 각 행의 첫 숫자마다 m개 씩 이어붙인 '문자열'을 만들어 해당 인덱스 위치에 있는 m개 길이 수열과 비교하여 같을 때마다 정답 카운트를 1씩 증가시켜줬다.

모범답안의 풀이는 나처럼 문자열 비교를 하지 않고, 행의 모든 숫자에 대하여 연속되는 숫자의 최대값을 계산하여 그것이 조건 m개 이상일 경우 true를 반환해주는 함수를 짰다.

---

하루에 4문제씩 풀려고 했는데, 2문제 풀면 더 이상 시간이 없을 듯 하다. 그만큼 내가 알고린이(?)라는 뜻... 풀 때마다 고통스럽고 풀기 싫은데 푼 순간에는 다행이 재미를 느낀다. 알고리즘 거북이 기어갑니다 엉금엉금 🐢