[99클럽 5기] Day11 TIL - 브루트포스 알고리즘, 스택

99클럽 5기 | Java | Middler

 

🗝️ 오늘의 학습 키워드 : Stack Brute Force

⌛ 회고

오늘 오전에는 설에 다 풀지 못하였던 윷놀이(Small) 문제를 드디어 해결하였습니다.  
아이디어도 딱히 떠오르지 않고 시간이 오래 걸렸던터라 성취감을 느낄 수 있었던 문제였습니다.😍
오늘 99클럽 문제는 Brute Force 문제였는데 처음 풀 때, 알고리즘 복잡도를 정확히 계산하지 않고 일단 해보자!라는 마음으로 제출하여 성공했는데 풀이를 작성하며 알고리즘 복잡도를 계산해보고 주어진 값의 범위가 크지 않아 Brute Force 문제로 풀 수 있는 문제였다는 것을 깨달았습니다.  
이번 풀이를 작성하며 다음 문제를 풀 때에는 알고리즘 복잡도를 계산해 보고
범위가 작게 주어질 때는 Brute Force 문제가 아닌가? 생각해 보아야겠다고 생각하였습니다.

생각보다 쉽게 문제가 풀려서 비기너 문제도 풀어보았습니다.
스택 문제였는데 문자열로 받은 명령어를 그대로 처리하기만 하면 되는 문제여서 그렇게 어렵지 않게 풀 수 있는 문제였던 것 같습니다.

오늘은 TIL 작성하고 챌린지 문제도 한 번 도전해 보아야겠습니다.

 

❓ 오늘 만난 문제

🐍설날 문제 이벤트

• 🥉 비기너 : 윷놀이
• 🥈 미들러 : 윷놀이(Small)
• 🥇 챌린저 : 주사위 윷놀이

🐣 오늘의 문제

• 🥉 비기너 : 스택
• 🥈 미들러 : 체스판 다시 칠하기
• 🥇 챌린저 : N-Queen

 

💦 나의 시도 & 해결 방법👍

🐍설날 문제 이벤트

• 🥉 비기너 : [백준 | Java] 2490번 윷놀이
• 🥈 미들러 : [백준 | Java] 12425번 윷놀이(Small)
• 🥇 챌린저 : [백준 | Java] 17825번 주사위 윷놀이

🐣 오늘의 문제

• 🥉 비기너 : [백준 | Java] 10828번 스택
• 🥈 미들러 : [백준 | Java] 1018번 체스판 다시 칠하기
• 🥇 챌린저 :

 

❗ 무엇을 새롭게 알았는지

브루트 포스 알고리즘(BF; Brute Force)

굳이 생각하지 않고, 컴퓨터의 빠른 연산력을 이용해 모든 경우를 다 살펴보는 것
완전 탐색(Exhaustive search)

 

컴퓨터는 보통 약 1억번의 단순 연산 (사칙연산 같은...) 을 하는데 1초 정도 걸립니다.

 

위의 미들러 문제에서는 제한 시간이 2초로 주어졌습니다.
9 ≤ N, M ≤ 50이므로

다음과 같은 4중 for문을 사용하였더라도

for (int i = 0; i <= N - 8; i++) {
    for (int j = 0; j <= M - 8; j++) {
        int cnt = 0;
        for (int i2 = i; i2 < i + 8; i2++) {
            for (int j2 = j; j2 < j + 8; j2++) {
                cnt += board[i2][j2];
            }
        }

        if (cnt > 32) {
            cnt = 64 - cnt;
        }
        minCnt = Math.min(cnt, minCnt);
    }
}

 

알고리즘 복잡도는 42 × 42 × 8 × 8 = 112,896로 1억번에 한참 못미치는 것을 확인할 수 있습니다.
실제 실행 결과도 108ms로 성공적으로 제출을 할 수 있었습니다.

스택(Stack)

"쌓다"라는 의미
데이터를 차곡차곡 쌓아 올린 형태의 자료구조입니다.

• 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조(후입 선출, LIFO; Last Int First Out)를 가지고 있습니다.
• 정해진 방향으로만 쌓을 수 있음
• top으로 정한 곳을 통해서만 접근 가능

연산의 종류

• 삽입 연산 : push (스택의 맨 위에 새로운 항목을 추가)
• 삭제 연산 : pop
  (스택의 맨 위에 있는 항목을 제거하고 그 항목을 반환
  스택이 비어있을 경우, 에러를 반환)
• 맨 위 항목 조회 : peek top
  (스택의 맨 위에 있는 항목을 반환, 제거하지는 않음
  스택이 비어있을 경우, 에러를 반환)
• 스택이 비어있는지 확인 : isEmpty

스택의 활용

• 함수 호출 시, 호출된 함수의 매개변수, 리턴 주소, 로컬 변수 등을 저장
  • 스택의 사용은 중첩된 함수 호출을 가능하게 하며, 프로그램 실행 흐름을 관리
• 실행 취소(Undo)
• 문법 검사 : 프로그래밍 언어에서 괄호나 태그 등의 짝을 확인할 때 사용
• 깊이 우선 탐색(DFS) : 트리나 그래프의 DFS에 스택 사용 가능
  1. 노드를 스택에 푸시
  2. 인접 노드를 방문하며 탐색
  3. 더 이상 방문할 노드가 없으면 스택에서 pop하여 이전 노드로 돌아감.
• 표현식 평가 : 수학적 표현식(중위, 후위 표기법 등)의 평가에 사용
  • 연산자와 피연산자를 적절히 스택에 푸시하고 팝하며 표현식을 평가
• 메모리 관리 : 컴퓨터의 메모리 관리에 중요한 역할을 함.
  • 컴파일러는 메모리에 스택을 만들어 로컬 변수를 저장
  • 이 스택은 실행 도중 동적으로 커지거나 줄어들 수 있음

단점

• 일반적으로 크기가 고정되어 있음.
  • 스택이 사용하는 메모리를 미리 할당해야 하기 때문
  • 스택이 꽉 차면 더 이상 요소 추가 불가 => 스택오버플로우
    ☠️ 이는 프로그램에서 심각한 오류를 발생시킬 수 있음 ☠️
• LIFO 원칙에 따라 가장 최근에 추가된 요소만 직접 접근 가능
  • 스택 내부의 중간 위치에 있는 요소에 접근하려면 그 앞에 있는 요소들을 모두 제거해야 함.
  • 따라서 다음과 같은 작업 시, 비효율적
    • 스택 내부 중간 위치 요소 접근
    • 특정 요소가 스택 내에 존재하는지 검사
• 스택이 재귀 함수나 반복문에 종종 사용되기 때문에
  이를 적절히 사용하기 위해 재귀적 사고나 프로그램 흐름을 잘 이해해야 함.
  • 스택을 잘못 사용하면 프로그램의 로직을 이해하기 어렵게 만들 수 있음.

 

📆 내일 학습할 것은 무엇인지

⏹️ 코딩테스트 문제 풀이
⏹️ TIL 작성

🏷️ 참고 블로그

• 1-4. [자료구조이론] 스택(Stack)