24년 8월 23일 알고리즘 공부 시작

https://www.youtube.com/watch?v=O9aQXFTbCDY

 

이제 다시 시작이다. 

알고리즘부터 부숴보도록 한다. 

 

튜터님께서 나에게 플레티넘을 찍으라는 명령을 주셨다. 

 

먼저 알고리즘이란 무엇일까. 

바로 선생 GPT에게 물어본다. 

 

 

알고리즘이란

어떤 문제를 해결하기 위한 단계적 절차라고 한다. 쉽게 말해서 어떠한 일을 효율적으로 처리하기 위해 필요한 지침서 같은 거라고 한다. 

 

알고리즘 문제풀이란 것은 주어진 문제를 해결 하기 위해 적절한 알고리즘을 설계하고, 이를 코드로 구현하는 과정을 말하는 것이었다. 뭐야 지금까지 한 거였잖아??

 

코딩테스트 문제는 보통 특정한 상황이나 문제를 제시하고, 그 문제를 효율적으로 해결 할 수 있는 프로그램을 작성 하도록 요구한다. 그래서 시간복잡도? 그런 걸 계산 하는 것 같다. 

 

GPT가 알려주는 알고리즘 문제풀이의 과정 

1. 문제 이해하기 : 문제를 읽고 요구사항을 정확히 파악 해야 한다. 

예를 들어, 숫자 목록을 오름차순으로 정렬 해야 하는 문제라면, 어떤 입력이 주어지고 어떤 출력을 만들어야 하는지 이해 해야 한다. 뭔소리임?

 

2. 알고리즘 선택 및 설계 : 문제를 해결 할 수 있는 방법을 고민한다. 

이 때 다양한 알고리즘 중에서 가장 적절한 것을 선택 해야 하는데, 예를 들어 정렬문제라면 버블 정렬, 퀵 정렬, 병합 정렬 등의 알고리즘 중 하나를 선택 할 수 있다고 한다. 선택한 알고리즘이 문제의 조건을 충족하고, 효율적인지 고민 하는 것도 중요하다고 한다. 

 

3. 코드 구현하기 : 선택한 알고리즘으로 코드를 작성한다. 이 때, 언어의 문법과 알고리즘의 동작 방식을 잘 이해하고 있어야 한다. 

 

4. 테스트 및 디버깅 : 코드를 작성 한 후에 다양한 입력값을 넣어 테스트를 해준다. 문제가 생긴다면 디버깅을 통해 오류 해결

 

5. 최적화 : 필요에 따라 코드를 더 효율적으로 개선 할 수 있다. 예를 들어 시간복잡도나 공간 복잡도를 줄일 수 있는 방법을 찾는 것이다. 

 

그리고 코딩테스트에서 중요한 것은 정확성과 효율성이라고 한다. 알고리즘이 문제를 정확히 해결해야 하고, 제한 된 시간과 자원 내에서 빠르고 효율적으로 동작 해야 한다고 한다. 그래서 알고리즘 공부와 연습이 중요하다고 알려준다. 

 

자 이제 무슨 느낌인진 알았으니까 바로 실전 들어가기 전에 인강으로 공부 하라고 배웠으니 인강부터 알아봐야겠다. -> 안 알아봄.

 

 

 

알고리즘의 기초개념 이해하기

자료구조와 기본 알고리즘:

배열, 리스트 ,스택, 큐, 해시 테이블, 트리, 그래프 등 기본 자료구조와 정렬, 탐색 등의 알고리즘을 먼저 공부, 

이를 통해 문제를 해결 할 때 어떤 도구를 사용할지 결정 할 수 있다. 

 

시간 복잡도와 공간 복잡도:

알고리즘의 효율성을 평가하는 방법인 빅오 표기법을 이해 해야 한다. 

어떤 알고리즘이 더 빠르고 효율적인지 판단 하는 데 중요하다. 

 

 

그 다음에 문제풀이 연습

1. 쉬운 문제부터 시작.

2. 문제풀이 사이트 활용 : 

백준, 프로그래머스 활용해서 다양한 유형의 문제에 익숙해지기 

3. 반복 학습 

 

해결방법 분석하기 :

다양한 사람의 코드를 분석 하기. 다른 사람들의 코드를 이해 하는 거 너무 힘든데 연습해야 한다. 

다양한 접근법 시도 : 한 문제를 여러 가지 방법으로 풀어본다. 그러면 좋은 학습이 된다고 한다. 

 

심화 학습

