AI 개발자 취업을 위한 코딩테스트 특강 후기

AI 개발자 취업을 위한 코딩테스트 특강 후기

🗓️ 2024.05.16 ~ 2024.05.20

3일간 노정호 강사님의 코딩테스트 특강을 들었다. 코딩테스트는 취업을 위해 거의 반 필수적인 요소이기 때문에 이번 기회에 열심히 들어보기로 했다. 특히, AI 개발자로 취업을 목표로 하고 있는 나에게는 더욱 중요한 요소이기 때문이다. 3일동안 DFS, DFS, HeapQ, Dijkstra, 완전탐색, Graph에 대해 다루었다. 수업방식은 강사님께서 간단히 이론설명을 해주셨고 관련된 알고리즘 문제를 LeetCode 혹은 프로그래머스에서 풀어보는 방식이었다. 사실 3일만에 다양한 자료구조와 알고리즘을 전부 흡수하기에는 어려웠지만, 강사님께서 알고리즘을 풀 때 어떤식으로 접근해야 하는지에 대한 방향성을 제시해주셔서 많은 도움이 되었다. 또한, 알고리즘을 풀 때 어떤식으로 코드를 작성해야 하는지에 대한 방법론을 배웠다.

1. twosum 문제

twosum 코드 구현(반복문)

class Solution:
    def twoSum(self, nums, target):
        n = len(nums)
        for i in range(n):
            for j in range(i+1, n):
                if nums[i]+nums[j] == target:
                    return [i, j]

twosum 코드 구현(재귀)

class Solution:
    def twoSum(self, nums, target):
        n = len(nums)
        def find(start, value):
            for i in range(start+1, n):
                if nums[i] == value:
                    return i
            return -1
        for i in range(n):
            idx = find(i, target-nums[i])
            if idx != -1:
                return [i, idx]

2. combination 조합(재귀)

def solution(n, k):
    ans = []
    def recur(start, comb):
        if len(comb) == 2:
            ans.append(comb[:])
            return
        
        for i in range(start, n+1):
            comb.append(i)
            recur(i+1, comb)
            comb.pop()
    recur(1, [])

    return ans

3. 올바른 괄호

def solution(s):
    stack = []
    for p in s:
        if p == '(':
            stack.append(p)
        else:
            if not stack:
                return False
            stack.pop()
    return not stack

4. keys and rooms

from collections import deque

class Solution:
    def canVisitAllRooms(self, rooms):
        n = len(rooms)
        visited = [False] * n
        def bfs(graph, start_v):
            # BFS코드 작성하기
            
            # visited[cur_v] = True
        bfs(rooms, start_v=0)

        return all(visited)

class Solution:
    def canVisitAllRooms(self, rooms):
        n = len(rooms)
        visited = [False] * n
        
        def dfs(cur_v):
            visited[cur_v] = True
            for next_v in rooms[cur_v]:
                if not visited[next_v]:
                    dfs(next_v)

        dfs(cur_v=0)
        print(visited)
        return all(visited)

s = Solution()
s.canVisitAllRooms(rooms= [[1,3], [2,4], [0], [4], [ ], [3,4] ])    

5. 암시적 그래프 DFS

def dfs(r, c):
    visited[r][c] = True
    print((r,c), end=' ')
    for i in range(4):
        next_r = r + dr[i]
        next_c = c + dc[i]
        if 0 <= next_r < row_len and 0 <= next_c < col_len:
            if grid[next_r][next_c] == 1:
                if not visited[next_r][next_c]:
                    dfs(next_r, next_c)

grid = [
   [1, 1, 1, 1],
   [0, 1, 0, 1],
   [0, 1, 0, 1],
   [1, 0, 1, 1],
]
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
dfs(0, 0)

6. 암시적 그래프 BFS

