문제 출처: 프로그래머스

문제 설명

🔎메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다.

이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

전형적인 dfs, bfs 문제였다.

maps와 그 원소들의 길이가 100이었고, 값이 'X' 또는 1~9사이 숫자로 조건도 완벽했다.

우선은 조금 더 친한 dfs를 통해서 문제를 해결하려고 시도했으나, 런타임 에러와 실패가 많이 떴다.

탐색 과정을 시각화해서 살펴봐도 내가 테스트한 케이스들에서는 잘 작동했다. 아마 탈출 조건에서 에러가 발생한 것 같지만, 아직까지 원인은 발견하지 못했다..

<틀린 코드 보기>

def solution(maps):
    answer = []
    r, c = len(maps), len(maps[0])
    maps = list(map(list, maps))
    visit = [[0]*c for _ in range(r)]
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

    def dfs(x, y, val):
        if visit[x][y] or maps[x][y] == 'X':
            return

        visit[x][y] = 1
        flag = 0

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < r and 0 <= ny < c and maps[nx][ny] != 'X' and not visit[nx][ny]:
                flag += 1
                dfs(nx, ny, val + int(maps[nx][ny]))

        if flag == 0:
            answer.append(val)


    for i in range(r):
        for j in range(c):
            if maps[i][j] != 'X':
                dfs(i, j, int(maps[i][j]))
    
    
    if answer:
        answer.sort()
        return answer
    else:
        return [-1]

그래서 bfs로 방향을 틀어 문제를 푸니까 맞았다.

<정답 코드>

from collections import deque
def solution(maps):
    answer = []
    r, c = len(maps), len(maps[0])
    maps = list(map(list, maps))
    visit = [[0] * c for _ in range(r)]
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

    def bfs(x, y):
        if visit[x][y] or maps[x][y] == 'X':
            return

        q = deque()
        q.append((x, y))
        visit[x][y] = 1
        val = 0
        while q:
            cx, cy = q.popleft()
            val += int(maps[cx][cy])

            for i in range(4):
                nx, ny = cx+dx[i], cy+dy[i]
                if 0 <= nx < r and 0 <= ny < c and not visit[nx][ny] and maps[nx][ny] != 'X':
                    q.append((nx, ny))
                    visit[nx][ny] = 1

        return val

    for i in range(r):
        for j in range(c):
            if maps[i][j] != 'X':
                life = bfs(i, j)
                if life:
                    answer.append(life)

    if answer:
        answer.sort()
        return answer
    else:
        return [-1]

접근은 아래와 같다.

1. 탐색이 좀 더 편하도록 maps의 원소를 list로 변환한다.
2. 문제에서 대각선을 포함하지 않았기 때문에, 대각선 방향을 제외한 4가지 방향을 dx, dy배열로 준비한다.
3. X가 아닌 지역에서 bfs를 수행한다. bfs를 마친 결과를 answer배열에 업데이트 한다.
4. answer 배열을 오름차순으로 정렬하여 return한다.

다시 보니 코드가 그렇게 깔끔하게 작성된 것 같진 않다. 

중복해서  점검하는 부분도 있는 것 같고, 좀 더 짧게 작성할 수 있었을 것 같다. 

문제 출처: 프로그래머스

문제 설명

🔎호텔을 운영 중인 코니는 최소한의 객실만을 사용하여 예약 손님들을 받으려고 합니다. 한 번 사용한 객실은 퇴실 시간을 기준으로 10분간 청소를 하고 다음 손님들이 사용할 수 있습니다.
예약 시각이 문자열 형태로 담긴 2차원 배열 "book_time" 이 매개변수로 주어질 때, 코니에게 필요한 최소 객실의 수를 return 하는 solution 함수를 완성해주세요.

오랜만에 난이도 순으로 풀지 않고 최신순으로 정렬해서 풀었는데, 이 문제가 처음에 있었고 정답률이 30퍼대라 잔뜩 긴장한 채로 문제에 들어갔다.

읽어보니 전에 카카오였는지 그냥 프로그래머스 문제였는지에서 주차 입출 관련 문제가 있었는데 이 문제랑 비슷했던 것 같다.

