[항해99 취업 리부트 코스 학습일지] 점점 흐려지는 의식 속에서 헤매는 나

9 to 9의 효과는 대단했다...!

알고리즘 문제풀이 5일 차

오늘 일어나는 것도 힘들었고 그러다 보니 문제를 보는데 집중이 안 돼서 하다가 중간에 10분 정도 책상 앞에 엎드려서 잤다.(커피냅이 좋다길래... ^^)

근데 진짜 10분 자니까 세상 정신이 맑아지면서 풀 집중력을 유지할 수 있었고 풀 수 있는 문제들은 다 풀어본 것 같다.

오늘 문제 난이도가 생각보다 올라간 것인지는 몰라도 다른 사람들도 푸는 속도가 좀 느렸던 것 같았다.

언제 늘까 내 알고리즘 실력..

---

0. TIL (2024.06.03)

📚오늘 진행한 문제 리스트

1. 백준 1018 체스판 다시 칠하기 (실버 4) ✔️

https://www.acmicpc.net/problem/1018

풀이⬇️

5일차 - 5번
# 백준 1018 체스판 다시 칠하기 - 실버 4
# M*N 체스판 -> 8*8 체스판 만들기
# 무조건 번갈아서 칠해져야함.
# 8*8로 잘라낸 후에 잘못된 부분 다시 칠함 -> 다시 칠해야 하는 최소 개수 구하기
import sys


def count_wrong_point(x, y):
    current_color = grid[x][y]
    cnt = 0
    for i in range(x, x+8):
        for j in range(y, y+8):
            if grid[i][j] != current_color:
                cnt += 1
            current_color = 'W' if current_color == 'B' else 'B'
        current_color = 'W' if current_color == 'B' else 'B'
    return min(cnt, 64 - cnt) # 시작 색깔로 계속 가는 경우 vs 시작 색깔을 바꿔서 하는 경우


N, M = map(int, sys.stdin.readline().strip().split())
grid = [[x for x in sys.stdin.readline().strip()] for _ in range(N)]
answer = float('inf')
for i in range(N-7):
    for j in range(M-7):
        answer = min(answer, count_wrong_point(i, j))
print(answer)

생각보다 재밌었던 문제

Brute Force로 처음 색깔 기준으로 번갈아가면서 칠해졌는지 보고 안 맞으면 개수 세는 문제였는데

계속 틀리길래 뭐가 문제지 했다가 갑자기 번뜩하고 떠오른 게 첫 색깔이 잘못 됐을 수도 있지 않나? 해서 반영하니까 정답이었다.

엣지 케이스들을 잘 생각해봐야 하는데 아직 쉽지가 않다ㅠ

 

2. 백준 1051 숫자 정사각형 (실버 3) ✔️

https://www.acmicpc.net/problem/1051

풀이⬇️

5일차 - 6번
# 백준 1051 숫자 정사각형 - 실버 3
# N*M 직사각형에서 꼭짓점이 모두 일치하는 가장 큰 정사각형 찾기

# 31120/44
import sys


def find_square(l):
    cnt = 0
    for i in range(N - l + 1):
        for j in range(M - l + 1):
            point_num = grid[i][j]
            if grid[i][j+l-1] == point_num and grid[i+l-1][j] == point_num and grid[i+l-1][j+l-1] == point_num:
                cnt = l**2
    return cnt


N, M = map(int, sys.stdin.readline().strip().split())
grid = [[x for x in sys.stdin.readline().strip()] for _ in range(N)]
answer = float('-inf')
limit = min(N, M)
for l in range(limit, 0, -1):
    answer = max(answer, find_square(l))
print(answer)

앞 문제와 매우 유사한 문제

이번에도 BF 사용했고, 꼭짓점이 모두 같은 숫자인 정사각형의 넓이의 최댓값을 구하는 문제였다.

 

3. 백준 2477 참외밭 (실버 2) ✔️

https://www.acmicpc.net/problem/2477

풀이⬇️

5일차 - 7번
# 백준 2477 참외밭 - 실버 2

# 참외밭의 참외 개수 비례식으로 구하는 문제
# 참외밭의 넓이 구하기 -> 비례식으로 개수 구하기
# 작은 영역의 가로, 세로 = 제일 큰 가로, 세로의 양 옆에 있는 값들의 차의 절댓값

# 31120/44
import sys


def find_max_val():
    w, h, w_i, h_i = 0, 0, 0, 0
    for i in range(6):
        if field[i][0] == 1 or field[i][0] == 2:
            if w < field[i][1]:
                w = field[i][1]
                w_i = i
        else:
            if h < field[i][1]:
                h = field[i][1]
                h_i = i
    return w, h, w_i, h_i


def find_min_val():
    w = abs(field[(h_idx - 1) % 6][1] - field[(h_idx + 1) % 6][1])
    h = abs(field[(w_idx - 1) % 6][1] - field[(w_idx + 1) % 6][1])
    return w, h


km_cnt = int(sys.stdin.readline().strip())
field = [[a for a in map(int, sys.stdin.readline().strip().split())] for _ in range(6)]
max_r, max_c, w_idx, h_idx = find_max_val()
min_r, min_c = find_min_val()
print(km_cnt * (max_r * max_c - min_r * min_c))

기술 매니저님이 이런 문제가 코딩테스트에 나오기 좋은 유형의 문제라고 하셨다.

각자 풀이 방법이 다 다르고 그 부분에 대해서 할 말도 많아서 다양한 풀이를 경험해 보는 게 좋을 것 같다고 생각했다.