기본 알고리즘에 익숙 해지면, 동적프로그래밍, 그래프 탐색, 이분 탐색, 최단 경로 알고리즘 등 심화 알고리즘을 공부해야 한다. 

수학적 사고력도 강화를 해야 한다. 쉽지 않다. 

 

 

 

시간복잡도와 공간복잡도

시간 복잡도와 공간 복잡도는 알고리즘의 효율성을 평가하는 중요한 개념이다. 

얼마나 빠르게 동작하는지, 얼마나 많은 메모리를 사용하는지를 측정한다. 

 

1. 시간 복잡도

알고리즘이 문제를 해결 하는 데 걸리는 시간을 입력 크기에 따라 표현 한거라고 한다. 입력 데이터가 커질 수록 알고리즘이 얼마나 느려지는지를 나타낸다. 

 

빅오 표기법 : 시간 복잡도는 보통 빅오 표기법으로 표현 돼 있다고 한다. 이 표기법은 알고리즘의 성능을 최악의 경우로 나타내며, 가장 중요한 연산의 횟수를 기준으로 시간 복잡도를 나타낸다고 한다. 

 

(빅오 표기법)

 

• O(1): 입력 크기에 상관없이 항상 일정한 시간이 걸려요. 예를 들어, 배열의 첫 번째 원소를 가져오는 연산은 O(1)입니다.
• O(log n): 입력 크기가 커질수록 연산 시간이 로그 함수처럼 증가해요. 예를 들어, 이진 탐색(Binary Search)은 O(log n)입니다.
• O(n): 입력 크기에 비례해 시간이 걸려요. 예를 들어, 배열의 모든 원소를 한 번씩 탐색하는 연산은 O(n)입니다.
• O(n log n): O(n)과 O(log n)을 결합한 시간 복잡도예요. 예를 들어, 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort) 알고리즘은 O(n log n)입니다.
• O(n^2): 입력 크기에 비례해 제곱 시간이 걸려요. 예를 들어, 이중 반복문이 있는 알고리즘은 O(n^2)입니다.
• O(2^n): 입력 크기가 커질수록 시간이 지수 함수처럼 급격히 증가해요. 예를 들어, 재귀적으로 모든 가능한 경우를 다 시도하는 알고리즘은 O(2^n)입니다.
• O(n!): 입력 크기 n에 대해 n 팩토리얼만큼 시간이 걸려요. 예를 들어, 순열을 모두 계산하는 알고리즘은 O(n!)입니다.

무슨 소리인지 대충 감은 오는 것 같은데, 한 번 해봐야 알 것 같긴 하다. 

 

 

2. 공간 복잡도

알고리즘이 문제를 해결 하는 데 필요한 메모리 양을 입력 크기에 따라 표현 한 것이다. 

 

• 고정된 공간: 알고리즘이 항상 일정한 양의 메모리를 사용하는 경우, 이는 O(1)의 공간 복잡도를 갖습니다. 예를 들어, 상수 개수의 변수만 사용하는 경우입니다.
• 입력 크기에 비례한 공간: 입력 크기에 비례해서 메모리가 필요한 경우, 이는 O(n)의 공간 복잡도를 가집니다. 예를 들어, 배열의 크기만큼 메모리를 사용하는 경우입니다.
• 추가 공간 사용: 알고리즘이 입력 데이터 외에 추가적인 데이터를 저장하기 위해 별도의 공간이 필요할 때가 있어요. 예를 들어, 재귀 함수에서 호출 스택이 깊어지면 그만큼 추가 메모리가 필요하죠.

이것도 무슨 소리인지 조금은 알 것 같다. 

 

 

시간 복잡도와 공간 복잡도 사이의 Trade-off

일반적으로 알고리즘을 최적화 할 때 시간 복잡도와 공간 복잡도  사이에 균형을 맞추는 것이 중요하다고 한다. 

때로는 속도를 높이기 위해 더 많은 메모리를 사용 하는 알고리즘이 필요 할 수 있고, 반대로 메모리를 절약 하기 위해 더 느린 알고리즘을 사용 할 수 있다고 한다. 이 선택은 문제의 요구사항에 따라 달라진다. 

 

약간 함수를 작성 할 때 꺼내오거나 계산 하는 함수를 만든 게 있으면 그걸 리턴 식으로 가져와서 변수에 저장 시키고 그 변수로 계속 작업 하면 계산을 몇 번 더 실행 할 필요가 없으니, 이걸 말 하는 것 같다. 메모리를 더 써서 빨리 하는 것? 같다. 

