구름문제 IDE 문제 6~8

배운점 ✨

1) 완전 탐색의 의미

그동안 for문을 이용해서 모든 경우의 수를 구해본적은 있었는데 그게 완전탐색이라는 것을 알게 되었다.

완전탐색(Exhaustive Search)은 컴퓨터 과학 및 알고리즘 이론에서 사용되는 개념이다. 이 방법은 가능한 모든 경우의 수를 시도하고 조사함으로써 문제를 해결하려는 접근법을 나타낸다. 다른 말로는 브루트 포스(Brute Force)라고도 한다.

완전탐색은 주로 주어진 문제의 모든 가능한 해답을 찾는데 사용된다고 한다. 이를 위해 모든 조합이나 순열을 시도하여 최적의 해답이나 원하는 결과를 찾아내는데, 하지만 이 방법은 가능한 경우의 수가 많을 경우에는 계산비용이 매우 크다는 단점이 있다고 한다.

나중에 경우의 수가 적을 경우에는 완전탐색을 활용하고, 경우의 수가 많거나 문제가 복잡한 경우에는 보다 효율적인 알고리즘 기법들을 고려하여 문제를 해결해야 겠다!

2) Hashet과 HashMap

문자열 나누기 문제를 보면서 HashSet과 HashMap의 차이점을 잘 알아두어야겠다고 느꼈다. 그래서 둘의 차이점에 대해 알아보도록 하겠다!

먼저 HashSet과 HashMap은 자바 프로그래밍 언어에서 제공되는 두 가지 중요한 컬렉션 클래스이다. 이들은 데이터를 저장하고 관리하는 데 사용되며 각각 다른 목적과 특징을 가지고 있다.

2-1) HashSet의 특징

• HashSet은 중복되지 않는 원소들의 집합을 저장하는 데 사용되는 클래스이다.
• 순서를 보장하지 않으며, 순서가 중요하지 않은 데이터를 저장할 때 사용된다.
• 원소들 간에는 동등성(Equivalence) 비교를 통해 중복을 허용하지 않는다.
• 해시 함수를 사용하여 원소의 저장 및 검색 속도를 빠르게 유지한다.
• 예를 들어, 어떤 항목이 HashSet에 이미 존재하는지 빠르게 확인하고자 할 때 유용하다.

2-2) HashMap의 특징

• HashMap은 (키, 값) 쌍을 저장하는 데 사용되는 클래스로, 각 키는 고유한 값을 가지고 해당 값과 연결된다.
• 순서를 보장하지 않으며, 순서가 중요하지 않은 키-값 쌍을 저장할 때 사용된다.
• 키는 중복될 수 없으며, 중복된 키를 사용하면 이전 값이 덮어쓰여진다.
• 해시 함수를 사용하여 키의 저장 및 검색 속도를 빠르게 유지한다.
• 예를 들어, 특정 키에 해당하는 값을 빠르게 찾고자 할 때 유용하다. 대표적으로 데이터베이스에서 ID와 해당하는 데이터를 매핑하는 데 사용될 수 있다.

두 클래스 모두 hashCode()와 equals() 메서드를 이용하여 해시 기반의 저장 및 조회를 수행한다. 만약 사용자 정의 클래스를 HashSet이나 HashMap의 원소로 사용하려면 이러한 메서드를 적절하게 오버라이딩하여 동등성 비교를 정의해야 한다.

예시 코드

// HashSet 예시
HashSet<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("apple"); // 중복된 값이므로 추가되지 않음

// HashMap 예시
HashMap<String, Integer> map = new HashMap<>();
map.put("one", 1);
map.put("two", 2);
map.put("three", 3);

int value = map.get("two"); // key가 "two"에 해당하는 값을 가져옴

이러한 컬렉션 클래스들은 자바에서 데이터를 보다 효율적으로 관리하고 처리하는 데 도움을 준다고 한다!

3) dx/dy 기법

이 기법을 활용하여 다른 문제들도 풀어 본적이 있는 데 이게 dx/dy 기법이라는 이름 이었다는 것을 처음 알게 되었다.😲

dx/dy 기법은 주로 2차원 배열에서 사용되는 기법이다. 간단하게 하면 현재 내 위치에서, 상하좌우, 대각선 방향으로 이동이나 탐색을 구현할 때 사용한다.

이동의 중심은 항상 현재 위치 이다. 현재 위치에서 상하좌우의 인덱스를 만들어내는 방법이다. 각각의 위치의 인덱스를 표현하고, 이 인덱스의 arr[1][1] 위치에서 상하좌우의 좌표를 확인하면 좌우는 열의 좌표가 +1되거나 -1이 되고, 상하는 행의 좌표가 +1 되거나, -1이 된다는 특징이 있다.

이 점을 이용한 것이 dx/dy 기법이라고 한다.

arr = 
[
  [ '0, 0', '0, 1', '0, 2' ],
  [ '1, 0', '1, 1', '1, 2' ],
  [ '2, 0', '2, 1', '2, 2' ]
]

arr[1][1] 의 상하좌우의 값은 arr[0][1], arr[2][1], arr[1][0], arr[1][2] 이다. 이를 인덱스로 표현하면 다음과 같이 표현할 수 있다.