다행히 오늘은 머리가 좀 잘 돌아가는지 문제를 보자마자 Priority Queue를 사용해야겠다는 생각이 들었고, 정답으로 이어질 수 있었다.

<정답 코드>

from queue import PriorityQueue
import datetime as dt


def solution(book_time):
    room = PriorityQueue()
    book_time = sorted(book_time)

    for start, end in book_time:
        if not room.qsize():
            room.put((end, start))
            continue

        out = room.get()
        clean = dt.datetime.strptime(out[0], '%H:%M') + dt.timedelta(minutes=10)
        if clean > dt.datetime.strptime(start, '%H:%M'):
            room.put(out)

        room.put((end, start))

    return room.qsize()

접근은 아래와 같다.

1.  book_time을 입장시간 기준으로 정렬한다. (예약이 뒤죽박죽으로 되어있기 때문에 필수 과정이다.)
2. 정렬된 book_time을 순회하면서 Priority Queue에 삽입한다.
   1. 삽입할 때는 퇴실이 빠른 기준으로 삽입한다.
   2. 가장 빨리 퇴실하는 [0]번째 방 + 10분이 현재 고객의 입장 시간보다 이른지 비교하는 과정을 포함한다.
3. get되지 못한 방들은 계속 이용되고 있다고 가정하면 Priority Queue의 길이가 정답이 된다.

정답을 도출하기 까지 총 두번의 시행착오가 있었다.

처음은 시간계산을 포함하지 않고 진행해서 틀렸었다.

시간이 문자열로 주어져있기 때문에 시간으로 전환하여 10분 뒤를 계산해줘야한다. (datetime 모듈)

두번째는 sort하지 않아서 틀렸었다.

Priority Queue를 채울 때 입장이 빠른 기준으로 처리해야하기 때문에 정렬을 해야했다.

이제 좁은 시각으로 문제를 바라보지 않고 좀 생각하는 시간을 가지게 된게 뿌듯했다.

앞으로도 이렇게 술술 문제가 풀렸으면 좋겠다.

문제 출처: 백준 온라인 저지

문제 설명

🔎 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.
- 정사각형은 서로 겹치면 안 된다.
- 도형은 모두 연결되어 있어야 한다.
- 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다.
종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.
테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

(테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.)

처음에는 문제를 잘못 읽어서 저것들을 하나씩 다 놔야하는 줄 알고, 이렇게 어려운 문제가 기초 강의 문제라고..? 생각했다.

물론 문제를 푸는 것이 쉽지는 않았으나, 다행히 저 도형들 중 하나만 놓아도 돼서 비교적 많이 쉬워졌다.

배열 원소 값은 상관없었고, N과 M은 500이라는 비교적 작은 숫자여서 완전 완전 탐색으로 진행했다.

product를 이용해서 갈 수 있는 모든 방향에 대해 구했고, (product의 길이는 64였다.) product를 탐색하면서 가장 큰 값을 구하는 그런 방법이었다.

product배열로는 'ㅗ, ㅜ, ㅓ, ㅏ' 모양을 구현할 수 없었기에 해당 방식을 구현하는 함수를 또 작성해준 후에야 정답에 접근할 수 있었다.

<틀린 코드 보기>

import sys
from itertools import product
inp = sys.stdin.readline


def place(x, y):
    val = 0
    for c in case:
        temp = paper[x][y]
        nx, ny = x, y
        visit = set()
        visit.add((nx, ny))
        flag = False
        
        for dx, dy in c:
            nx = nx+dx
            ny = ny+dy
            if (nx, ny) in visit:
                flag = True
                break
            if 0 <= nx < n and 0 <= ny < m:
                temp += paper[nx][ny]
                visit.add((nx, ny))
            else:
                flag = True
                break
                
        if not flag:
            val = max(val, temp)

    return val

def last_place(x, y):
    moves = [[[0, 1], [0, 1], [-1, -1]], [[0, 1], [0, 1], [1, -1]], [[1, 0], [1, 0], [-1, 1]], [[1, 0], [1, 0], [-1, -1]]]
    val = 0
    for move in moves:
        flag = False
        nx, ny = x, y
        temp = paper[nx][ny]

        for dx, dy in move:
            nx, ny = nx+dx, ny+dy

            if 0 <= nx < n and 0 <= ny < m:
                temp += paper[nx][ny]
            else:
                flag = True

        if not flag:
            val = max(temp, val)

    return val