from collections import deque
def bfs(r, c):
    q = deque()
    q.append((r,c))
    visited[r][c] = True

    while q:
        cur_r, cur_c = q.popleft()
        print((cur_r, cur_c), end ='->')
        for i in range(8):
            next_r = cur_r + dr[i]
            next_c = cur_c + dc[i]
            if 0 <= next_r < row_len and 0 <= next_c < col_len:
                if grid[next_r][next_c] == 1:
                    if not visited[next_r][next_c]:
                        q.append((next_r, next_c))
                        visited[next_r][next_c] = True

grid = [
   [1, 1, 1, 1],
   [0, 1, 0, 1],
   [0, 1, 0, 1],
   [1, 0, 1, 1],
]
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
dr = [0, 1, 0, -1, 1, 1, -1, -1]
dc = [1, 0, -1, 0, 1, -1, 1, -1]
bfs(0, 0)

7. number of islands

BFS

from collections import deque
class Solution:
    def numIslands(self, grid):
        row_len, col_len = len(grid), len(grid[0])
        visited = [[False] * col_len for _ in range(row_len)]
        cnt = 0
        dr = [0, 1, 0, -1]
        dc = [1, 0, -1, 0]
        def bfs(r, c):
            q = deque()
            q.append((r,c))
            visited[r][c] = True

            while q:
                cur_r, cur_c = q.popleft()
                for i in range(4):
                    next_r = cur_r + dr[i]
                    next_c = cur_c + dc[i]
                    if 0 <= next_r < row_len and 0 <= next_c < col_len:
                        if grid[next_r][next_c] == '1':
                            if not visited[next_r][next_c]:
                                q.append((next_r,next_c))
                                visited[next_r][next_c] = True

        for i in range(row_len):
            for j in range(col_len):
                if grid[i][j] == "1" and not visited[i][j]:
                    bfs(i,j)
                    cnt += 1
        return cnt

grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "1", "0"],
    ["0", "0", "0", "1", "1"],
]
s=Solution()
print(s.numIslands(grid))

DFS

from collections import deque
class Solution:
    def numIslands(self, grid):
        row_len, col_len = len(grid), len(grid[0])
        visited = [[False] * col_len for _ in range(row_len)]
        cnt = 0
        dr = [0, 1, 0, -1]
        dc = [1, 0, -1, 0]

        def dfs(cur_r,cur_c):
            visited[cur_r][cur_c] = True
            for i in range(4):
                next_r = cur_r + dr[i]
                next_c = cur_c + dc[i]
                if 0 <= next_r < row_len and 0 <= next_c < col_len:
                    if grid[next_r][next_c] == '1':
                        if not visited[next_r][next_c]:
                            dfs(next_r, next_c)

        for i in range(row_len):
            for j in range(col_len):
                if grid[i][j] == "1" and not visited[i][j]:
                    dfs(i,j)
                    cnt += 1
        return cnt

grid = [
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "1", "0"],
    ["0", "0", "0", "1", "1"],
]
s=Solution()
print(s.numIslands(grid))

8. shortest path in binary matrix

from collections import deque
class Solution:
    def shortestPathBinaryMatrix(self, grid):
        if grid[0][0]==1:
            return -1
        # BFS 초기세팅
        q = deque()
        # q.append(start_r, start_c, start_distance)
        q.append((0, 0, 1))
        # vististed = 초기화
        row_len, col_len = len(grid), len(grid[0])
        visited = [[False] * col_len for _ in range(row_len)]
        visited[0][0] = True
        dr = [1,1,1,0,0,-1,-1,-1]
        dc = [0,-1,1,1,-1,1,-1,0]
        while q:
            cur_r, cur_c, cur_d = q.popleft()
            if cur_r == row_len -1 and cur_c == col_len-1:
                return cur_d
            for i in range(8):
                next_r,next_c = cur_r+ dr[i],cur_c + dc[i]
                if 0 <=next_r <row_len and 0 <= next_c < col_len:
                    if grid[next_r][next_c] == 0 and not visited[next_r][next_c]:
                        q.append([next_r,next_c,cur_d+1])
                        visited[next_r][next_c] = True

            # 현재 노드 방문
            
            # 다음 노드 예약
            # q.append((next_r, next_c, cur_d+1))
        return -1 

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기