본문 바로가기

Algorithm16

[Algorithm] 백트래킹 (Backtracking) 1. 백트래킹이란? 백트래킹은 모든 조합의 수(완전 탐색)를 조건이 만족할 때(유망할 때)만 살펴보는 것이다. Backtracking은 임의의 집합(set)에서 주어진 기준(criterion)대로 원소의 순서(sequence)를 선택하는 문제를 푸는 데 사용한다. 2. DFS VS Backtracking (1) DFS DFS는 가능한 모든 경로를 탐색한다. 불필요한 것 같은 (유망하지 않은) 경로도 탐색하기 때문에 경우의 수를 줄이지 못한다. (2) Backtracking (DFS + 조건) DFS를 통해 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아간다. 백트레킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다. DFS .. 2022. 1. 21.
[Algorithm] 완전탐색 (BruteForce) 완전탐색 (BruteForce) 문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법 모든 코테 문제에서 기본적으로 접근해 봐야 한다. 완전 탐색 문제를 접근할 때 중복과 순서를 신경써서 구현해야 한다. 1. 중복 O, 순서 O (1) 문제 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1부터 N까지 자연수 중에서 M개를 고른 수열 ex) N=4, M=2 (1 1), (1 2), (1 3), (1 4) (2 1), (2 2), (2 3), (2 4) (3 1), (3 2), (3 3), (3 .. 2022. 1. 21.
Greedy Algorithm (그리디 알고리즘) 현재 사황에서 지금 당장 좋은 것만 고르는 방법 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서 고려하지 않는다. 1. Example. 거스름돈 (1) 문제 거스름돈으로 사용한 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소의 개수를 구하여라. (2) 문제 해설 그리디 알고리즘을 이용해 풀어 보자. 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다. 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 그다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다. (3) 소스 코드 publi.. 2021. 11. 5.
[프로그래머스] 전화번호 목록 (JAVA) 1. 문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. 2. 문제 풀이 (1) 정렬 후 String 클래스 Method를 이용한 풀이 import java.util.Arrays; import java.util.Collections; cla.. 2021. 10. 15.
반응형

티스토리툴바