int[] dx = {0, 0, -1 -1};
int[] dy = {1, -1, 0, 0};

그리고 각각의 인덱스를 접근할 때, 반복문을 사용하면 된다. 아래 코드의 결과를 봤을 때, arr 배열에서 상하좌우를 잘 탐색하고 있는 것을 확인할 수 있다.

int[] dx = {0, 0, -1 -1};
int[] dy = {1, -1, 0, 0};

// 시작 위치 설정
int x = 1;
int y = 1;

// 4방향 탐색
for (int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    System.out.println(nx + " " + ny); // 1 0\n 1 2\n 0 1\n 2 1
}

구름 찾기 문제는 대각선 방향도 포함하고 있기 때문에, 아래의 8 방향으로 표현할 수 있다. 또 탐색을 할 때는 올바른 탐색 위치인지 항상 확인해야 한다. 이 경우에는 배열 밖을 나가는 탐색을 올바른 탐색 위치가 아니기 때문에, 만약에 다음 탐색할 위치가 2차원 배열 밖이라면 탐색 하지 않게 해야 한다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
				..code

        int[] dx = {0, 0, 1, 1, 1, -1, -1, -1};
        int[] dy = {1, -1, 1, 0, -1, 1, 0, -1};
				int x = 1;
				int y = 1;
        if (matrix[x][y] == 0) {
            for (int i = 0; i < 8; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
									..code
                }
            }
		    }
		}
}

4) 그리디 알고리즘

통증 문제를 통해 그리디 알고리즘에 대해 처음 알게 되었다.

그리디 알고리즘은 보통 탐욕법이라고 번역을 하곤 한다. 말 그대로 문제를 해결할 때 있어서 현재 경우만 고려해서 최적의 상황을 선택하는 방법이다.

당연하게도 이런 선택이 항상 최적해를 구할 수 있는 방법은 아니기 때문에, 항상 사용할 수 있는 방법은 아니다. 하지만 다음 두 가지 조건이 성립한다면 그리디 알고리즘을 기계적으로 적용할 수 있다고 알려져 있다.

• 현재의 최적의 선택이 다음 선택에 영향을 미치지 않는다.
• 현재의 선택이 최종 선택의 최적 해결 방법에 포함된다.

이 내용만 얼핏 봐선 언제 그리디 알고리즘을 적용할 수 있는지 알기 어렵다. 실제로 어떤 문제에 대한 사전 지식이 없이, 그 문제를 그리디로 해결할 수 있을지 증명하는 것은 어렵다.

하지만 일반적인 코딩 테스트 정도의 레벨에서 나오는 유형은 한정되어 있다. 따라서 자주 나오는 몇 가지 상황에 대해 그리디로 해결할 수 있음을 알고 있으면, 이를 응용하는 문제를 만났을 때 훨씬 편하게 대처할 수 있을 것이라고 한다.

그리디 알고리즘에 대해 더 자세히 알기 위해 거스름돈 문제를 예로 들어 공부해 보았다.

주어진 동전의 종류와 거슬러줘야 할 금액을 입력으로 받아 최소한의 동전 개수로 거스름돈을 주는 그리디 알고리즘을 구현

import java.util.Arrays;
public class GreedyCoinChange {
    public static int minCoins(int[] coins, int amount) {
        Arrays.sort(coins); // 동전 종류를 오름차순으로 정렬
        int count = 0; // 거스름돈 동전 개수
        int index = coins.length - 1; // 가장 큰 동전부터 시작
        while (amount > 0) {
            if (index < 0) {
                System.out.println("거스름돈을 주기 위한 동전이 부족합니다.");
                return -1;
            }
            if (coins[index] <= amount) {
                int numCoins = amount / coins[index];
                count += numCoins;
                amount -= numCoins * coins[index];
            }
            index--;
        }
        return count;
    }
    public static void main(String[] args) {
        int[] coins = { 500, 100, 50, 10 };
        int amount = 1260;
        int result = minCoins(coins, amount);
        if (result != -1) {
            System.out.println("거스름돈 동전 개수: " + result);
        }
    }
}

위 코드에서 minCoins 메서드는 주어진 동전 종류(coins)와 거슬러줘야 할 금액(amount)을 입력으로 받아 최소한의 동전 개수로 거스름돈을 주는 그리디 알고리즘을 구현했다. coins 배열은 동전의 종류를 나타내며, 큰 동전부터 시작하여 거슬러주는 방식으로 동전의 개수를 계산한다.

느낀점 ✍🏻

문제의 난이도가 점점 높아졌다는 것이 느껴졌고, 내 실력도 바닥이라는 것을 다시금 깨달았다. 🥲
하지만 문제 해설을 보면서 내가 몰랐던 부분을 잘 체크해 보고 나중에 다른 코딩테스트 문제를 풀었을 때 적용해보기로 마음 먹었다!! 화이팅🫠

어려웠던 점 🤔

어려웠던 점은 문제를 읽으면서 내가 이해하고 있는게 맞나? 싶을 정도로 문제를 이해하지 못했던 부분 이었던 것 같다...

구름톤 챌린지가 뭔지 궁금하다면?
https://9oormthonchallenge.oopy.io/
학습 일기 작성법이 궁금하다면 ?
https://9oormthonchallenge.oopy.io/blogeventguide