예시

• 배열의 모든 원소 합 구하기 (시간 복잡도 O(n), 공간 복잡도 O(1)):
  • 시간 복잡도: 배열의 모든 원소를 순회해야 하므로 O(n).
  • 공간 복잡도: 별도의 메모리 없이, 합계를 저장할 변수 하나만 필요하므로 O(1).
• 정렬된 배열에서 이진 탐색 (시간 복잡도 O(log n), 공간 복잡도 O(1)):
  • 시간 복잡도: 배열을 반씩 나누어 탐색하므로 O(log n).
  • 공간 복잡도: 추가 메모리 없이 인덱스를 조작하기만 하면 되므로 O(1).

음...,

 

시간 복잡도와 공간 복잡도는 알고리즘을 평가하고 선택 할 때 매우 중요한 요소다. 각 문제 상황에 따라 최적의 알고리즘을 선택 하기 위해 이 개념들을 잘 이해하고 있어야 한다. 

확인 했어. 그런데 암기는 안 돼. 

 

 

 

예제 문제 풀어보기

문제: 가장 큰 수 찾기

설명: 주어진 정수 배열에서 가장 큰 수를 찾는 알고리즘을 작성하세요.

입력: 정수 배열 arr (예: [3, 1, 4, 1, 5, 9, 2, 6, 5])

출력: 배열에서 가장 큰 수 (예: 9)

 

나라면 이렇게 할 것 같다. 

 

private int LookForArryLargeNumber()

{

int largeNum = 0; 

for(i = 0; i < arry; i++)

{

if ( largeNum > arry[i]) continue;

largeNum  = arry[i];

}

return largeNum;

}

 

이렇게 하면 시간복잡도가 O(9), 공간복잡도가 O(1) , 맞나?

 

해설 -> 

우리는 주어진 배열에서 가장 큰 수를 찾아야 해요. 이 문제는 단순히 배열의 모든 원소를 확인하면서 최대값을 갱신하면 해결할 수 있어요.

2. 알고리즘 설계

1. 배열의 첫 번째 원소를 현재 최대값(max_value)으로 설정합니다.
2. 배열의 나머지 원소들을 순차적으로 확인하며, max_value보다 큰 값을 찾으면 그 값을 새로운 max_value로 갱신합니다.
3. 배열의 모든 원소를 확인한 후, 최종적으로 max_value를 반환합니다.

이 알고리즘의 시간 복잡도는 O(n)입니다. 배열의 모든 원소를 한 번씩 확인하기 때문이에요.

5. 최적화 고려

이 문제는 매우 간단해서 추가적인 최적화는 필요하지 않아요. 그러나 빈 배열이 입력될 경우를 대비해, None을 반환하는 예외처리를 추가했습니다.

 

 

뭐 비슷한 것 같다. 그런데 시간 복잡도가 O(n)이라는데 배열 개수만큼이 아닌가보다. 

 

 

 

다음 문제

두 수의 합

설명: 정수 배열과 목표값이 주어졌을 때, 배열 내에서 두 수를 더해 그 합이 목표값이 되는 두 숫자의 인덱스를 찾는 문제입니다. 같은 요소를 두 번 사용할 수 없으며, 정답이 여러 개인 경우 그중 하나만 반환하면 됩니다.

입력:

• 정수 배열 nums (예: [2, 7, 11, 15])
• 목표값 target (예: 9)

출력:

• 두 수의 인덱스를 가지는 리스트 (예: [0, 1])

예시:

• 입력: nums = [2, 7, 11, 15], target = 9
• 출력: [0, 1] (nums[0] + nums[1] = 2 + 7 = 9)

조건:

• 배열에 반드시 답이 존재한다고 가정합니다.
• 시간 복잡도가 O(n) 이내로 효율적인 방법을 찾아보세요.

뭔 소리지?

====

깨달았다. 

 

겁나 복잡한 건줄 알았는데 겁나 쉽네. 한 가지 요소를 두 번 사용은 못한다자너!! 너무 어렵게 생각했나?!!?

 

private void 생략(int targetNum)

{

for(i = 0; 생략; i +2;)

{

if(arry.length > arry[i+1])

{

if(arry[i] + arry[i+1] == targetNum)

{

num[0] = i;

num[1] = i+1;

}

}

}

}

 

이렇게 하는 것 맞나? 반복문은 한 번 썻으니까 시간복잡도는 O(n)이 맞는 거겠지.

