본문 바로가기
728x90

알고리즘과 자료구조21

[BOJ]#15649 N과 M (1-기본순열) JAVA 문제 풀이 [silver 3] 백트래킹 유형, 백준 15649번 문제(N과 M 1)를 풀어보고자 한다. | 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 | 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) | 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. | Code import java.io.*; import java.util.*; public class Main { public static int N; publ.. 2021. 3. 2.
BOJ 백준 1904(JAVA) 문제 풀이 [silver 3] DP 유형, 백준 1904번 문제(01타일)를 풀어보고자 한다. (오랜만에 포스팅 📢그럼에도, , ) 이 문제를 포스팅하는 이유는, , , 어렵지 않은(정말 쉬운 ,, )문제지만 , , 담부턴 똑같은 실수를 하지 않고자 ! 산전수전 우여곡절😂 풀었던 문제였기 때문에 기록하고자 한다. 🧐 | 문제 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. (못됐다) 결국 현재 1 하나만으로 이루어진 타일 또는 0 타일을 두 개 붙인 한 쌍의 00 타일들만.. 2021. 2. 17.
[개념] 최단경로 알고리즘 최단 경로는 보통 그래프로 표현한다. 3가지의 최단 거리 알고리즘이 있다. (1) 다익스트라 최단 경로 알고리즘 O(ElogV) : 한지점에서 다른 모든 지점까지 한 지점에서 다른 모든 지점까지의 최단 경로를 계산한다. * 우선순위 큐가 사용된다. (2) 플로이드 알고리즘 O(V^3) : 모든 지점에서 다른 모든 지점까지 모든 지점에서 다른 모든 지점까지의 최단 경로를 계산한다. *3중 for문이 사용된다. (3) 벨만 포드 알고리즘 🐾추후 관련 백준 문제 풀이 예정🐾 ps.이 내용은 자료구조 시간때 배웠었는데 C로 다루다 보니, JAVA로 다루는 연습을 다시 해야겠다. 2021. 2. 5.
[개념] 그래프 이론 알고리즘 그래프를 활용하여 풀 수 있는 알고리즘 유형에 대해서 정리한 포스팅이다. 📌서로소 집합 공통 원소가 없는 두집합 이때 집합 간의 관계를 파악하기 위해 서로소 집합 알고리즘을 사용할 수 있는데 , 서로소 집합 알고리즘은 union-find연산으로 구성되며, 모든 노드는 자신이 속한 집합을 찾을 때 루트 노드를 재귀적으로 찾는다 📌신장 트리 하나의 그래프가 있을 때 모든 노드를 포함하는 부분 그래프를 의미한다. 일반적인 그래프에서 신장 트리를 추출하는 예시는 다음 그림과 같다. 주로 현실세계에서 '모든 섬을 도로를 이용해 연결하는 문제'등에서 사용된다. 📌크루스 칼 알고리즘 가능한 최소 비용의 신장 트리를 찾아주는 알고리즘이다. 시간 복잡도는 O(ElogE) 간선을 정렬한 뒤에 간선의 비용이 작은 순서대로 .. 2021. 1. 31.
[개념] 백트래킹 Backtracking 알고리즘 | 백트래킹 '가능한 모든 방법을 탐색한다' 즉, 완전 탐색 기법이다. | 완전 탐색기법인 DFS와의 차이점 DFS는 현재 지점에서 방문할 곳이 있으면 재귀 호출을 이용해서 계속 이동한다. 무한히 깊은곳을 찾아야 할때 효과적이다. 하지만, 모든 곳을 방문하기 때문에 굳이 목표 지점이 있지 않는 경로를 탐색한다면 비효율적인 시간이 소요될수있다. 그래서 비효율적인 경로를 차단 ! 하고 목표지점에 갈수있는 가능성이 있는 루트를 검사하는 방법이 '백트래킹 알고리즘'이다. 즉, DFS에서 가지 않아도 되는 루트는 탐색하지 않는 완전 탬색 기법이다. 가지치기를 얼마나 잘하느냐에 따라 효율이 극대화 될수 있는 방법이다. *배제 해야할 조건과 *풀이 시간 단축에 힘을쓰도록 하자. 2021. 1. 29.
728x90