백준3 [알고리즘] 위상 정렬(Topological Sort) - 개발하는 지토 위상 정렬(Topological Sort) 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 이다. 위상 정렬을 가장 잘 설명할 수 있는 예시는 대학의 선수과목 구조 또는 게임에서의 스킬트리 중 선행스킬이 존재하는 경우이다. 앞선 대표 예 두가지 중 각자 더 이해가 쉬운 예시를 떠올려 보면 쉽게 이해할 수 있을 것이다. 위상 정렬이 성립하기 위해서는 반드시 그래프에 순환이 존재하지 않아야 한다. 즉, 비순환 방향 그래프(Directed Acyclic Graph, DAG) 여야 한다. 그리고 하나의 방향 그래프에 대해서 위상 정렬을 수행한 결과 값이.. 2021. 3. 18. [공부] 온라인 알고리즘 문제풀이 스터디 후기 - 구글미트 (프로그래머스, 백준온라인저지) 오늘은 간단하게만 후기를 남겨보려 한다. 다음 스터디를 진행하면서는 좀 더 좋은 내용으로 글을 써볼 예정이다. 얼마 전에 내 블로그에 있던 문제풀이 글을 보시고 댓글을 남겨주신 분과 연락이 닿게 되었다. 같이 알고리즘 스터디를 하자는 제안이 있으셔서 나도 공부를 하고 있고, 더 열심히 해야 하는 입장이었기 때문에 흔쾌히 같이 하겠다고 했다. 그리고 오늘 오후 9~12시, 총 3시간 동안 스터디를 진행했다. 사실 아직 어떠한 방향으로 스터디를 하겠다고 명확히 정하질 못해서 체계적인 스터디는 아니지만, 차츰 발전하는 스터디가 되었으면 좋겠다. 오늘 같이 풀어본 문제는 1. programmers.co.kr/learn/courses/30/lessons/67256?language=java 코딩테스트 연습 - 키패.. 2020. 10. 29. [알고리즘] 백준 2839번: 설탕 배달 풀이 (자바/Java) DP,동적계획법, Dynamic Programming 기본 www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그�� www.acmicpc.net 설탕 배달 1 초 128 MB 130830 39344 31733 31.834% 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로.. 2020. 9. 26. 이전 1 다음
