WOONY's 인사이트

오늘은 그리디 알고리즘에 대해 공부한 내용을 빠르게 정리하고 마무리. 앞에서 배웠던 재귀 관련 알고리즘으로는 크게 두 가지가 있었다. 분할 정복(Divide and Conquer)과 동적계획법(Dynamic Programming)이 그것이다. 1. 분할정복은 큰 문제를 중복 없는 작은 문제들로 분할하는 방법이다. 재귀적으로 작은 문제부터 해결한다. 2. 반면, 동적계획법은 작은 문제들로 쪼개되 이 작은 문제들 중 중복되는 애들을 DP 테이블에 저장해두고 같은 값이 나왔을 때 계산 없이 바로 테이블에서 꺼낸다. 그러면 오늘 다룰 그리디 알고리즘은 어떤 친구일까? 이름처럼 말 그대로 Greedy하게 선택하는 알고리즘을 뜻한다. 즉, 현재 상태에서 가장 좋은 선택을 반복해서 해를 구성한다. 예제로 동전 교환 ..

오늘은 1주차 알고리즘 시험날. 문제는 #1924, #2503, #6603이 나왔고 1시간 반 동안 푼 문제는 #1924와 #6603으로 3문제 중 2문제. 오늘 시험 목표가 2문제 이상 맞추기였으니 선방은 했는데, 생각보다 1924와 6603을 쉽게 풀어 2503까지 풀지 못한 건 좀 아쉽긴 하다. 시험이 끝나고 바로 2주차 문제가 주어졌으나, 오늘은 푼 문제를 리뷰하면서 시간을 보냈다. 오후에는 #2503을 푸는데 시간을 썼다. 어렵다고 생각했지만 조금 해보니 어느 정도 감이 잡히더라. 스트라이크와 볼을 if문 두 번으로 처리하는 개념만 잘 생각하면 괜찮다. 오히려 쉽게 풀었던 #6603에서 시간을 많이 썼는데, 재귀를 이용한 다른 풀이를 익히느라 고생했다. 시험에서는 조합을 이용해 쉽게 풀었으나 원..

0. 목차 1. BFS - 큐 2. DFS - 스택 오늘은 사족 없이 빠르게 가보자. 아래와 같이 두 그래프가 있다. 보다시피 그래프 자체는 동일하다. 하지만 어디서부터 데이터를 읽어오는지 그 순서가 다르다. 1. BFS (Breath First Search) 왼쪽의 빨간 경로는 너비 우선 탐색인 BFS에 해당한다. 시작 노드에서 가까운 노드부터 순서대로 방문하는 탐색 알고리즘이다. 오른쪽의 DFS는 보다시피 경로 하나하나가 깊이를 주구장창 파는 반면, BFS에서는 시작 노드를 기준으로 동일한 레벨(=뎁스)에 있는 노드를 병렬적으로 방문하는 방식이다. 이를 구현하는 방식을 이해하려면 큐(Queue) 자료구조를 이해할 필요가 있다. 언젠가 큐와 스택을 구별하는 아주 명쾌한 설명을 읽은 적이 있는데, 큐는 ..

0. 목차 1. Dynamic Programming (DP) 2. 외판원 순회 문제(TSP) 어제는 일요일이었기에 TIL을 생략하고 8일차 TIL을 업로드한다. 그렇다고 어제도 공부를 하지 않은 것은 아니었는데, 어제부터 시작해 오늘까지 하루종일 괴롭혔던 건 외판원 순회 문제(TSP)였다. 먼저 외판원 순회 문제에 대한 설명을 읽어보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지..