728x90

목록완전탐색 (6)

mondegreen

[240417] 알고리즘 리부트 50일차 - 프로그래머스 모음사전 자바

기본적으로 재귀의 방식으로 구현하면 된다. 다섯가지의 문자로 길이 5의 문자열을 만드는 경우의 수가 5000가지 이하이므로 시간을 고려하지는 않았다. 그래도 글자에 + 하는 건 비효율이라고 생각해서 스트링빌더를 사용했다. 그리고 오래 가지 않도록 답을 찾으면 return 하도록 구현했다. import java.util.*; class Solution { public static char [] arr = {'A', 'E', 'I', 'O', 'U'}; public static String target; public static int tmp, answer; public int solution(String word) { tmp = 0; answer = -1; target = word; StringBuilde..
알고리즘 풀이 및 리뷰/프로그래머스 2024. 4. 18. 23:17
[240402] 알고리즘 리부트 44일차 - 프로그래머스 전력망 둘로 나누기 자바

그래프 너무 어렵지만.. 가중치가 없는 그래프이니까 다익스트라 제외, 최단경로가 아니라 어디까지 이어져 있는지가 중요하니까 BFS가 아닌 DFS로 구현하기로 결정했다. 보통은 두개의 트리로 분리되어 있는 송전탑을 하나의 트리로 연결시키라고 하면 너무...정말... 유니온파인드 써서 쉽게 처리하겠지만 이건 반대로 한개를 두개로 나누라고 하니 풀이방법을 찾지 못했다. 아래는 책을 참고해서 푼 로직이다. 답인 answer는 최대값인 n-1로 설정한다. 그 이유는 다른 한쪽이 한 개의 송전탑으로 이루어진 경우에 가장 큰 차이를 가지는 때이므로 n-1로 초기화해준다. DFS부분이 문제인데 송전탑을 하나씩 연결해가면서 나머지 송전탑 무리들과의 차이를 최솟값으로 갱신해나간다. 그래서 현재 송전탑이 연결된 것으로 가정..
알고리즘 풀이 및 리뷰/프로그래머스 2024. 4. 3. 11:03
[240217] 알고리즘 리부트 9일차 - 백준 3085 자바

[Part1-Chapter04-Clip05] - 백준 3085 사탕게임 시간이 많이 걸린 문제였다. 처음에 시간 복잡도를 최대한 줄여보겠다고 한 행과 열에 등장하는 색을 체크하고 수가 적은 행열만 반복하려다가 행과 열을 구분해서 작성하게 되고 오히려 코드가 길어져서 포기했다. 다시 고민해보니 차라리 사방탐색을 하며 경계 체크하고 다르면 바꾸고 해당 요소가 속한 행렬에서 최대 연속 수를 구하는 방식으로 구현했다. 오히려 코드가 명료해졌고 인접한 사탕이 다른 경우에만 바꾸고 시간 복잡도를 고려해 그 사탕이 속한 행렬만 체크하도록 구현했기 때문에 추가로 원래 배열인 경우에도 최대 연속의 수를 구하도록 했다. 이 글을 작성하다 보니 이렇게 풀면 안되었나.. 바꾸고 모든 행렬을 보아야했을까? 라는 생각이 든다. ..
알고리즘 풀이 및 리뷰/[패캠] 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 리뷰 2024. 2. 17. 22:56
[240216] 알고리즘 리부트 8일차 - 백준 10448, 11005, 11068 자바

[Part1-Chapter04-Clip02] -백준 10448 유레카 이론 아무리 생각해도 재귀가 아니라면 반복문을 3중으로 돌리는 수밖에 없다고 생각해서 아래와 같이 3중 반복문을 구현하여 돌렸다. 불필요한 순회를 줄이기 위해 찾으면 바로 반복문을 빠져나오도록 처리했다. package BaekJoon.bruteforce; import java.util.Arrays; import java.util.Scanner; public class BJ10448 { public static void main(String[] args) { solve(); } private static void solve() { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); S..
알고리즘 풀이 및 리뷰/[패캠] 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 리뷰 2024. 2. 16. 21:50
[240215] 알고리즘 리부트 7일차 - 백준 10989, 3273 자바

[Part1-Chapter03-Clip04] -백준 10989 수 정렬하기 3 위 문제는 시간 제한과 메모리 제한이 비교적 있는 편이라 단순히 삽입 정렬을 할 수는 없었다. 최악의 경우 모든 숫자를 배열에넣고 단순히 sort 매서드를 쓰기에는 메모리 제한에 걸리기 때문에 그렇게 풀 수 는 문제는 아니었고. 정수배열의 경우 인덱스 하나당 4바이트 인데 모든 수를 배열에 넣는다면 4천만 바이트로 메모리 제한에 걸리기 때문에 불가. 주어지는 수의 갯수는 천개 이지만 수의 종류가 최대 10000이기 때문에 카운팅 배열을 활용하고자 했다. 입력을 받으며 해당하는 인덱스에 갯수를 늘려주고 입력되는 수의 최대값을 구해 놓으면 반복문을 돌 때 그 수를 줄일 수 있을 거라고 생각했다. 카운팅 배열에 오름차순으로 값을 넣..
알고리즘 풀이 및 리뷰/[패캠] 핵심유형 20개로 한 번에 끝내는 알고리즘 코딩테스트 리뷰 2024. 2. 15. 13:44
완전검색(Brute Force, Generate and test)

완전 검색이란 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법으로서 상대적으로 빠른 시간 내에 알고리즘 설계가 가능하다. 경우의 수가 적을 때 유용하며, 모든 경우의 수를 생성한 후 테스트하기 때문에 수행속도는 느리지만 해답을 찾지 못할 가능성이 현저히 낮다. ** 완전 검색을 이용한 Baby-gin 1) 6개의 숫자로 만들 수 있는 모든 경우의 수를 나열한다 => 중복을 포함한 순열 2) 앞 3개의 숫자, 뒤 3개의 숫자를 구분하여 run(연속된 수) 또는 triplet(동일한 수) 여부를 판단한다. 완전 검색은 전형적으로 순열, 조합, 부분집합과 같은 조합적 문제와 연관되어 있다. ** 검색 기법 https://rileylee.tistory.com/5 검색 검색이란 저장된 ..
알고리즘 풀이 및 리뷰/알고리즘 이론 2023. 6. 5. 18:35
728x90
이전 Prev 1 Next 다음