본문 바로가기

Java/알고리즘63

모음사전 문제이해에 한시간을 쏟았다. 결론을 낸건 DFS를 사용해서 풀어야 한다는 것이다. 내 이론은 이렇다. A시작점을 기준으로 왼쪽으로 X는 추가하지않는것이고, Ax, AAx, AAAx, AAAAx, AAAAA, AAAAE,AAAAI, AAAAO, AAAAU, 다시 한칸 더 위로가서, AAAEx, AAAEA, AAAEE.... 이런식으로 완전탐색으로 풀면되겠다 싶었다. 하지만 나의 능력의 한계에 부딪혀 결국 치트키를 썼다. 그래서 얻어낸 코드를 보며 코드의 설명을 해보겠다. public class Main { static final char[] WORDS = {'A', 'E', 'I', 'O', 'U'}; static final int MAX_LENGTH = 5; public static int solutio.. 2023. 11. 1.
알고리즘 공부(3) - 완전탐색을 알아보자 ㅇ 완전탐색이란? 가능한 모든 경우의수를 다 체크해서 정답을 찾는 방법. 3자리수 자물쇠가 있다면 000부터 999까지 모든 경우의수를 다 따져보는것이다. 이렇게 되면 효율성은 떨어질 수 있으므로 문제에 대한 파악이 중요하다. ㅇ 완전탐색의 방법 - Brute Force : 반복/조건문을 활용해 모두 테스트하는 방법 - 순열 : n개의 원소중 r개의 원소를 중복허용없이 나열하는 방법 - 재귀 호출 - 비트 마스크 : 2진수 표현기법을 활용하는 방법 - BFS, DFS를 활용하는 방법 ㅇ Brute Force 기법 public class BruteForceExample { public static void main(String[] args) { int[] numbers = {1, 2, 3, 4, 5, 6,.. 2023. 10. 31.
게임 맵 최단거리 이건 지금 내 레벨이 아니라 느끼고 풀이를 보고 그냥 완전탐색을 공부하기로 합의봤다ㅎ 일단 코드를 보자. ㅇ 코드 class Solution { public int solution(int[][] maps) { int n = maps.length; //maps의 행 수 int m = maps[0].length;//maps의 열 수 int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 동, 남, 서, 북으로의 이동 Queue queue = new LinkedList();//BFS를 위한 큐 초기화 queue.offer(new int[]{0, 0, 1}); // 시작 지점 (0, 0)에 도착했으므로 거리는 1 while (!queue.isEmpty()) {//큐가 비.. 2023. 10. 31.
N진수 게임 점점 알고리즘 문제가 어려워진다. 대충 머리로는 어떻게 풀진 알거같아서 일단 풀어봤는데 벽을 느끼고 포기했다. 내가 먼저 시도했던 수도코드를 보면 // int[] arr = new int[m*t]; // 0부터 arr.length까지반복문돌면서 i를 Integer.toString(i,n) n진수로 변환하고 // n진수로 변환한 i가 2자리 이상일때, 각 자리수를 다시 int로 변환해 arr[]에다가 집어넣는다. 그런데 코드를 짜다 보니 arr[]에 집어넣는 과정이 굉장히 까다로웠다. 그래서 다시 다른 방법으로 풀려다가 벽에 부딪혔다... 같이 문제를 푼 영재님은 JavaScript를 사용해서 푸셨는데, 킹갓 영재님의 풀이를 보자 function solution(n, t, m, p) { let numRan.. 2023. 10. 30.

티스토리툴바