helpot.kr helpot.kr

IT 분야에서 개발이 필요한 직군의 많은 경우, 코딩 테스트가 필요하다.

학습이 필요한 내용

• 자료구조
  List, queue, stack, dictionary(hashtable), graph, heapq(우선순위큐), tree
• 알고리즘
  완전탐색(+백트래킹), 재귀, 반복문, DFS, BFS, Dijkstra, 정렬, 위상정렬, two pointer, DP

외부 라이브러리 사용하는 것 관련(ex itertools)

파이썬에서는 각종 자료구조와 알고리즘을 제공하는 itertools와 같은 외부 라이브러리가 있다.
이런 라이브러리 사용을 코딩 테스트 때 허용하는 회사도 있고, 그렇지 않은 회사도 있기 때문에,
라이브러리 없이도 문제를 풀 수 있도록 준비해야 한다.

예제. twosum 코드 구현 (반복문)

https://leetcode.com/problems/two-sum/

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

if __name__ == "__main__":
    nums = [2, 7, 11, 15]
    target = 9
    sol = Solution()
    print(sol.twoSum(nums, target))

예제. twosum 코드 구현 (재귀)

https://leetcode.com/problems/two-sum/

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        return self.recur(nums, target, [], 0)
    
    def recur(self, nums: list[int], target: int, ans: list[int], start: int) -> list[int]:
        if len(ans) == 2:
            if nums[ans[0]] + nums[ans[1]] == target:
                return ans
            return []
        
        for i in range(start, len(nums)):
            ans.append(i)
            result = self.recur(nums, target, ans, i + 1)
            if result:
                return result
            ans.pop()


if __name__ == "__main__":
    nums = [4, 9, 7, 5, 1]
    target = 14
    sol = Solution()
    print(sol.twoSum(nums, target))

예제. 조합

https://leetcode.com/problems/combinations/

class Solution:
    def combine(self, n: int, k: int) -> list[list[int]]:
        def recur(comb, start_index):
            if len(comb) == k:
                answer.append(comb[:])
            for i in range(start_index, n+1):
                comb.append(i)
                recur(comb, i + 1)
                comb.pop()
        answer = []
        comb = []
        start_index = 1
        recur(comb, start_index)
        return answer

if __name__ == "__main__":
    n = 4
    k = 2
    sol = Solution()
    print(sol.combine(n, k))

예제. 괄호 유효성 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12909

def solution(s):
    open = 0
    close = 0
    for char in s:
        if char == '(':
            open += 1
        else:
            close += 1
        if close > open:
            return False
    if open != close:
        return False
    return True

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

예제. BFS(Breadth First Search)

from collections import deque
class Solution:
    def bfs(self, graph: dict[int, list[int]], start_v: int) -> dict[int, bool]:
        visited_dict = {}
        q = deque()
        q.append(start_v)
        visited_dict[start_v] = True

        while q:
            current_v = q.popleft()
            for next_v in graph[current_v]:
                if next_v not in visited_dict:
                    q.append(next_v)
                    visited_dict[next_v] = True
        return visited_dict

if __name__ == "__main__":
    graph = {
        0: [1, 3, 6],
        1: [0, 3],
        2: [3],
        3: [0, 1, 2, 7],
        4: [5],
        5: [4, 6, 7],
        6: [0, 5],
        7: [3, 5],
    }
    start_v = 0
    sol = Solution()
    print(sol.bfs(graph, start_v))

예제. DFS(Depth First Search)

from collections import deque
class Solution:
    # 재귀 방식
    def dfs1(self, graph: dict[int, list[int]], start_v: int) -> dict[int, bool]:
        self.visited_dict = {}
        current_v = start_v
        self.dfs1_recur(graph, current_v)
        return self.visited_dict
    
    def dfs1_recur(self, graph: dict[int, list[int]], current_v: int) -> None:
        self.visited_dict[current_v] = True
        for next_v in graph[current_v]:
            if next_v not in self.visited_dict:
                self.dfs1_recur(graph, next_v)

		# 스택 방식
    def dfs2(self, graph: dict[int, list[int]], start_v: int) -> dict[int, bool]:
        self.visited_dict = {}
        stack = [start_v]
        
        while stack:
            current_v = stack.pop()
            if current_v not in self.visited_dict:
                self.visited_dict[current_v] = True
                for next_v in graph[current_v]:
                    if next_v not in self.visited_dict:
                        stack.append(next_v)
        
        return self.visited_dict

if __name__ == "__main__":
    graph = {
        0: [1, 3, 6],
        1: [0, 3],
        2: [3],
        3: [0, 1, 2, 7],
        4: [5],
        5: [4, 6, 7],
        6: [0, 5],
        7: [3, 5],
    }
    start_v = 0
    sol = Solution()
    print(f'재귀방식: {sol.dfs1(graph, start_v)}')
    print(f'스택방식: {sol.dfs2(graph, start_v)}')

#패스트캠퍼스 #패스트캠퍼스AI부트캠프 #업스테이지패스트캠퍼스 #UpstageAILab #국비지원 #패스트캠퍼스업스테이지에이아이랩 #패스트캠퍼스업스테이지부트캠프