[TIL_Carrotww] 30 - 22/10/14

📝Carrotww의 코딩 기록장

🧲 Algorithm

🔍 프로그래머스 게임 맵 최단거리
전형적인 dfs, bfs 문제이다 내가 재귀에 약한편인데 그래도 나름 많이 익숙해져서 문제를 봤을때 뇌정지가 왔었지만, 그래도 지금은 어떻게 접근 해야할 지 느낌이 오기는 한다.

def solution(maps):
    import math
    from collections import deque
    last_row, last_col = len(maps[0]) - 1, len(maps) - 1
    MAX = math.inf
    visited = [[MAX] * (last_row + 1) for x in range(last_col + 1)]

    # 동서남북
    dx = [1, -1, 0, 0]
    dy = [0, 0, -1, 1]

    result = []
    stack = deque([(0, 0, 1)])

    cnt = 0
    while stack:
        cnt += 1
        x, y, cnt_val = stack.popleft()
        if x == last_row and y == last_col:
            result.append(visited[y][x])

        for i in range(4):
            n_x, n_y = x + dx[i], y + dy[i]
            if 0 <= n_x <= last_row and 0 <= n_y <= last_col:
                if maps[n_y][n_x] == 1:
                    if visited[n_y][n_x] < cnt_val + 1:
                        continue
                    visited[n_y][n_x] = cnt_val + 1
                    stack.append((n_x, n_y, cnt_val + 1))

    if result:
        print(cnt)
        return min(result)
    return -1

• 하다 하다 DFS로 DP까지 섞어서 끝까지 해보았는데 효율성에서 하나도 아쉽지 않게 모두 실패했다 ㅠㅠ
  이 문제로 이제 머리속에 각인되었다. 최단거리는 BFS 로 푸는것이 가장 좋다는것.
  처음에 DFS 로 접근하여 꼭 풀고싶어서 visited에 거리를 갱신해주며 기록하였는데 효율성에서 떨어지는 것 보니 위 문제는 BFS 아니면 안될 것 같다...
  아래는 BFS로 다시 푼 문제
• 또 row와 column 에 대해서 나는 다른 식으로 표기를 하였는데 행 -> x 축 row -> 행에 있는 자료 수 로 표기를 하였다.
  하지만 그렇게 표기를 하면 가시성이 좋지 않고 행렬에 대입할때 row, x, col, y를 서로 반대로 대입해 주어야 해서 나만 알아보기 쉬웠다.
  아래 풀이는 row -> row의 개수 ; col -> column의 개수 로 표기하여 가시성이 좋아? 졌다. ㅎㅎ 이제 절대 안까먹고 잘 쓸 것 같다.

def solution(maps):
    from collections import deque
    total_row, total_col = len(maps) - 1, len(maps[0]) - 1
    cnt = 0
    queue = deque()
    queue.append([0, 0])
    visited = [[0]*(total_col + 1) for _ in range(total_row + 1)]
    visited[0][0] = 1
    # 동서남북
    dr, dc = [1, -1, 0, 0], [0, 0, -1, 1]

    while queue:
        current_r, current_c = queue.popleft()
        if current_r == total_row and current_c == total_col:
            return visited[current_r][current_c]

        for i in range(4):
            next_r, next_c = dr[i] + current_r, dc[i] + current_c
            if 0 <= next_r <= total_row and 0 <= next_c <= total_col:
                if maps[next_r][next_c] == 1 and not visited[next_r][next_c]:
                    visited[next_r][next_c] = visited[current_r][current_c] + 1
                    queue.append((next_r, next_c))
    return -1

진짜 BFS, DFS 이해는 됐지만 풀때 상상이 안돼서 막막했었는데 역시 시간이 답인가보다.
잡고 계속 하니까 완벽히 이해했다. 이제는 머리속에서 지도로 그려지는 것 같다.
위 방식대로(BFS) 로 푸니 효율성 바로 통과 ㅎ
테스트 케이스 통과 시간도 훨씬 빨라졌다. 굳굳 너무 기분 좋다.

🔍 DFS 문제를 하나 더 풀었는데 이건 쉬우니 푼 방식만 올리겠다.
프로그래머스 타겟넘버

def solution(numbers, target):
    result = []

    def dfs(number, temp):
        if not number:
            if temp == target:
                result.append(1)
            return
        temp_num = number.pop()
        dfs(number[:], temp + temp_num)
        dfs(number[:], temp - temp_num)

    num = numbers.pop()
    dfs(numbers[:], -num)
    dfs(numbers[:], num)

    return len(result)

🧲 Django set_password 함수

🔍 Django authenticate 사용 시

user = authenticate(request, username=username, password=password)

DB 도 정상으로 들어가고 POST 로 데이터도 잘 넘어왔는데 user 가 계속 None이 뜰때!!!
장고에서 기본 제공중인 AbstractUser 를 상속받아 user model을 만들어 로그인 회원가입 테스트를 했는데 로그인, 즉 위 코드의 user 에 데이터가 자꾸 없다고 하는 것이였다.

💡 이유는 내가 PW 저장 시 DB에 잘 못 저장하였기 때문...

user_table.username = request.POST.get('username')
user_table.set_password(request.POST.get('password'))

Django에서 AbstractUser 모델을 상속받아 사용할때 DB에 set_password 함수로 저장을 하여야 암호화 하여 저장하여 authenticate로 검증이 가능해 진다.
검증 시 decoding을 하는 것이 아닌 같은 값을 encoding 하여 저장된 값이랑 비교하기 때문