알고리즘 요구사항 분석

시간제한에 따른 알고리즘 설계

N의 max	빅오
500 (5백)	O(N³)
2,000 (2천)	O(N²)
100,000 (10만)	O(NlogN)
10,000,000 (천만)	O(N)

---

오늘 공부한 개념

투 포인터

리스트에 순차적으로 접근해야할 때, 두개의 점 위치를 기록하면서 처리하는 알고리즘

배열의 회전

deque의 rotate()

만약 오른쪽(시계방향) 회전을 해야한다면 deque 자료형에서 제공하는 메서드인 rotate() 함수에 양수를 전달한다
만약 왼쪽(반시계방향) 회전을 해야한다면 음수를 전달한다

누적합

실버 1. 백준 21318 피아노 체조

풀이

실수를 몇번했는지 누적합으로 계산해서 구간 내의 실수를 출력해주면 된다.
누적합 접근방식이 익숙하지 않아 아이디어가 안 떠올라 바로 해설을 참고했다

코드

from sys import stdin

input = stdin.readline

N = int(input())

data = list(map(int, input().split(" ")))

mistake = [0 for _ in range(N)]  # i번째 값 = i번째 곡까지 몇번 실수했는가

for i in range(N):
    if i == 0:
        continue
    if data[i] < data[i - 1]:
        mistake[i] = mistake[i - 1] + 1
    else:
        mistake[i] = mistake[i - 1]

Q = int(input())

for _ in range(Q):
    s, e = map(int, input().split(" "))
    print(mistake[e - 1] - mistake[s - 1])

실버 2. 백준 2559 수열

풀이

최대, 최소 구할 때 int(1e9) 사용하자. result의 초기값을 0으로 설정해서 계속 에러났다.

온도의 누적합 배열을 만들어준 뒤, 구간 K에 대하여 가장 큰 acc[i+K] - acc[i]을 출력해주면 된다.

코드

from sys import stdin

input = stdin.readline

N, K = map(int, input().split(" "))
data = list(map(int, input().split(" ")))

acc = [0 for _ in range(N + 1)]

for i in range(1, N + 1):
    if i == 1:
        acc[i] = data[i - 1]
        continue
    acc[i] = acc[i - 1] + data[i - 1]

result = -int(1e9)
for i in range(0, N - K + 1):
    result = max(result, acc[i + K] - acc[i])

print(result)

실버 1. 백준 15724 주지수

풀이

구간이 주어지고 해당 2차원 배열 구역 내 누적합을 구하면 되는 문제

코드

from sys import stdin

input = stdin.readline

N, M = map(int, input().split(" "))  # N : len(graph), M : len(graph[0])

graph = [list(map(int, input().split(" "))) for _ in range(N)]

acc = [[0 for _ in range(M + 1)] for _ in range(N + 1)]

# 2차원 누적합 배열 구하기
for i in range(1, N + 1):
    for j in range(1, M + 1):
        acc[i][j] = (
            acc[i - 1][j] + acc[i][j - 1] + graph[i - 1][j - 1] - acc[i - 1][j - 1]
        )

K = int(input())

# 구간 내 2차원 배열 누적합 구하기
for _ in range(K):
    x1, y1, x2, y2 = map(int, input().split(" "))
    print(acc[x2][y2] - acc[x1 - 1][y2] - acc[x2][y1 - 1] + acc[x1 - 1][y1 - 1])

골드 3. 백준 1806 부분합

풀이

처음 완탐으로 접근했을 때는 누적합 배열을 계산해준 뒤, 뒤에서부터 가능한 부분수열을 만들어가면서 길이를 갱신해줬는데 O(N^2)라서 시간초과난다.

내가 생각한 알고리즘에서는 더 시간복잡도를 줄일 수 없을 것 같아 해설을 참고했다. 이 문제는 투 포인터 방식으로 접근해야 한다.

투 포인터

