공부 기록

날짜: 2025년 12월 10일
학습 범위: p.120 ~ p.154

---

💡 책에서 새롭게 알게 된 내용 메모

책을 읽으며 중요하다고 느낀 개념, 공식, 팁을 적습니다.

1. p, np, np-hard, np-complete

• p: 다항시간 알고리즘이 존재하는 문제
• np: 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제
• np-hard: 모든 np 문제보다 어렵거나 같다
• np-complete: np-hard이지만 검산이 가능

2. 반복문 불변식

• 반복문의 내용이 한번 실행될 때마다 중간결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건

3. 완전 탐색 알고리즘: 모든 경우의 수를 다 구하는 것

---

문제 1. 보글게임 150P

1) 문제 분석

• 요구사항: 5x5 상하좌우 대각선으로 인접한 칸들의 글자를 이어서 단어를 찾아내기

• 내 생각(접근법):

  1. 중복처리를 어떻게?
  • ex) 한방향으로 cry, crying이 모두 가능할때 어디까지 crying을 못찾을 수 있음
  2. 단어가 맞는지 확인 어떻게?

  • 한 방향으로 단어 cqqw등이 나왔을 때 이게 말이 된는 단어인지 확인하는법? -> 찾아야하는 단어가 주어짐

    3. 옆의 글자 확인하는 방법

    - 역으로 된 단어가 있을수 있음 -> 모든 방면 확인
    - ex) yrc는 단어가 아니지만 cry는 단어
    4. 호출하는 방법: 한 글자를 기준으로 8가지 경우의 수가 존재 -> 뻗어나가기

    즉 "보드판의 (y, x) 좌표에서 시작해서, 주어진 단어 word를 만들 수 있는가?" (True/False 반환)

로직 흐름 (종료 조건이 중요)

1. 범위 이탈: (y, x)가 5x5 보드판 밖으로 나갔나? -> False

2. 글자 불일치: 현재 좌표 board[y][x]의 글자가 word의 첫 글자와 다른가? -> False

3. 성공(완료): 글자가 일치하고, word의 길이가 1인가? (마지막 글자까지 다 찾음) -> True

2) 핵심 코드 & 풀이

	public class Boggle{
    	// 방향백터
    	static final int[] dx = {-1, -1, -1,  1, 1, 1,  0, 0};
    	static final int[] dy = {-1,  0,  1, -1, 0, 1, -1, 1};
        char[][] board;
        
        boolean hasWord(int y, int x, String word){          
        	// 범위 밖으로 나갔을때
            if (y < 0 || y >= 5 || x < 0 || x >= 5) return false;
            
            // 현재 칸의 글자가 찾는 첫 단어와 다름
            if (board[y][x] != word.charAt(0)) return false;
            
            // 단어의 끝에 도달했을 때 
            if(word.length() ==1) return true;
            
            for(int direction = 0; direction <8; direction++){
            	int nextY = y + dy[direction];
                int nextX = x + dx[direction];
                
                if (hasWord(nextY, nextX, word.substring(1))) {
                return true;
            }
        }
        
        // 8방향 다 뒤져봤는데 없으면 실패
        return false;
        }
   }