본문 바로가기

알고리즘231

[알고리즘 이론] 동적계획법(Dynamic Programming, DP) 이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘이다. 동적계획법 알고리즘은 복잡하고 여러개의 연산이 있는데.. 작은 단위를 연산을 한다음 반복되거나 중복 되는 연산은 최소화 해서 풀어 나가는 알고리즘이다. 동적계획법은 시간 복잡도상에서 최적으로 나타낼수있는 강력한 알고리즘이지만 완벽한 알고리즘이라고 할수는 없다. dp로 해결하는 이유는 메모리 절약과 시간복잡도의 최적화로 되어 있지만 문제 푸는데는 어느정도 한계가 있고 이론보다는 접근 방법이나 아이디어가 더 많이 요구되기도 한다. 자세한 설명은 아래 사이트에서 찾아 보면된다. https://ko.wikipedia.or.. 2022. 12. 14.
[BAEKJOON] 11725 트리의 부모 찾기 문제 요약 알고리즘 분류: 트리, 탐색 난이도: Silver2 문제내용: 루트가 1이라고 가정할때 2번 노드부터 N개까지의 부모노드를 출력해라. 사이트: https://www.acmicpc.net/problem/11725 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제풀이 이번 문제는 트리의 활용과 트리의 탐색에 대한 내용을 알고있으면 풀수있다고 생각한다. 트리에 대한 자세한 설명은 여기에서 확인 해보면 된다. 문제 접근 방법 일단 예제 1번을 그림 으로 대충 표현한다면 아래와 같다. 왼.. 2022. 12. 13.
[알고리즘 이론] 트리(Tree) 이론 이번에 볼 자료구조는 트리이다. 트리는 연결리스트(Linked List)에서 노드간의 부모와 자식을 갖는 자료 구조이다. 연결리스트는 앞과 뒤로 이루어 져 있는데 트리는 계층별로 상하 관계로 되어 있는 구조이다. 트리는 코딩테스트 뿐만 아니라 실무나 실생활에서도 많이 접하기 때문에 반드시 알아야 될 기본 자료구조이다. 자세한 설명은 밑에 사이트에 참조하면된다. https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84) 트리(그래프) - 나무위키 트리를 정의할 때에는 다양한 정의가 쓰이고, 다음은 모두 동치이다. GGG는 회로가 없는 연결 그래프이다.GGG는 회로가 없고, 단순 그래프의 형태를 유지하면서 간선을 추가할 경우 회로가 생긴다 .. 2022. 12. 13.
[BAEKJOON] 23757 아이들과 선물 상자 문제 요약 알고리즘 분류: 힙, 우선순위 큐, 자료구조 난이도: Silver2 문제내용: 선물N개와 아이들 M개가 있다. 아이들은 순서대로 선물 N개 선택할수 있고 이전에 선택된 선물을 또 선택가능하다. 아이들이 원하는 선물개수가 없는 경우 실망한다. 아이들이 실망 하지 않고 선물을 다 가져 갈수 있는지 확인해라.. 사이트: https://www.acmicpc.net/problem/23757 23757번: 아이들과 선물 상자 모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 $1$을, 그렇지 않으면 $0$을 출력한다. www.acmicpc.net 문제풀이 이번 각 10^5개 데이터라서 O(NM)으로 풀면시간이 초과가 된다. 그래서 O(MlogN)이 나오도록 처리를 해야 한다. 그러기.. 2022. 12. 12.
[BAEKJOON] 15654 N과 M (5) 문제 요약 알고리즘 분류: 백트래킹 난이도: Silver3 문제내용: N, M 가 주어 졌을때 1 ~ N수 에서 중복된 숫자가 없고 크기 순으로 출력하면 된다. 중복되는 수열은 여러번 출력하면 안된다. 사이트 주소: https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제풀이 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다. https://jih3508.tistory.com/84 [알고리즘 이론] .. 2022. 12. 9.
[알고리즘 이론] 백트래킹(Backtracking) 이론 이번에 볼 알고리즘은 백트래킹이다. 백트래킹을 알아두면 대부분 해를 찾는데 도움이 될것이다. 백트레킹은 탐색하는 도중 중복되거나 해를 찾는 방향이 맞지 안 맞으면 그 부분을 탐색하지않는다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 이러면 불필요한 탐색을 할 필요가 없어서 기존 완전 탐색보다 시간적이나 메모리가 단축할수 있다. 자세한것은 아래 사이트에서 확인해보면된다. https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89 퇴각검색 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 퇴각검색(영어: backtracking, 한국어: 백트래킹)은 한정 조건을 가진 문제를 풀.. 2022. 12. 9.

티스토리툴바