리스트에 순차적으로 접근해야할 때, 두개의 점 위치를 기록하면서 처리하는 알고리즘

1. 부분합 sum_을 첫번째 숫자를 넣어준다. (첫번째 숫자만으로 S를 넘을 수 있으므로)
   start=0, end=0으로 초기화
2. 만약 부분합이 목표 이상이면 sum_ <= S, start~end가 answer보다 작으면 answer 갱신. 부분합에서 해당 숫자(data[start]를 빼주고 왼쪽 포인터 start 한칸 이동
3. 만약 부분합이 목표 미만이면 sum_ > S, 오른쪽 포인터 end 한칸 이동.
   만약 끝까지 다 살펴봤다면 (end = N) break, 아니면 부분합에 현재 숫자(data[end]) 더해주기
4. answer의 초기값은 100,001으로 설정하고 끝까지 다 봤어도 100,001이면 0을 출력 아니면 answer 출력하기

from sys import stdin
input = stdin.readline

N, S = map(int,input().split())
data = list(map(int,input().split()))

start, end = 0, 0
sum_ = data[0]
answer = 100001
 
while True:
    if sum_ >= S:
        sum_ -= data[start]
        answer = min(answer, end - start + 1)
        start += 1
    else:
        end += 1
        if end == N:
            break
        sum_ += data[end]
 
if answer == 100001:
    print(0)
else:
    print(answer)

구현

실버2. 백준 2477 참외밭

나의 풀이

모양 판별을 위해 존재할 수 없는 좌표에 따라 4개의 모양을 판별했다.

위 경우에 따라 내부 사각형의 크기를 계산했다.

코드

from sys import stdin

input = stdin.readline

K = int(input())

x, y = 0, 0
max_x, max_y = -int(1e9), -int(1e9)
min_x, min_y = int(1e9), int(1e9)

data = []

# 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4
for _ in range(6):
    data.append(list(map(int, input().split(" "))))

pos = []
pos_x = []
pos_y = []
for dir_, len_ in data:
    # 동
    if dir_ == 1:
        x += len_
    # 서
    elif dir_ == 2:
        x -= len_
    # 남
    elif dir_ == 3:
        y -= len_
    # 북
    else:
        y += len_

    max_x = max(max_x, x)
    max_y = max(max_y, y)
    min_x = min(min_x, x)
    min_y = min(min_y, y)

    pos.append([x, y])
    pos_x.append(x)
    pos_y.append(y)

pos_x = list(set(pos_x))
pos_y = list(set(pos_y))

pos_x.remove(max_x)
pos_x.remove(min_x)
pos_y.remove(max_y)
pos_y.remove(min_y)

middle_x = pos_x.pop()
middle_y = pos_y.pop()

w = max_x - min_x
h = max_y - min_y

inner_w = 0
inner_h = 0

# ㄴ자
if [max_x, max_y] not in pos:
    inner_w = max_x - middle_x
    inner_h = max_y - middle_y
# ㄱ자
elif [min_x, min_y] not in pos:
    inner_w = middle_x - min_x
    inner_h = middle_y - min_y
# 90도 회전 ㄴ자
elif [min_x, max_y] not in pos:
    inner_w = middle_x - min_x
    inner_h = max_y - middle_y
else:
    inner_w = max_x - middle_x
    inner_h = middle_y - min_y


print(K * (w * h - inner_w * inner_h))

다른 풀이

거진 1시간정도 걸렸고, 코드가 깔끔하지 않아 다른 풀이를 찾아서 공부했다.

입력되는 데이터를 살펴보면, 가장 긴 너비 w는 순서상 이전 이후가 높이에 해당되는 데이터(작은 사각형과 관계X)이고 가장 긴 높이 h 역시 순서상 이전 이후가 너비에 해당되는 데이터(작은 사각형과 관계X)이다.
따라서 w와 h에 인접하지 않은 변의 곱이 내부 사각형의 넓이다.

다른 풀이 2 (이게 더 쉬운 것 같다)

가로 길이와 세로 길이의 최대값을 통해 큰 사각형의 넓이를 구하고, 각 최대길이 변의 양옆 변의 길이의 차가 작은 사각형의 한 변임을 이용하자.

코드

풀이 및 코드는 이 분의 블로그를 참고했다.

from sys import stdin
input = stdin.readline

K = int(input())

data = []
# 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4
for _ in range(6):
    data.append(list(map(int, input().split(" "))))

width = []
height = []
total = []
for dir_, len_ in data:
    # 동 or 서
    if dir_ == 1 or dir_ == 2:
        width.append(len_)
        total.append(len_)
    # 남 or 북
    else:
        height.append(len_)
        total.append(len_)

maxHeightIndex = total.index(max(height))
maxWidthIndex = total.index(max(width))

small1 = abs(total[maxHeightIndex-1] - total[(maxHeightIndex-5 if maxHeightIndex == 5 else maxHeightIndex +1)])
small2 = abs(total[maxWidthIndex-1] - total[(maxWidthIndex-5 if maxWidthIndex == 5 else maxWidthIndex +1)])

print((max(height) * max(width) - small1 * small2) * K)

실버2. 백준 3085 사탕게임

잘 이해가 되지 않는 부분

인접한 사탕을 바꾼 다음에 왜 전체배열을 살펴봐야하는지 이해가 되지 않는다. 어차피 영향을 받는 행, 열은 최대 3개가 아닌가?

이렇게 풀어도... 될 것만 같은데.... 69%에서 계속 틀렸다고 떠서 체크해주는 로직을 전체 배열을 훑도록 수정해주고 넘어갔다.

--> 알고리즘 톡방에서 도와주신 분이 계셔서 고칠 수 있었다!! 로직 자체는 맞았다. 다만 다를 때 체크해주는 코드를 빼고 무조건 교환하는 방식으로 바꿔줘야 한다.

틀린 코드... 왜인지 더 고민해보고 싶어서 기록

from sys import stdin

input = stdin.readline

N = int(input())

board = [list(input().rstrip()) for _ in range(N)]
answer = 0
# 가로줄 변경된 후
def afterSwapLeftRight(row, col):
    global answer

    # 가로줄 체크
    cnt = 1
    for i in range(N - 1):
        if board[row][i] == board[row][i + 1]:
            cnt += 1
        else:
            cnt = 1
        answer = max(answer, cnt)

    # 세로줄 체크
    cnt = 1
    for i in range(N - 1):
        if board[i][col] == board[i + 1][col]:
            cnt += 1
        else:
            cnt = 1
        answer = max(answer, cnt)

    cnt = 1
    for i in range(N - 1):
        if board[i][col + 1] == board[i + 1][col + 1]:
            cnt += 1
            
        else:
            cnt = 1
        answer = max(answer, cnt)

# 세로줄 변경된 후
def afterSwapTopBottom(row, col):
    global answer

    # 가로줄 체크
    cnt = 1
    for i in range(N - 1):
        if board[row][i] == board[row][i + 1]:
            cnt += 1
            
        else:
            cnt = 1
        answer = max(answer, cnt)
    cnt = 1
    for i in range(N - 1):
        if board[row + 1][i] == board[row + 1][i + 1]:
            cnt += 1
            
        else:
            cnt = 1
        answer = max(answer, cnt)
    # 세로줄 체크
    cnt = 1
    for i in range(N - 1):
        if board[i][col] == board[i + 1][col]:
            cnt += 1
            
        else:
            cnt = 1
        answer = max(answer, cnt)

for i in range(N):
    for j in range(N):
        # 세로 방향 교환
        if j + 1 < N:
            if board[i][j] != board[i][j + 1]:
                board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]
                afterSwapLeftRight(i, j)
                board[i][j], board[i][j+1] = board[i][j+1], board[i][j]

        # 가로 방향 교환
        if i + 1 < N:
            if board[i][j] != board[i + 1][j]:
                board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]
                afterSwapTopBottom(i, j)
                board[i][j], board[i+1][j] = board[i+1][j], board[i][j]