n, m = map(int, inp().split())
paper = [list(map(int, inp().split())) for _ in range(n)]
answer = 0
case = list(product([[1, 0],[-1, 0],[0, 1],[0, -1]], repeat=3))

for i in range(n):
    for j in range(m):
        answer = max(answer, place(i, j))
        answer = max(answer, last_place(i, j))

print(answer)

작성한 코드는 python3로는 통과하지 못했고, pypy3로는 통과했다. 실행시간과 메모리 사용량 모두 불만족스러웠다. Python3로도 통과하지 못했기 때문에 프로그래머스였다면 정확성만 통과한 코드라 취급하고 다른 방법을 모색했다.

진짜 정답 코드에서는 원리는 같지만 dfs를 활용했고, max값을 이용해 불필요한 계산을 하지 않았다는 점이 내 코드와 차이가 있었다.

<정답 코드>

def dfs(x, y, depth, cur):
    global answer

    if cur + max_val*(4-depth) <= answer:
        return

    if depth == 4:
        answer = max(answer, cur)
        return

    for dx, dy in moves:
        nx, ny = x + dx, y + dy

        if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny]:
      		# 'ㅗㅜㅓㅏ' 구현
            if depth == 2:
                visit[nx][ny] = True
                dfs(x, y, depth+1, cur + paper[nx][ny])
                visit[nx][ny] = False

            visit[nx][ny] = True
            dfs(nx, ny, depth+1, cur + paper[nx][ny])
            visit[nx][ny] = False



n, m = map(int, input().split())
paper = [list(map(int, input().split())) for _ in range(n)]
answer = 0

visit = [[False]*m for _ in range(n)]
moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
max_val = max(map(max, paper))

for i in range(n):
    for j in range(m):
        visit[i][j] = True
        dfs(i, j, 1, paper[i][j])
        visit[i][j] = False

print(answer)

접근은 아래와 같다.

1. 모든 좌표에서 dfs를 실행한다.
2. 갔다가 다시 되돌아오는 경우도 있기 때문에 visit을 통해서 방지한다.
3. 모든 도형은 총 4개의 작은 사각형으로 이루어져 있기 때문에 탈출 조건은 아래와 같다.
   1. 현재 값에서 가장 큰 값을 가능한 많이 더해도 현재 answer 값 보다 작으면 return한다.
   2. 깊이(depth)가 4가 되면 answer을 업데이트한 후 탈출한다.
4. 'ㅗ, ㅜ, ㅓ, ㅏ'는 무조건 갔던 길을 한번 되돌아와야하기 때문에 분기점인 depth=2에서 현재 위치에 대한 재귀를 또 한번 수행한다.
5. 한번의 도형 탐색이 끝나면 방문했던 경로들을 초기화 시켜준다.

일반적으로 재귀 함수는 실행 속도가 느리지만, 탈출 조건이 명확하고 depth가 4밖에 안되기 때문에 빠르게 돌아갔다.

실행속도가 10배 넘게 빨라졌고 메모리 소비량도 1/3가량으로 줄었다.

혹시나 해서 내가 작성했던 'ㅗ, ㅜ, ㅓ, ㅏ'를 확인하는 함수로 진행했을 때는 어떤가 확인해봤더니

그냥 중간정도로 나왔다. Python3로 통과되는 것에 의의를 두기로 했다.

탈출 조건을 잘 설정하는 것만으로도 시간을 많이 단축할 수 있다는 사실이 좀 놀라웠고, dfs는 이제 학을 땠다라고 생각했지만 여전히 모르는 것 투성이었다.

문제 출처: 프로그래머스

문제 설명

처음 열었을 때 아 그냥 문자열 파싱 문제인가 생각했지만 생각보다 까다로운 구현과정이 내포된 문제였다.

정말 다행스럽게도 연산자가 3개 밖에 없고, 문자열의 길이도 100이 제한이었기 때문에 시간 복잡도를 고려하지 않고 문제를 풀어나갔다.

<정답 코드>

from itertools import permutations
from collections import deque