공간복잡도는 늘어난게 없으니까 O(n) 맞나?

 

내가 만든 알고리즘의 피드백 ->

private int[] findTwoSum(int[] arry, int targetNum) {
    int[] num = new int[2];
    
    for (int i = 0; i < arry.length - 1; i++) {
        if (arry[i] + arry[i + 1] == targetNum) {
            num[0] = i;
            num[1] = i + 1;
            return num;  // 찾으면 바로 반환
        }
    }
    
    // 답이 없을 경우
    return null;
}

 

나는 배열의 크기 이상으로 가지 못 하게 하기 위해서 조건문을 달았었다. 그런데 반복횟수에 -1 하는 방식으로 고쳤다. 그로 인해서 if조건문을 하나 줄일 수 있었다. if(arry.length > arry[i+1])

이 코드로 예외 처리를 해줬는데 할 필요가 없어진 것이다. 시간 복잡도는 O(n)이 맞고, (반복문을 통해 배열을 한 번 순회)

공간 복잡도는 O(1)이다. (추가적인 메모리 사용이 거의 없다.)

그런데 같은 수 한 번 더 못 쓰게 하려면 i++ 하는 게 아니라 i +2 해야 하는 게 아닌가?

 

 

그리고 GPT라면 어떻게 풀었을까 ->

import java.util.HashMap; 자바이긴 하다.

public class TwoSumSolution {
    public int[] findTwoSum(int[] nums, int target) {
        // 숫자와 인덱스를 저장할 해시맵 생성
        HashMap<Integer, Integer> map = new HashMap<>();
        
        // 배열 순회
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            
            // 목표값과 일치하는 값이 해시맵에 존재하는지 확인
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            
            // 해시맵에 현재 숫자와 인덱스 저장
            map.put(nums[i], i);
        }
        
        // 답이 없는 경우 null 반환 (사실상 문제에서 반드시 답이 존재한다고 했으므로 이 경우는 발생하지 않음)
        return null;
    }
}

 

해시맵을 하나 생성해서 사용을 했다. 

반복문을 돌릴 때 int를 생성하고 해쉬맵에 컨테인 있는지 확인 하고 있으면  map.get(complement), i 두 개를 리턴 시켜서 원하는 것을 찾게 했다. 

 

해쉬맵과 int를 사용해서 공간복잡도가 안 좋아지긴 했지만 굉장히 빠르게 찾아낼 것 같은 방법이다. 

 

해설

1. 해시맵의 역할: 해시맵은 각 숫자와 그 숫자가 있는 인덱스를 저장해줍니다. 이렇게 하면, 현재 숫자를 처리할 때, 이전에 처리한 숫자들 중에서 현재 숫자와 더했을 때 target이 되는 숫자가 있었는지 빠르게 확인할 수 있어요.
2. 시간 복잡도: 이 알고리즘은 배열을 한 번 순회하면서 해시맵을 사용하는데, 해시맵의 조회 및 삽입은 평균적으로 O(1)이므로 전체 시간 복잡도는 **O(n)**입니다.
3. 공간 복잡도: 해시맵이 추가적인 메모리를 사용하므로, 공간 복잡도는 **O(n)**입니다. 이는 입력 배열의 크기만큼의 메모리가 필요하기 때문입니다.

장점

• 효율성: 해시맵을 사용함으로써, 배열을 한 번만 순회해도 문제를 해결할 수 있습니다. 이 방법은 단순 반복문으로 풀 때보다 효율적이며, 특히 배열의 길이가 길어질수록 차이가 큽니다.
• 직관성: 두 수의 합 문제는 해시맵을 활용한 접근법이 직관적이며, 코드도 상대적으로 간결합니다.

이 방법은 공간을 조금 더 사용하지만, 속도 측면에서 매우 효율적입니다. 문제의 요구 사항에 따라 최적의 알고리즘을 선택하는 것이 중요한데, 이 경우 해시맵을 사용한 방법이 가장 적절한 해결책이라고 할 수 있습니다.

 

 

해쉬맵이란 것에 대해서 공부를 해봐야 할 것 같다. 

일단 오늘은 이제 잘 시간! 내일 다시 알고리즘 공부 하자. 꽤 재미 있는 것 같다. 

-> C#에 해쉬맵은 없는 것 같다. 해쉬테이블이 해쉬맵인 것 같은데 해쉬테이블은 사용 하면 박싱 언박싱이 일어난다는데?? 일단 잔다.