print(answer)

위의 코드를 수정!! 통과한 코드

from sys import stdin

input = stdin.readline

N = int(input())

board = [list(input().rstrip()) for _ in range(N)]
answer = 0
# 가로줄 변경된 후
def afterSwapLeftRight(row, col):
    global answer

    # 가로줄 체크
    cnt = 1
    for i in range(N - 1):
        if board[row][i] == board[row][i + 1]:
            cnt += 1
        else:
            cnt = 1
        answer = max(answer, cnt)

    # 세로줄 체크
    cnt = 1
    for i in range(N - 1):
        if board[i][col] == board[i + 1][col]:
            cnt += 1
        else:
            cnt = 1
        answer = max(answer, cnt)

    cnt = 1
    for i in range(N - 1):
        if board[i][col + 1] == board[i + 1][col + 1]:
            cnt += 1
            
        else:
            cnt = 1
        answer = max(answer, cnt)

# 세로줄 변경된 후
def afterSwapTopBottom(row, col):
    global answer

    # 가로줄 체크
    cnt = 1
    for i in range(N - 1):
        if board[row][i] == board[row][i + 1]:
            cnt += 1
            
        else:
            cnt = 1
        answer = max(answer, cnt)
    cnt = 1
    for i in range(N - 1):
        if board[row + 1][i] == board[row + 1][i + 1]:
            cnt += 1
            
        else:
            cnt = 1
        answer = max(answer, cnt)
    # 세로줄 체크
    cnt = 1
    for i in range(N - 1):
        if board[i][col] == board[i + 1][col]:
            cnt += 1
            
        else:
            cnt = 1
        answer = max(answer, cnt)

