문제 링크
알고리즘 설명
[알고리즘 공부] #1 완전 탐색, 브루트포스(Brute Force) 알고리즘 with Python
[알고리즘 공부] #1 완전 탐색, 브루트포스(Brute Force) 알고리즘 with Python
완전 탐색 알고리즘(Brute Force)어떤 알고리즘일까?완전 탐색 알고리즘은 조건문이나 반복문을 통해 가능한 모든 경우의 수를 탐색하여 원하는 값을 구하는 알고리즘을 말한다. 알고리즘 설계의
juyear-coding.tistory.com
문제 설명
이 문제는 완전 탐색 알고리즘을 활용하여 풀 수 있다.
먼저 N x N 크기의 사탕이 주어지고, 사탕의 색이 다른 인접한 두 사탕의 위치를 바꾼다.
그 후 같은 색으로 이루어져 있는 가장 긴 연속 부분을 고른 다음 사탕을 먹는다고 했을 때 사탕을 몇 개 먹을 수 있는지 구하는 문제다.
이 문제는 모든 사탕을 확인하면서 인접한 다른 색깔의 사탕과 교환했을 때 먹을 수 있는 사탕의 갯수를 구해야 한다. 모든 사탕을 확인해야 한다는 점에서 완전탐색 알고리즘이 사용되는 것을 알 수 있다.
자세한 설명은 코드와 같이 보도록 하자.
CODE 설명
Count Function
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
def count(num):
result = 0
a = 1
for i in range(num):
for j in range(num-1):
if candy[i][j] == candy[i][j+1]:
a += 1
else:
if a > result:
result = a
a = 1
if a > result:
result = a
a = 1
a = 1
for i in range(num):
for j in range(num-1):
if candy[j][i] == candy[j+1][i]:
a += 1
else:
if a > result:
result = a
a = 1
if a > result:
result = a
a = 1
return result
tempList = []
for i in range(num):
color = input()
for j in range(num):
tempList.append(color[j])
candy.append(tempList)
tempList = []
|
cs |
위에는 count 함수이다.
count함수의 기능은 num(N x N 크기의 사탕에서 N을 의미)을 매개변수로 입력받아 현재 사탕의 배열에서 가장 많이 먹을 수 있는 사탕의 갯수를 return 해주는 기능이다. 즉 현재 사탕 배열에서 가장 긴 연속으로 같은 색깔인 사탕의 길이를 알려준다.
입력 받기 및 배열 생성
|
1
2
3
4
5
6
7
8
9
10
|
num = int(input())
candy = []
numMax = 0
tempList = []
for i in range(num):
color = input()
for j in range(num):
tempList.append(color[j])
candy.append(tempList)
tempList = []
|
cs |
문제 조건에 맞춰 입력을 받는 코드다.
입력을 받음과 동시에 candy리스트에 색깔을 넣어주고 있다.
tempList를 만들어 색깔을 하나 하나 뜯어서 candy에 넣어주었다.
입력을 받은 후 candy리스트에는 [['C','C','P'],['C','C','P'],['P','P','C']] 이런식으로 이중리스트로 입력될 것이다.
사탕 가로 바꾸기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
for i in range(num):
for j in range(num-1):
if candy[i][j] != candy[i][j+1]:
temp1 = candy[i][j]
temp2 = candy[i][j+1]
candy[i][j] = temp2
candy[i][j+1] = temp1
tempMax = count(num)
if tempMax > numMax:
numMax = tempMax
candy[i][j] = temp1
candy[i][j+1] = temp2
|
cs |
모든 사탕을 확인하면서 색깔이 다른 사탕이 가로줄에 있는지(오른쪽에 있는지) 확인하는 코드이다.
만약에 색깔이 다른 사탕이 오른쪽에 있다면 위치를 바꾼 후 count함수를 호출하여 현재 사탕 배열에서 먹을 수 있는 사탕의 갯수를 구한다.
그 후 return받은 값이 현재 최댓값보다 크다면 return 값을 최댓값으로 바꿔준다.
사탕 세로 바꾸기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
for i in range(num):
for j in range(num-1):
if candy[j][i] != candy[j+1][i]:
temp1 = candy[j][i]
temp2 = candy[j+1][i]
candy[j][i] = temp2
candy[j+1][i] = temp1
tempMax = count(num)
if tempMax > numMax:
numMax = tempMax
candy[j][i] = temp1
candy[j+1][i] = temp2
print(numMax)
|
cs |
가로 바꾸기와 코드는 거의 비슷하지만 세로를 확인하는 코드이다.
작동방식은 가로와 똑같다.
전체 CODE
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
num = int(input())
candy = []
numMax = 0
def count(num):
result = 0
a = 1
for i in range(num):
for j in range(num-1):
if candy[i][j] == candy[i][j+1]:
a += 1
else:
if a > result:
result = a
a = 1
if a > result:
result = a
a = 1
a = 1
for i in range(num):
for j in range(num-1):
if candy[j][i] == candy[j+1][i]:
a += 1
else:
if a > result:
result = a
a = 1
if a > result:
result = a
a = 1
return result
tempList = []
for i in range(num):
color = input()
for j in range(num):
tempList.append(color[j])
candy.append(tempList)
tempList = []
for i in range(num):
for j in range(num-1):
if candy[i][j] != candy[i][j+1]:
temp1 = candy[i][j]
temp2 = candy[i][j+1]
candy[i][j] = temp2
candy[i][j+1] = temp1
tempMax = count(num)
if tempMax > numMax:
numMax = tempMax
candy[i][j] = temp1
candy[i][j+1] = temp2
for i in range(num):
for j in range(num-1):
if candy[j][i] != candy[j+1][i]:
temp1 = candy[j][i]
temp2 = candy[j+1][i]
candy[j][i] = temp2
candy[j+1][i] = temp1
tempMax = count(num)
if tempMax > numMax:
numMax = tempMax
candy[j][i] = temp1
candy[j+1][i] = temp2
print(numMax)
|
cs |
전체 코드
추천 글
[알고리즘 공부] #2 백트래킹(BackTracking) 알고리즘 with Python
[알고리즘 공부] #2 백트래킹(BackTracking) 알고리즘 with Python
백트래킹 알고리즘(BackTracking)어떤 알고리즘일까?백트래킹 알고리즘은 비선형으로 구성된 자료 구조를 깊이 우선으로 탐색할 때, 더 이상 탐색할 수 없는 상황에서 이전 단계로 돌아가는 알고
juyear-coding.tistory.com
백트래킹 알고리즘 배우기.
[완전탐색 알고리즘] #1 백준 일곱 난쟁이 (파이썬,2309번)
[완전탐색 알고리즘] #1 백준 일곱 난쟁이 (파이썬,2309번)
문제 링크2309번: 일곱 난쟁이 (acmicpc.net)알고리즘 설명[알고리즘 공부] #1 완전 탐색, 브루트포스(Brute Force) 알고리즘 with Python (tistory.com) [알고리즘 공부] #1 완전 탐색, 브루트포스(Brute Force) 알고
juyear-coding.tistory.com
완전탐색 알고리즘을 사용하는 다른 문제.
방문해주셔서 감사합니다!
'[알고리즘] > [알고리즘 문제 풀기]' 카테고리의 다른 글
| [백트래킹 알고리즘] #2 백준 N과 M (2) (파이썬,15650번) (2) | 2024.07.07 |
|---|---|
| [백트래킹 알고리즘] #1 백준 N과 M (1) (파이썬,15649번) (1) | 2024.07.06 |
| [완전탐색 알고리즘] #3 백준 날짜 계산 (파이썬,1476번) (2) | 2024.07.01 |
| [완전탐색 알고리즘] #1 백준 일곱 난쟁이 (파이썬,2309번) (0) | 2024.06.26 |
