본문 바로가기
반응형

알고리즘4

2017 팁스타운 - 예상 대진표 (python & JavaScript) 프로그래머스에서 제공하는 연습 문제를 옛날 자료부터 최근 자료까지 모두 풀고 있습니다. 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 문제 설명 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번,... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호.. 2022. 4. 26.
신장 트리 (Spanning Tree) & 크루스칼(Kruskal) 신장트리 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 이러한 성질을 가진 그래프는 다양한 문제에 활용되는데, 대표적인 유형이 여러 노드를 연결하는 간선이 비용을 가질 때, 그 비용의 합이 최소가 되는 신장트리를 찾아야 하는 경우이다. 예를 들어보면, 아래와 같은 그래프가 존재 한다고 한다. 간선의 비용의 합을 최소로 하기는 신장트리가 되기 위해서는 아래와 같이 연결을 해야 할 것이다. 이처럼 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트릴르 찾는 알고리즘을 이제 '최소 신장 트리 알고리즘'이라고 하자. 이러한 최소 신장 트리 문제를 해결하기 위한 대표적인 알고리즘을 다음을 통해 배워보자. 크루스칼 알고리즘 (Kruskal Algorithm) 이는 가장 적은.. 2021. 9. 13.
위상 정렬 (Topology Sort) 위상 정렬 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘, 또는 방향 그래프의 모든 노드를 방향성에 어긋나지 않고 순서대로 나열하는 것으로 정의할 수 있다. 위상 정렬을 2단계로 설명할 수 있는데 다음과 같다. 진입차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 이때 진입차수란? 이는 한 노드로 방향을 가르키는 간선의 개수를 의미한다. 파이썬 소스 2021. 9. 13.
동적 계획법(Dynamic Programming, DP) 우리는 컴퓨터를 활용해도 해결하기 어려운 문제가 존재한다. 흔히 말하길, 해를 구하는 과정에서 비용( 시간 or 공간 )이 매우 많이 필요한 문제 등이 컴퓨터로 해결하기 어려운 문제,, 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 필요로 한다. 이때, 우리가 메모리 공간을 조금 더 할당함으로써 연산 속도를 증가시킬 수 있는 방법이 존재하는데 이것이 다이나믹 프로그래밍 기법이다. 동적 계획법은? 동적 계획법(다이나믹 프로그래밍)은 2가지 방식으로 접근할 수 있으며, 특히 메모이제이션기법을 통해 이전의 연산 결과를 저장하고 이를 다음 연산에 필요한 과정을 따른다. 모두 책에나 블로그에서 봤듯이 동적 계획법의 대표적인 예로 피보나치수열을 통해 알고리즘에 접근해보도록 .. 2021. 9. 1.
반응형

티스토리툴바