for i in range(N):
    for j in range(N):
        # 세로 방향 교환
        if j + 1 < N:
            board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]
            afterSwapLeftRight(i, j)
            board[i][j], board[i][j+1] = board[i][j+1], board[i][j]

        # 가로 방향 교환
        if i + 1 < N:
            board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]
            afterSwapTopBottom(i, j)
            board[i][j], board[i+1][j] = board[i+1][j], board[i][j]

print(answer)

전체 배열을 체크하도록 수정, 통과한 코드

from sys import stdin

input = stdin.readline

N = int(input())

board = [list(input().rstrip()) for _ in range(N)]
answer = 0


def check():
    global answer
    for i in range(N):
        cnt = 1
        for j in range(N-1):
            if board[i][j] == board[i][j+1]:
                cnt += 1
                answer = max(answer, cnt)
            else:
                cnt = 1
        
        cnt = 1
        for j in range(N-1):
            if board[j][i] == board[j+1][i]:
                cnt += 1
                answer = max(answer, cnt)
            else:
                cnt = 1
            

for i in range(N):
    for j in range(N):
        # 세로 방향 교환
        if j + 1 < N:
            if board[i][j] != board[i][j + 1]:
                board[i][j], board[i][j + 1] = board[i][j + 1], board[i][j]
                check()
                board[i][j], board[i][j+1] = board[i][j+1], board[i][j]

        # 가로 방향 교환
        if i + 1 < N:
            if board[i][j] != board[i + 1][j]:
                board[i][j], board[i + 1][j] = board[i + 1][j], board[i][j]
                check()
                board[i][j], board[i+1][j] = board[i+1][j], board[i][j]

print(answer)

골드5. 백준 14891 톱니바퀴

풀이

문제에서 나온 조건대로 구현하면 되는 시뮬레이션 문제