내가 푼 방법은 참외밭은 사각형 구조가 아니라 사각형에서 한 꼭짓점 부근의 사각형이 잘린 형태이므로 전체 직사각형에서 잘린 영역의 직사각형 넓이를 빼주면 된다고 생각하고 들어갔다.

우선 주어진 길이들 중 최댓값을 가지는 가로, 세로를 구해주면서 해당 요소가 나온 index까지 찾아준다.

이유는 최대 길이의 가로와 세로의 양 옆에 무조건 두 변이 존재하고 그 두 변의 차가 결국 잘린 영역의 변이 되기 때문이다.

최소 영역의 변을 구하는 방법은 이전에 구한 최댓값의 index를 사용해서 양 옆을 비교하는데 그 인덱스가 언제 입력된 값인지는 모르니까 나머지 정리를 이용해서 범위에서 벗어나지 않게만 해줬고 문제를 해결했다.

 

4. 백준 16926 배열 돌리기 1 (골드 5) ✔️

https://www.acmicpc.net/problem/16926

풀이⬇️

5일차 - 8번
# 백준 16926 배열 돌리기 1 - 골드 5

# 배열 회전하기
# 배열을 순회하면서 각 원소를 실제 회전 방향으로 이동시킨 인덱스에다가 값 업데이트 하기
# 했는데 시간초과 -> 그렇게 크다고 생각 안했는데..
# 그럼 depth에 따라 idx로 구분해서 저장해놓고 회전한 위치 따로 구해서 값 업데이트 하는 방식으로 진행
import sys


# 외각 배열 depth 순으로 분류 (상 -> 우 -> 하 -> 좌 순으로 진행)
def classify_array_by_depth():
    depth = 0
    nums = [[] for _ in range(depth_count)]
    while depth < depth_count:
        for c in range(depth, M - depth):
            nums[depth].append(arr[depth][c])
        for r in range(depth + 1, N - depth):
            nums[depth].append(arr[r][M - 1 - depth])
        for c in range(M - 2 - depth, depth - 1, -1):
            nums[depth].append(arr[N - 1 - depth][c])
        for r in range(N - 2 - depth, depth, -1):
            nums[depth].append(arr[r][depth])
        depth += 1
    return nums


# 회전된 위치에 값 업데이트 (classify_array_by_depth 함수와 동일하게 상 -> 우 -> 하 -> 좌 순으로 진행)
def rotate_array():
    depth = 0
    while depth < depth_count:
        num = 0
        length = len(classified_arr[depth])
        for c in range(depth, M - depth):
            idx = (num + R) % length
            arr[depth][c] = classified_arr[depth][idx]
            num += 1
        for r in range(depth + 1, N - depth):
            idx = (num + R) % length
            arr[r][M - 1 - depth] = classified_arr[depth][idx]
            num += 1
        for c in range(M - 2 - depth, depth - 1, -1):
            idx = (num + R) % length
            arr[N - 1 - depth][c] = classified_arr[depth][idx]
            num += 1
        for r in range(N - 2 - depth, depth, -1):
            idx = (num + R) % length
            arr[r][depth] = classified_arr[depth][idx]
            num += 1
        depth += 1


N, M, R = map(int, sys.stdin.readline().strip().split())
arr = [sys.stdin.readline().strip().split() for _ in range(N)]
depth_count = min(N, M) // 2
classified_arr = classify_array_by_depth()
rotate_array()
print('\n'.join(' '.join(x) for x in arr))

처음 문제를 풀 때, 단순하게 다음 숫자를 따로 저장한 뒤에 현재 숫자를 이동시켜 주는 방식으로 해서 문제를 풀었는데, 시간 초과가 났다.

아마 한 바퀴 돌고 다음 바퀴 들어갈 때, 중복되는 상황이 벌어질 수도 있고 풀이도 보면 5중 for 문을 쓰게 됐는데 거기서 문제였지 싶다.

그래서 최대한 중첩 반복문을 사용하지 않기 위해 외각부터 depth를 index로 해서 하나의 리스트로 저장하고 이를 통해 값들을 회전한 위치에 갱신하는 방식으로 구현했다.

 

5. 백준 10868 최솟값 (골드 1) ❌

https://www.acmicpc.net/problem/10868

풀이⬇️

처음에 heap 써서 순회하면서 슬라이싱 된 배열의 최솟값을 구했는데, 딱 봐도 시간초과 걸릴 거 같았는데 걸렸다.

근데 남은 방법이 이분탐색 밖에 없는 것 같은데 막상 정렬할 수가 없어서 사용도 못 했다.

기술 매니저님이 세그먼트 트리를 쓰면 해결 가능하다고 하셨는데

말만 들어봤지 제대로 공부해 본 적이 없어서 공부하고 풀어보려고 한다.

 

6. 백준 17435 합성함수와 쿼리 (골드 1) ❌

https://www.acmicpc.net/problem/17435

풀이⬇️

푸는 중

 

7. 백준 27368 Sum Zero (플래티넘 2) ❌

https://www.acmicpc.net/problem/27368

풀이⬇️

푸는 중

 

8. 백준 10060 감시 카메라 (다이아몬드 5) ❌

https://www.acmicpc.net/problem/10060

풀이⬇️

푸는 중

---

📝오늘자 질문

1. 오늘 진행된 강의에서 학습한 내용은 무엇인가요

• 파이썬 기초 문법(입출력, 반복문, 조건문, 자료형, 시간 복잡도 등)

 

2. 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?

• 세그먼트 트리, 희소 배열

---

* 항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.

https://hanghae99.spartacodingclub.kr/reboot

IT 커리어 성장 코스 항해99, 개발자 취업부터 현직자 코스까지