def ex_split(ex):
    reg = []
    tmp = ''
    for i in ex:
        if i.isdigit():
            tmp += i
        else:
            reg.append(int(tmp))
            reg.append(i)
            tmp = ''

    if tmp:
        reg.append(int(tmp))
    return reg


def solution(expression):
    answer = 0
    expression = ex_split(expression)

    for case in permutations(['+', '-', '*'], 3):
        temp = deque(expression)
        for operator in case:
            ans = deque()
            while len(temp):
                cur = temp.popleft()

                if cur == operator:
                    a = ans.pop()
                    b = temp.popleft()
                    ans.append(eval(str(a)+cur+str(b)))
                else:
                    ans.append(cur)

            temp = ans

        answer = max(abs(temp[0]), answer)

    return answer

피연산자와 연산자를 구분하고 연산 자체도 구현해야하는 번거로운 문제였기에 코드도 조금 길어졌다.

접근은 아래와 같다.

1. 인자로 받은 expression 식을 숫자와 연산자로 구분한다.
2. permutation을 이용해 연산자의 계산 순서를 정의한다.
3. 하나의 연산자 순서를 순회하면서 해당 연산자가 존재하는 양옆을 연산하며 전체를 순회한다.
4. 최대값을 갱신한다.

eval을 통해서 문자열 수식을 간단하게 계산할 수 있는 점이 좋았다.

다른 사람들을 보니, 문자열 포맷팅을 통해 간단히 구현한 사람도 있고 regex를 활용해 간단히 푼 사람도 있었다. 코드를 참조해서 발전해보도록 하자..

문제 출처: 프로그래머스

문제 설명

