[코딩테스트] 배열, 문자열과 완전 탐색(Brute Force)

이번 글의 핵심 주제는 세 가지입니다.

첫째, 배열
둘째, 문자열
셋째, 완전 탐색

저번 글에서 입출력과 기본 구현 패턴을 익혔다면,

이번 글에서는 데이터를 담고 꺼내고 돌려보는 연습을 해보겠습니다.

 

---

 

Ⅰ. 목표

배열과 문자열을 자유롭게 다루면서
가능한 모든 경우를 직접 탐색하는 완전 탐색 패턴에 익숙해진다.

 

구체적으로는 다음 네 가지를 목표로 합니다.

• 1차원 / 2차원 배열 선언, 초기화, 순회 패턴 익히기
• 문자열에서 문자를 꺼내고, 부분 문자열을 다루는 패턴 연습
• 이중, 삼중 반복문을 사용한 완전 탐색 감각 익히기
• 완전 탐색의 시간 복잡도에 대한 감을 잡기

 

---

 

Ⅱ. 배열 기본 패턴 정리

- 1차원 배열 선언과 초기화

코딩테스트에서 가장 기본이 되는 자료구조가 1차원 배열입니다.

int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];

StringTokenizer st = new StringTokenizer(br.readLine());
for (int i=0; i<n; i++) {
	arr[i] = Integer.parseInt(st.nextToken());
}

이 패턴은 자주 쓰이므로, 손에 완전히 익혀두는 것이 좋습니다.

 

---

 

- 2차원 배열(행렬) 패턴

표 형태의 데이터를 다룰 때는 2차원 배열을 사용합니다.

int n = 3;
int m = 4;
int[][] map = new int[n][m];

for (int i=0; i<n; i++) {
	StringTokenizer st = new StringTokenizer(br.readLine());
    for (int j=0; j<m; j++) {
    	map[i][j] = Integer.parseInt(st.nextToken());
    }
}

2차원 배열에서 자주 사용하는 패턴은 다음과 같습니다.

• 전체 순회: 이중 for문
• 특정 조건을 만족하는 칸만 처리: if (map[i][j] == 1) 등의 조건 추가
• 상하좌우 이동은 나중에 DFS/BFS에서 다루지만, 2차원 배열에 익숙해지는 것이 먼저

 

---

 

Ⅲ. 문자열(String) 다루기 기본

문자열 문제도 코테에서 자주 등장합니다.

Java에서는 String과 char를 잘 왔다 갔다 하면서 사용하는 연습이 중요합니다.

 

---

 

- 문자열 길이와 문자 접근

String s = br.readLine();
int len = s.length();

for (int i=0; i<len; i++) {
	char c = s.charAt(i);
    // c를 이용해 처리
}

• string.length()로 문자열 길이를 구할 수 있음
• string.charAt(i)로 문자열의 i번째 문자를 구할 수 있음

 

---

 

- 문자 비교와 카운팅 예시

특정 문자열 안에 특정 문자가 몇 번 나오는지 세는 문제는 아래와 같이 풀이할 수 있습니다.

String s = br.readLine();
char target = 'a';
int count = 0;

for (int i=0; i<s.length(); i++) {
	if (s.charAt(i) == target) {
    	count++;
    }
}

System.out.println(count);

 

---

 

- 부분 문자열(substring) 사용

부분 문자열을 뽑을 때는 substring을 사용합니다.

String s = "abcdef";
String sub1 = s.substring(0, 3);	// "abc"
String sub2 = s.substring(2);		// "cdef"

• string.substring(i): i번째 글자부터 끝까지의 부분 문자열
• string.substring(i, j): i번째 글자부터 j-1번째 글자까지의 부분 문자열

문자열을 인덱스로 자유롭게 쪼갤 수 있는 상태까지 도달하는 것을 목표로 하면 좋습니다.

 

---

 

Ⅳ. 완전 탐색이란?

- 정의

가능한 모든 경우를 전부 시도해보면서 조건을 만족하는 답을 찾는 방법

 

완전 탐색은 알고리즘 관점에서 봤을 때 아주 우아한 방법은 아니지만,

문제의 크기가 작을 때는 가장 직관적이고 구현하기 쉬운 방법입니다.

 

---

 

- 언제 사용할까?

• 데이터 크기 N이 작을 때
  • 예: N이 100 이하 또는 경우의 수가 100만 번 이하
• 탐색해야 할 경우의 수를 직접 세어봤을 때 돌려볼 만한 수준일 때
• 다른 복잡한 알고리즘이 떠오르지 않을 때

 

---

 

Ⅴ. 완전 탐색 기본 패턴: 이중 반복문

가장 기본적인 완전 탐색 코드는 이중 for문 입니다.

 

- 예시1: 배열에서 두 수 의 합이 특정 값이 되는 쌍 찾기

• 길이 N인 배열
• 두 수를 골라 더했을 때
• 합이 k가 되는 쌍의 개수

를 구하는 문제를 생각해봅시다.

 

완전 탐색 접근은 다음과 같습니다.

• i를 0부터 N-1까지 돌린다.
• j를 i+1부터 N-1까지 돌린다.
• arr[i] + arr[j] == k이면 카운트 증가

이것을 코드로 옮기면 아래와 같습니다.

int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];

