[모각코 / 240105] 알고리즘 문제 풀이 (코드트리 - 시뮬레이션)

 

안녕하세요. 모각코 1일차입니다. 
 
 
 
오늘은 코드트리를 이용하여 알고리즘 문제를 풀어보았습니다.
시뮬레이션에 약해서 보완하기 위해 이 부분의 문제를 풀었습니다.
 
 
 
코드 트리 - 최고의 33위치
https://www.codetree.ai/missions/2/problems/best-place-of-33/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 
n * n 격자에 3 * 3 격자를 적절하게 잘 잡아서 최댓값을 구하는 문제입니다. 
 
입력 양식

5
0 0 0 1 1
1 0 1 1 1
0 1 0 1 0
0 1 0 1 0
0 0 0 1 1

 
출력 양식

6

 
 
풀이 방법입니다. 
시뮬레이션인만큼 수학적으로 접근해보았습니다. 
3*3 격자는 위 아래로 세 개씩입니다. 시작 위치를 알면 for문을 돌려서 반복하면됩니다. 시작 위치는 아래의 그림과 같이 구할 수 있습니다. 

 
정답

n = int(input())

li = [list(map(int, input().split())) for i in range(n)]  # n*n 격자 입력
max = 0


for i in range(((n-2) * (n-2))):  #  n*n 격자에 3*3 격자가 들어갈 수 있는 개수만큼 반복
    val = 0
    for j in range(i // (n-2), i // (n-2) + 3):
        for k in range(i % (n-2), i % (n-2) + 3):
            val += li[j][k]
    if val > max:
        max = val


print(max)

 
 
 
 

코드 트리 - 행복한 수열의 개수
https://www.codetree.ai/missions/2/problems/number-of-happy-sequence/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 
행과 열에 m 이상의 개수로 연속된 수가 있으면 행복한 수열입니다. 이 행복한 수열의 개수를 찾는 문제입니다. 
 
입력 양식

3 2
1 2 2
1 3 4
1 2 3

 
 
출력 양식

2

 
 
풀이 방법입니다. 
이 문제는 직관적이게 접근했습니다. 일단 행과 열을 for문을 통해 확인하면서 이전 값이 같으면 cnt만 증가, 다르면 cnt를 초기화하며 이전 값을 변경합니다.
 
정답

n, m = map(int, input().split())  # n 은 n*n, m은 행복한 수열이 되기 위한 조건

li = [list(map(int, input().split())) for i in range(n)]  # 리스트 입력받음
happy = 0


# 열
cnt = 1
for i in range(n):
    first = li[i][0]
    for j in range(1, n):
        if li[i][j] == first:  # 이전 값과 다음이 같다면 cnt 1만큼 증가
            cnt += 1
        else:  # 다르면 이전 값을 변경하고 cnt 초기화
            first = li[i][j]
            cnt = 1
        if cnt >= m:  # cnt 값이 m 보다 크거나 같으면 행복한 수열 개수 증가 및 cnt 초기화
            happy += 1
            cnt = 1
            break
    
# 행
cnt = 1
for i in range(n):
    first = li[0][i]
    for j in range(1, n):
        if li[j][i] == first:  # 이전 값과 다음이 같다면 cnt 1만큼 증가
            cnt += 1
        else:  # 다르면 이전 값을 변경하고 cnt 초기화
            first = li[j][i]
            cnt = 1
        if cnt >= m:  # cnt 값이 m 보다 크거나 같으면 행복한 수열 개수 증가 및 cnt 초기화
            happy += 1
            cnt = 1
            break

if n == 1:  # 예외 사항
    happy = 2

print(happy)