본문 바로가기

Algorithm43

[SWEA] 자바 1247 최적경로 접근 방안 : 완전 탐색(DFS) 고객의 집 방문 순서에 대해 하나씩 방문해보면서 총 이동 경로를 구했습니다. 재귀함수를 통해 이와 같은 로직을 구현했습니다. 또한, 마지막 고객의 집에 방문한 경우 구하고자 하는 답의 값을 갱신해주었습니다. 실행시간 단축을 위한 추가 개선 사항 비트 연산자를 통해 사용해 풀어볼 수 있습니다. flag와 1 2022. 8. 21.
[Algorithm] 순열, 조합 구현 순열 : 서로 다른 n개의 수에서 r개를 뽑아서 정렬하는 경우의 수( nPr 로 표현된다.) 순열은 순서를 생각해서 뽑아야 한다. 예를 들어 {1,2,3,4,5} 중에서 3개의 수를 뽑아야 하는 경우 {2,3,4}와 {2,4,3} 은 다른 경우의 수로 카운트된다. 재귀를 통해 구현할 수 있다. 순열을 구현하기 위해서는 함수 안에서 현재 수를 뽑고 다음수를 뽑기 위해 재귀함수를 호출한다. 특히, 중복순열과는 다르게 순열은 중복해서 수를 뽑을 수 없기 때문에, 현재 수를 뽑았는지를 확인하기 위해 boolean배열을 사용한다. public class PermutationTest { private static int N;//총 개수 private static int R;//뽑을 개수 private static .. 2022. 8. 20.
[백준] 백설 공주와 일곱 난쟁이(자바) 문제 방안 도출 : 아홉 난쟁이 중에서 총합이 100이 되는 일곱 난쟁이를 찾는 문제이므로, 모든 경우의 수를 확인해야한다고 생각했다. 따라서, 이와 관련된 알고리즘인 브루트포스 알고리즘을 도출할 수 있었다. 접근 유형 : 브루트포스 알고리즘 브루트포스 알고리즘 모든 경우의 수를 탐색하면서 조건에 만족하는 결과를 찾는다. 이와 같은 알고리즘은 for문, 재귀, DFS, BFS 등을 사용하여 해결할 수 있다. package com.algorithm.boj; import java.util.Scanner; /* * 일곱난쟁이들의 모자 합은 100이 되어야함 * 접근 유형 : 브루트포스 알고리즘 * */ public class Main_3040 { private static int[] hat; private s.. 2022. 8. 11.
[백준] 6603번 로또 (자바) 접근 방법 처음에는 그냥 재귀로 탐색하여 풀었으나 순서만 다른 같은 로또 번호 배열이 출력되었습니다. 따라서, 조합이라는 방법을 생각했습니다 조합 : n개의 원소 중에서 r개를 순서 없이 뽑는 경우의 수를 의미합니다. package com.algorithm.boj.recursive; import java.util.Scanner; /* * 문제 : 백준 6603번 로또 * 접근 유형 : 재귀, 조합 * 1. 로또 번호의 순서와 상관없이 선택해야하므로->조합 * */ public class Main_6603 { static int k; static boolean[] check; static int[] lotto; static int[] temp = new int[6]; public static void ma.. 2022. 8. 9.

티스토리툴바