StringTokenizer st = new StringTokenizer(br.readLine());
for (int i=0; i<n; i++) {
	arr[i] = Integer.parseInt(st.nextToken());
}

int k = Integer.parseInt(br.readLine());
int count = 0;

for (int i=0; i<n; i++) {
	for (int j=i+1; j<n; j++) {
    	if (arr[i] + arr[j] == k) {
        	count++;
        }
    }
}

System.out.println(count);

• 시간 복잡도: O(N*N)
• N이 2,000 정도까지는 무난하게 통과하는 수준입니다.

 

---

 

Ⅵ. 완전 탐색 응용: 모든 조합 / 부분 수열 탐색

- 세 수를 골라 조건을 검사하는 경우

조합을 완전 탐색하는 가장 직관적인 코드는 삼중 for문입니다.

for (int i=0; i<n; i++) {
	for (int j=i+1; j<n; j++) {
    	for (int k=j+1; k<n; k++) {
        	// arr[i], arr[j], arr[k] 세 수를 사용하는 로직
        }
    }
}

예를 들어, 세 수의 합이 최대가 되는 값을 구한다든지,

세 수의 합이 특정 범위에 있는 조합의 개수를 세는 등의 문제를 완전 탐색으로 접근할 수 있습니다.

 

---

 

- 부분 수열을 전부 확인하는 경우

아직 비트마스크나 재귀를 본격적으로 쓰지 않는 시점이라면,

길이가 짧은 경우에 한해 for문을 늘리는 방식으로 충분히 대응할 수 있습니다.

예를 들어, 길이 4짜리 배열에서 모든 비어있지 않은 부분 수열을

완전 탐색하려면 다음과 같은 패턴이 가능합니다.

for (int i=0; i<n; i++) {
	// 길이 1에 해당
    // arr[i]
    
    for (int i=0; i<n; i++) {
    	// 길이 2에 해당
        // arr[i], arr[j]
        
        for (int k=j+1; k<n; k++) {
        	// 길이 3에 해당
            // arr[i], arr[j], arr[k]
        }
    }
}

실제 코테에서는 이런 식의 고정 길이 조합 완전 탐색 패턴이 여러 문제에서 등장합니다.

 

---

 

Ⅶ. 문자열에서의 완전 탐색 예시

문자열에서도 완전 탐색은 자주 사용됩니다.

 

- 예시: 부분 문자열이 몇 번 등장하는지 세기

문자열 s가 있고, 문자열 pattern이 몇 번 등장하는지 세는 문제를 생각해 보겠습니다.

완전 탐색 접근법은 아래와 같습니다.

• s의 0번 인덱스부터 끝까지 pattern이 시작할 수 있는 모든 위치를 시도
• 각 위치에서 pattern과 길이만큼 비교
• 모두 일치하면 카운트 증가

코드로 옮기면 다음과 같습니다.

String s = br.readLine();			// "ababcababc"
String pattern = br.readLine();		// "ab"

int n = s.length();
int m = pattern.length();
int count = 0;

for (int i=0; i<=n-m; i++) {
	boolean match = true;
    for (int j =0; j<m; j++) {
    	if (s.charAt(i+j) != pattern.charAt(j)) {
        	match = false;
            break;
        }
    }
    if (match) {
    	count++;
        // 겹치는 것도 허용하지 않으려면 i += (m-1);
    }
}

System.out.println(count);

이 역시 가능한 시작 위치를 전부 시도한다는 점에서 전형적인 완전 탐색 패턴입니다.

 

---

 

Ⅷ. 시간 복잡도 감각 잡기

완전 탐색을 사용할 때는 항상 N이 얼마나 되는지를 확인해야 합니다.

대략적인 기준은 다음과 같이 잡을 수 있습니다.

• N이 100 이하면 O(N*N), O(N*N*N)도 꽤 여유 있음
• N이 1000 이하면 O(N*N)까지는 대체로 가능, O(N*N*N)는 위험
• N이 100000 이하면 O(N logN) 또는 O(N) 정도를 목표로 해야 함

N이 작으면 완전 탐색을 먼저 떠올려 볼 수 있다는 감각을 가지면 됩니다.

 

---

 

Ⅸ. 체크리스트

• 1차원 / 2차원 배열을 선언하고, 입력을 받아 채우는 코드를 혼자서 작성할 수 있다.
• 문자열에서 문자 하나씩 꺼내어 비교하고, 카운트하는 코드를 작성할 수 있다.
• 이중 for문, 삼중 for문을 사용해서 두 개/세 개를 뽑는 완전 탐색 패턴을 구현할 수 있다.
• 두 수의 합이 k가 되는 쌍을 완전 탐색으로 찾는 코드를 직접 짤 수 있다.
• 부분 문자열 패턴 매칭을 완전 탐색으로 구현할 수 있다.
• N의 크기를 보고 완전 탐색이 가능한지, 대략적인 시간 복잡도를 판단할 수 있다.

 

---

 

다음 글부터는 본격적으로 자료구조를 사용한 문제 풀이를 해볼 것입니다.

• 스택 (Stack)
• 큐 (Queue)
• 덱 (Deque)
• 우선순위 큐 (Priority Queue, 힙 구조)

를 활용해 괄호 검사, 프린터 큐, 카드 게임 등 전형적인 문제들을 풀어볼 예정입니다.