코딩 테스트 - 노정호 강사님

• 코딩 테스트를 공부해야 하는 이유

  • 대기업은 취업할때 대부분 코딩테스트를 실시.
  • 내 포트폴리오가 아무리 좋아도 코테를 통과하지 못하면 포폴을 보여줄 수도 없음.

• 요즘 트렌트는 문제길이가 길어지면서 문해력파트가 중요해짐.

• 문제풀이 절차
  (1) 문제 이해하기 문제 분석
  (2) 접근 방법 - 자료구조 알고리즘 이론 학습
  (3) 코드설계 시간 복잡도
  (4) 코드 구현 언어숙련도(필수 코드 외우기) 구현연습
  

• 코테 효율적인 공부방법

  • 시간복잡도
  • 자주나오는 필수 자료구조/알고리즘
  • 면접과 코테 내용은 다르다.
  • 이론을 제대로 이해하고 문제 접근
  • 구현이 중요하다. 주력 언어를 정하고 체화
  • 스터디 꼭꼭.

1일차

• 시간 복잡도
• 메모리 구조
• 자료구조
  • List, queue, stack, dictionary, graph, tree, heapq
• 알고리즘
  • 완전탐색(+백트레킹), 재귀, 반복문,
  • DFS, BFS, DP,
  • Dijkstra(heapq), sort()

---

💡 오늘의 하이라이트는 재귀함수

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

    return recur([], 0)

    
print(solution(nums = [4,9,7,5,1], target = 14))

---

• Stack - LIFO (프링글스)
  < 괄호문제는 stack으로 >

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

2일차

💡 BFS, DFS

    - 그래프의 길찾기 문제.
    - DFS는 재귀를 이용한 알고리즘.
    - BFS는 최단거리를 알수 있다.
    

• BFS - queue를 사용한다.
  • Queue - FIFO
    • deque.append()
    • deque.popleft()

from collections import deque
def bfs(graph, start_v):
    q = deque()
    # 시작점 예약
    q.append(start_v)
    # 방문 표시
    visited = {start_v: True}
    while q:
        cur_v = q.popleft()
        print(cur_v," ", end='')
        for next_v in graph[cur_v]:
            if next_v not in visited:
                q.append(next_v)
                visited[next_v] = True
        
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],
}
bfs(graph, start_v=0)

---

• DFS : 재귀 사용

def gogo(graph, start_v):
    visited = {}
    visited[start_v]=True
    def dfs(cur_v):
        print(cur_v," ", end='')
        for next_v in graph[cur_v]:
            if next_v not in visited:
                visited[next_v] = True
                dfs(next_v)
    dfs(start_v)
                
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],
}
gogo(graph, start_v=0)

3일차

💡 암시적 그래프, Dijkstra

	- 암시적 그래프는 행렬에 지도를 표시하는 방식
    - 4방향 또는 8방향을 탐색하면서 문제를 해결
    - 그 안에서 길을 찾는 것은 BFS, DFS를 사용.
    - Dijkstra는 그래프에 가중치를 더한 것.
    - heapq를 사용.
    

• 암시적 그래프
  < DFS예시> : 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)]
        def dfs(r,c):
            visited[r][c]=True
            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)
				cnt = 0        
				for i in range(row_len):
            for j in range(col_len):
                if grid[i][j] == "1"
                    if 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"],
]

dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
s=Solution()
s.numIslands(grid)

---

• Dijkstra : 이해해면서 외우자

def dijkstra(graph, start_v, dest, n):
    distances = [INF] * (n + 1)
    distances[start_v] = 0
    pq = [(0, start_v)]

    while pq:
        cur_dist, cur_v = heapq.heappop(pq)
        if distances[cur_v] < cur_dist:
            continue
        for next_v, cost in graph[cur_v]:
            next_dist = distances[cur_v] + cost
            if next_dist < distances[next_v]:
                distances[next_v] = next_dist
                heapq.heappush(pq, (next_dist, next_v))
    return distances[dest]

graph = { … }
dijkstra(graph, 1, 8, len(graph))

• Dijkstar 실전문제

from collections import defaultdict
import heapq
import sys


class Solution:
    def networkDelayTime(self, times, n, k):
        # 입력값 변환
        # 가중치 단방향 그래프를 인접리스트로 구현하기
        graph = defaultdict(list)
        for u, v, time in times:
            graph[u].append((time, v))

        # 1부터 n까지 총 n개의 노드의 cost를 적어 놓는다.
        costs = [sys.maxsize for _ in range(n + 1)]
        pq = [(0, k)]
        costs[k] = 0
        while pq:
            travel_time, cur_v = heapq.heappop(pq)
            for time, next_v in graph[cur_v]:
                next_cost = travel_time + time
                if next_cost < costs[next_v]:
                    costs[next_v] = next_cost
                    heapq.heappush(pq, (next_cost, next_v))

        # index 0번째에는 sys.maxsize값이 무조건 들어 있으므로 이를 제외한 나머지 값들만 다시 떼어준다.
        new_costs = costs[1:]

        # costs에 sys.maxsize와 같은 크기의 값이 저장되어 있다면 도달하지 못했다는 뜻이므로 -1를 반환한다.
        for cost in new_costs:
            if cost == sys.maxsize:
                return -1

        # 모든 노드를 방문하기 위한 최소 시간을 구해야 한다.
        # 각 노드까지 도달할 수 있는 최소 시간은 이미 costs에 저장해두었다.
        # 따라서 모든 노드를 방문하기 위해서는 가장 높은 시간을 반환해야 한다.
        return max(new_costs)

수업시간 문제들

• 1번문제: two sum
• 3번문제: combinations
• 4번문제: 괄호 유효성 문제
• 7번문제: keys and rooms
  
• 10번문제: number of islands
• 11번 문제: shortest path
• 13번 문제: network delay time

추천문제들

1. 네트워크
2. 거리두기 확인
3. 스타트 택시