본문 바로가기

Java107

알고리즘 공부(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.
압축 ㅇ 1트 먼저 길이가 자유로운 리스트에다가 알파벳을 순서대로 집어넣었다. 완벽히 풀진 않았지만 1트에서 구현 하고자 했던건 KAKAO가 주어질때, KAKAO를 alp에서 찾고 없으면 KAKA를 찾고 없으면 KAK를 찾고 없으면 KA를 찾고 없으면 K를 찾고 있으니,K의 index인 11를 ans 리스트에 집어넣는것과 KA를 alp에다가 넣는것 까지 구현했다. ans를 리스트로 만든이유는, 반복문을 돌 때 언제끝날지 모르기 때문에 add를 쓰면 쉬워지기 때문에 리스트로 썼다. 이제 구현해야하는건, 그 다음에 AKAO부터 차례로 다시 검증해가면서 index를 ans에 집어넣고, AK를 alp에 넣는것이다. 이렇게 마지막 까지 반복하는거다. public static int[] solution(String ms.. 2023. 10. 26.

티스토리툴바