🔎[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 함께 가을 소풍을 가는 중에 징검다리가 있는 개울을 만나서 건너편으로 건너려고 합니다. "라이언" 선생님은 "니니즈 친구들"이 무사히 징검다리를 건널 수 있도록 다음과 같이 규칙을 만들었습니다.

징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다.디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다.단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다.

"니니즈 친구들"은 개울의 왼쪽에 있으며, 개울의 오른쪽 건너편에 도착해야 징검다리를 건넌 것으로 인정합니다."니니즈 친구들"은 한 번에 한 명씩 징검다리를 건너야 하며, 한 친구가 징검다리를 모두 건넌 후에 그 다음 친구가 건너기 시작합니다.

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k가 매개변수로 주어질 때, 최대 몇 명까지 징검다리를 건널 수 있는지 return 하도록 solution 함수를 완성해주세요.

[입출력 예]

사람의 직관으로는 어렵지 않은 문제나, 컴퓨터를 통해 구현하고자 하니 까다로운 문제였다.

stones 배열 제한이 200,000, 각 원소 제한이 200,000,000이고 효율성 테스트까지 통과해야하므로 단순히 모든 돌을 1씩 감소시키면서 문제를 풀면 시간 제한을 통과할 수 없다.

그래서 처음 생각한 방법은, stone배열을 정렬해서 k번째 원소만큼 빼고 시작하는 것이었다.

이 방법은 결국은 1씩 감소 시키는 걸 조금 더 가속화 시켜줄 뿐, 시간 복잡도 개선에 별 기여를 하지 못했다.

방법은 '이분 탐색'에 있었다.

처음에 이분 탐색이라는 힌트를 봤을 때 돌의 순서가 정해져있어서 정렬하지 못하는데 이분 탐색이 가능한가? 의문을 가졌었다. (이분 탐색은 원래 정렬된 배열에 시행하는 탐색 알고리즘이다.)

<정답 코드>

def solution(stones, k):
    left, right = 0, max(stones)
    
    while left <= right:
        mid = (left+right)//2
        flag = 0
        for s in stones:
            if s-mid < 0:
                flag += 1
                if k <= flag:
                    break
            else:
                flag = 0
            
        if k <= flag:
            right = mid-1
        else:
            left = mid+1

    return left-1

이 문제에서 이분 탐색의 개념은 배열에 적용하는게 아니라 윈도우(범위)에 적용되는 것이었다.

접근은 아래와 같다.

1. stones원소의 최대 값을 구한다.
2. 돌에서 뺄 원소 값을 left와 right의 중간값으로 하여 전체 돌을 순회한다.
3. flag를 통해서 0보다 작은 값이 되는 돌들을 카운트 한다.
   1. 0보다 크면 flag를 0으로 초기화한다.
4.  flag가 k가 되면 for문을 탈출한다.
5. 이후 윈도우의 크기를 절반으로 줄여 다시 진행한다.

이 방법을 시도하면서 들었던 의구점은 left나 right의 값이 stone의 원소와 일치하지 않는다면 정렬을 통해 진행했던 내 방법보다 나은게 뭐가 있지? 라는 생각이었다.

그래서 다시 값의 개수 자체를 줄이고자 set을 활용해서 진행해보고자 했으나, set으로 전환하고 list로 바꾸고 sort까지 하는 과정에서 시간 복잡도를 너무 잡아먹어서 포기하기로 했다..

*해당 문제를 deque와 sliding window maximum을 통해 해결할 수 있다는 글을 보았다. 원리 자체가 아예 이해 안가지는 않았지만, 여러번 작성해봐도 실제로 작동하는 코드를 짤 수 없었다. 이후에 다시 한번 도전해보고자 한다.

아직 현업에서 데이터 분석가로 뛰어본 적이 없는 나는 실무를 어떻게 경험할 수 있을까 고민하다가 GCP에서 제공하는 BigQuery 라는 데이터웨어하우스에서 예제 DB를 제공해준다는 소식을 접하게 됐다.

빅쿼리는 페타 바이트*급 데이터 웨어하우스다.
NoOps라는 특징을 가지고 있고, 기존 RDBMS에서 사용하는 SQL언어를 그대로 사용해 접근성이 좋다.
기본적으로 유료 서비스지만 월 1TB만큼의 연산을 무료로 제공해주고 있다.
(페타 바이트(PB) = 1,000 테라바이트(TB) = 10^15 바이트)

Analytics Hub를 열심히 뒤져서 Thelook_eCommerce라는 데이터셋을 찾았다.

페이지에서는 데이터베이스가 어떤 관계로 구성되어있는지까지는 자세히 나와있지 않았지만, 온라인 의류 쇼핑몰에서 발생할 수 있는 데이터를 예제로 작성해놓은 것이라고 했다.

최근 그로스해킹을 공부하면서 이를 실습할 기회가 있었으면 좋겠다고 생각했기 때문에 냉큼 주워서 어떻게 생긴 데이터셋인지 열어보았다.

데이터셋을 프로젝트에 연결하고 열어보니 사진과 같이 총 7개의 테이블로 구성되어있었다.

• distribution_centers : 데이터 적재에 기여한 온라인 쇼핑몰 지점에 관한 테이블
• events : 유저가 발생시킨 이벤트에 대한 테이블
• inventory_items : 적재되어있는 물품에 대한 테이블
• order_items : 유저가 주문한 아이템에 대한 테이블
• orders : 유저의 주문 내역이 담긴 테이블
• products : 취급하는 물품에 대한 테이블
• users : 유저의 정보가 담긴 테이블

실제 온라인 쇼핑몰에서 사용할 법한 내용으로 구성했다길래 내가 모르는 복잡한 관계를 가지고 있지 않을까 생각했는데, 테이블 간의 관계는 따로 설정되어있지 않았고, type만 지정되어있고 nullable 한 특징 말고는 설정되어있는게 없었다.

log 기록을 통해서 AU(Active User)을 구하는 것에 대해 궁금했기에, event 테이블을 열어서 MAU를 직접 구해보기로 했다.

테이블에 대해 상세히 보니 테이블은 총 13개의 필드로 구성되어있었고, 이벤트에 대한 id, 발생시킨 유저의 id, 발생 날짜, 종류, 트래픽 소스, 발생 위치 등의 내용이 들어있었다.

MAU를 구하려면 월별 접속한 유저를 중복하지 않고 합산하는 query를 작성해야한다.

select ym, count(user_id) as MAU
from 
(
  select format_datetime('%Y-%m', created_at) as ym, user_id
  from `thelook_ecommerce.events`
  group by ym, user_id
)
group by ym
order by ym;

(아직 미숙한 SQL 실력, 아직까지 query별 속도 차이를 잘 모른다.)

연월, 유저별로 group by해 조회한 결과에서 연월을 기준으로 user_id를 count한 값으로 구했다.

다행히 결과물이 잘 나왔다.

대충 살펴보니 월별로 꾸준히 증가하는 형태였다.

이를 좀 더 직관적으로 보고싶어서 태블로와 연동해서 시각화해보기로 했다.

태블로에서 서버와 연결하기 기능에서 Google BigQuery가 있어서 바로 연동 가능했다.

예제 데이터셋이기 때문에 변화가 없어서 어떻게 불러오든 상관은 없지만, 연산 용량 제한이 있어서 추출 방법으로 불러왔다.

사용자 지정 SQL 불러오기를 통해 작성한 query를 삽입해서 MAU를 바로 땡겨왔고, ym이 string 타입으로 되어있어 아래 함수를 통해 date타입으로 변환시켜줬다.

DATEPARSE('yyyy-MM', str([ym]))

변경시킨 후, 월별 MAU 그래프를 생성하고 바로 퀵 테이블 계산을 이용해 전월대비MAU상승률을 그래프로 나타냈다.

결과는,,

괜찮게 나온거같다.

19년 1월부터 데이터가 적재되기 시작했고 이후로 감소하는 경우는 거의 없고 꾸준히 성장하고 있는 형태로 보인다.

작은 단위에서 시작하다보니 초반에 급격한 상승이 관찰된 것으로 보인다.

다음에는 데이터들을 활용해서 리텐션이나 다른 지수들을 구해보는 것이 목표다.

문제 출처: 프로그래머스

문제 설명

🔎개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다.
이런 응모자들을 따로 모아 "불량 사용자"라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다.
이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다.
가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
"무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 "제재 아이디" 라고 부르기로 하였습니다.

문자열 처리 문제는 언제나 귀찮음을 동반한다.

그리고 해당 문제는 브루트포스가 아닌 방법으로 접근하면 상당히 어렵게 느껴졌다.

제한사항을 잘 읽어보고 바로 브루트포스를 떠올렸다면 상당한 침착한 실력자임이 분명하다..

<정답 코드>

from itertools import permutations
import re

def solution(user_id, banned_id):
    n = len(banned_id)
    answer = set()
    banned_id = [i.replace('*', '.') for i in banned_id]
    
    for per in permutations(user_id, n):
        tmp = list(per)
        for i in range(n):
            if not(re.match(banned_id[i], tmp[i]) and len(tmp[i]) == len(banned_id[i])):
                break
        else:
            tmp.sort()
            answer.add(tuple(tmp))

    return len(answer)

개인적으로 permutations, combinations를 사용하지 않는 것을 선호하지 않는다.

옛날에 처음 itertools를 알게 됐을 때 신나게 사용하다가 항상 시간초과를 먹었기 때문에 친하지 않다..

하지만 이 문제에서는 배열의 길이가 최대 8이므로 permutation을 이용해도 시간을 많이 잡아먹지 않아 결국은 사용하게 됐다.

접근은 아래와 같다.

1. user_id에서 banned_id 길이 만큼의 아이디를 순열로 추출한다.
   • 순열로 추출하는 이유: user_id 배열의 순서와 상관없이 banned_id가 구성되었기 때문
2. 추출된 순열 전체를 탐색하면서 banned_id 전체와 매칭되는지 확인한다.
   • 매칭되는가는 re 모듈을 활용해서 진행한다.
   • re.match 함수는 '.'이 입력된 자리에는 어떤 문자든 대체 가능하기 때문에, 우선적으로 banned_id의 원소를 구성하는 '*'을 '.'로 대체하는 작업을 진행하고 순회한 것이다.
   • 또한, match는 길이와 상관없이 "해당 문자들로 시작한다면 True"이기 때문에 길이 검사를 따로 해줘야한다.

처음에는 match도 직접 구현하려하고, permutation이 아닌 match되는 문자들을 추출한 다음 조합하려했으나, 결국은 banned_id의 길이만큼 반복해야한다는 것이 permutation과 같은 복잡도를 가져 그냥 가져다 쓰게 되었다.

파이썬이라는 언어가 가진 훌륭한 특징인 라이브러리들은 문제 해결에 큰 도움을 줄 수 있지만, 어떻게 동작하는지 정확히 파악하지 않고 쓰면 오히려 문제 해결에 방해가 될 수 있는 것 같다.

항상 유의해서 사용하도록 하자.

문제 출처: 프로그래머스

문제 설명

🔎0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다.

구체적인 방식은 다음과 같습니다.

당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다.
위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

정사각형의 크기를 가진 2차원 배열을 4분할 하면서 풀어나가는 문제다.

처음에는 배열을 분할하는데 초점을 두고 문제를 풀어보려했다.

배열의 크기는 반드시 2의 배수인 정사각형 형태였기 때문에 항상 (배열의 길이)//2 만큼씩 행, 열을 분할해서 진행해나가면 4분할 하는 것은 그렇게 어렵지 않았다.

하지만, 분할된 사각형 안에서 0과 1의 개수를 세아리는 부분이 어렵다.

처음에는 재귀호출을 통해 분할이 불가능할 때 까지 분할한 후 list로 반환하는 답안을 작성하였다.

<틀린 코드 보기>

def quard_split(arr):
    n = len(arr)
    box = [[], [], [], []]
    for i in range(n//2):
        box[0].append(arr[i][:n//2])
        box[1].append(arr[i][n//2:])
        box[2].append(arr[n//2+i][:n//2])
        box[3].append(arr[n//2+i][n//2:])
        
    for i in range(4):
        if 0 < sum(list(map(lambda x: sum(x), box[i]))) < (n//2)**2:
            box[i] = quard_split(box[i])
    
    return box

def solution(arr):
    answer = [0, 0]
    box = quard_split(arr)
    print(box)
    return answer

분할을 한 결과 배열을 출력해보면 위와 같이 중첩 배열 형식으로 나타나기 때문에 이것을 다시 flatten 하는 작업이 어려웠고, flatten했을 때 하나로 세아려지는 0, 1의 개수를 파악하기가 어려웠다. 그렇다고 무작정 for문을 돌리자니 깊이가 얼마인지 알 턱이 없었기 때문에 시간 복잡도 부분에서도 심각한 문제가 있었다.

정답에서는 실제로 분할하는 것이 아닌, count하는 것이 주 목적이었다.

<정답 코드>

def solution(arr):
    answer = [0, 0]
    _len = len(arr)
    
    def quard_split(x, y, _len):
        cur = arr[x][y]
        
        for i in range(x, x+_len):
            for j in range(y, y+_len):
                if arr[i][j] != cur:
                    _len //= 2
                    quard_split(x, y, _len)
                    quard_split(x+_len, y, _len)
                    quard_split(x, y+_len, _len)
                    quard_split(x+_len, y+_len, _len)
                    return
        
        answer[cur] += 1
    
    quard_split(0, 0, _len)
    return answer

이 방법은 분할을 모두 마친 후 분석을 진행하는 것이 아닌, 분할을 하는 과정에서 count를 한다. 다른 개념 자체는 이전에 작성했던 코드와 일치한다.

접근은 아래와 같다.

1. 분할(혹은 전체) 사각형의 좌측 상단 꼭짓점을 좌표에서 시작해서 해당 사각형 내에서 시작점과 다른 값을 하나라도 가지면 다시 4분할을 진행한다.
2. 반복문을 전부 순회하고 탈출하게 되면 시작점 값을 +1 해준다.

🔎해당 알고리즘은 분할 정복 알고리즘이라고 한다.
쉽게 풀리는 부분은 그냥 계산으로 진행하고, 아니면 작은 여러 개의 부분 문제로 구분해서 푸는 개념이다.
위 문제에서는 하나의 사각형을 점검하는 quard_split 함수가 분할해야 하는 상황에 처하게 되면 4개의 quard_split함수로 나뉘어 문제를 푸는 형태인 것이다.

코딩 테스트를 공부하다 보면 가장 자주 등장하는 탐색, DP, 트리, 그래프 등의 문제 이외에도 분할 정복, 이분 탐색, 슬라이딩 윈도우 등과 같이 한번씩 등장하는 어려운 문제들을 발견할 수 있다.

이런 문제일수록 더욱 꼼꼼히 기록하고 기억해서 코딩 테스트에서 우위를 가져갈 수 있도록 노력해야겠다.