조건을 그대로 구현하는 것에서 거진 2시간정도 걸렸는데... 왜 이렇게 오래 걸렸나면 왼쪽, 오른쪽 톱니바퀴를 살펴볼 때 방향을 안 바꿔주고 들어갔다. 기준이 되는 데이터는 인덱스 뿐만 아니라 현재 회전 방향도 꼭 같이 갖고 있어야 한다.

문제 해결 시 중요하게 잡고 가야되는 포인터가 몇가지 있어 기록하기.

1. 회전되기 전 인덱스값(2,6번째)을 저장하여 비교 시 사용한다.
2. 회전시키고자 입력한 기어를 회전시킨다.
3. while문을 사용하여 만약 왼쪽에 기어가 존재한다면, 왼쪽 기어를 살펴본다.
   3-1. 회전시키기 전 비교를 위해 왼쪽 기어의 인덱스 값(6번째)을 저장한다.
   3-2. 왼쪽 기어가 회전이 필요한 상태라면 회전시킨다.
   3-3. 현재방향 기준(copy_dir_)으로 움직일 것
   3-4. 현재방향 기준(copy_dir_)을 업데이트한다.
4. while문을 사용하여 만약 오른쪽에 기어가 존재한다면, 오른쪽 기어를 살펴본다.
   4-1. 회전시키기 전 비교를 위해 오른쪽 기어의 인덱스 값(2번째)을 저장한다.
   4-2. 오른쪽 기어가 회전이 필요한 상태라면 회전시킨다.
   4-3. 현재방향 기준(copy_dir_)으로 움직일 것
   4-4. 현재방향 기준(copy_dir_)을 업데이트한다.

일차원 배열의 회전

1차원 배열의 회전은 deque를 사용하는 것이 훨씬 간편하다! 배열을 회전시킬 일이 있다면 사용해야겠다.

deque의 rotate()

만약 오른쪽(시계방향) 회전을 해야한다면 deque 자료형에서 제공하는 메서드인 rotate() 함수에 양수를 전달한다
만약 왼쪽(반시계방향) 회전을 해야한다면 음수를 전달한다

코드

from sys import stdin
from collections import deque

input = stdin.readline

gear = [[]]

for _ in range(4):
    gear.append(deque(list(input().rstrip())))

K = int(input())

# 1 : 시계(right), -1 : 반시계(left)
for _ in range(K):
    idx, dir_ = map(int, input().split(" "))

    gear_idx2 = gear[idx][2]
    gear_idx6 = gear[idx][6]
    # 본인만 돌리기
    if dir_ == 1:
        gear[idx].rotate(1)
    else:
        gear[idx].rotate(-1)

    # 회전시키면서 변경될 데이터(기준이 되는 인덱스, 방향 저장용) copy_ 생성
    copy_idx = idx
    copy_dir_ = dir_
    # 왼쪽에 기어 존재
    while copy_idx - 1 >= 1:
        # 반대 방향 회전
        if gear_idx6 != gear[copy_idx - 1][2]:
            gear_idx6 = gear[copy_idx - 1][6]
            if copy_dir_ == 1:
                gear[copy_idx - 1].rotate(-1)
                copy_dir_ = -1
            else:
                gear[copy_idx - 1].rotate(1)
                copy_dir_ = 1
            copy_idx -= 1
        # 더이상 살펴볼 필요 없음
        else:
            break

    copy_idx = idx
    copy_dir_ = dir_
    # 오른쪽에 기어 존재
    while copy_idx + 1 <= 4:
        # 반대 방향 회전
        if gear_idx2 != gear[copy_idx + 1][6]:
            gear_idx2 = gear[copy_idx + 1][2]
            if copy_dir_ == 1:
                gear[copy_idx + 1].rotate(-1)
                copy_dir_ = -1
            else:
                gear[copy_idx + 1].rotate(1)
                copy_dir_ = 1
            copy_idx += 1
        # 더이상 살펴볼 필요 없음
        else:
            break

answer = 0
for i in range(1, 5):
    if gear[i][0] == "1":
        answer += 2 ** (i - 1)

print(answer)