하나씩 배워나가는 개발일지

탐색 많은 양의 데이터 중 원하는 데이터를 찾는 과정 대표적인 그래프 탐색 알고리즘으로 DFS, BFS가 있음 스택 자료구조 선입후출(FILO): 먼저 들어온 데이터가 나중에 나가는 자료구조 입구와 출구가 동일한 형태로 스택을 시각화할 수 있음(박스쌓기 - 먼저 쌓은 박스를 가장 마지막에 꺼낼 수 있음) append() - 삽입 pop() - 삭제 큐 자료구조 선입선출(FIFO): 먼저 들어온 데이터가 먼저 나가는 자료구조 입구와 출구가 모두 뚫려있는 터널로 스택을 시각화 할 수 있음 큐를 구현할 땐 파이썬에서 제공하는 리스트를 사용하는 것보다 deque 라이브러리를 사용하는 것이 더 시간적으로 효율적임! from collections import deque # 큐 구현을 위해 deque 라이브러리 사용..

구현 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 행렬 일반적으로 알고리즘 문제에서 2차원 공간은 행렬의 의미로 사용 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용 문제 1) 상하좌우 코드 N = int(input()) plans = input().split() x, y = 1, 1 # L, R, U, D로 이동 dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] move_direction = ['L', 'R', 'U', 'D'] for plan in plans: for i in range(len(move_direction)): if plan == move_direction[i]: nx = x + dx[i] ny = y + dy[i] if nx < 1 o..

그리디 알고리즘이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 루트 노드부터 시작해서 거쳐 가는 노드 값의 합을 최대로 만들고 싶은 경우, 이때의 최적해는 무엇일까? 아래처럼 5 -> 7 -> 9로 거쳐가면 21이라는 최댓값이 나온다. 하지만 그리디 알고리즘은 어떻게 갈까? 놀랍게도 매순간 선택지 중 가장 최적의 해만 고른다. 루트 노드 5에서 시작해서 7, 10, 8 중에 가장 큰 10을 선택하고 4, 3중에 4를 선택한다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 ..