Algorithm TIL (240904)

[백준] 참외밭

• https://www.acmicpc.net/problem/2477
• 레벨 : 실버 2

 

문제 접근 과정

• 큰 사각형에서 작은 사각형을 빼면 참외밭의 면적이 나온다.
• 이를 위해 큰 사각형의 가로,세로와 작은 사각형의 가로,세로를 판별해야 한다.
• 육각형의 둘레는 한 모퉁이를 기준으로 반시계방향으로 돈 (방향, 길이)를 순차적으로 입력된다. 그러므로 작은 사각형의 변의 길이를 구하기 위해선, 변의 길이 정보 배열에서 i번째 와 i+2번째의 방향이 같다면 i+1번째의 길이가 작은 사각형의 가로 혹은 세로가 된다.

문제 풀이

python

# 🌱 2477 참외밭 스스로 풀어보기

# 어느 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나는 변의 방향과 길이가 주어진다.
# 이를 순차대로 담아서, i번째 변과 i+2번째 변의 방향이 같다면 i+1번째 변은 작은 사각형의 변이 된다.

k = int(input())
s = [list(map(int, input().split())) for _ in range(6)]

maxL, maxW, smallRec = 0, 0, 1
for i in range(6) :
    if s[i][0] == 1 or s[i][0] == 2 :
        if maxL < s[i][1] :
            maxL = s[i][1]
    elif s[i][0] == 3 or s[i][0] == 4 :
        if maxW < s[i][1] :
            maxW = s[i][1]

for i in range(6) :
    # 만일 i번째 변의 방향과, i+2의 변의 방향이 같다면 작은 사각형의 가로, 세로이므로 값을 곱해준다.
    if s[i][0] == s[(i+2)%6][0] :
        smallRec *= s[(i+1)%6][1]
        
# 원하는 리턴ㄱ밧은 이 참외밭에서 자라는 참외의 수 이므로 (큰사각형 - 작은 사각형) * 1m^2의 넓이에서 자라는 참외의 개수
# 을 연산한 값을 리턴하면 된다.
print((maxL * maxW  - smallRec) * k)

 

예상 시간복잡도 : O(1) 상수 시간복잡도

 

---

 

[백준] 수들의 합 5

• https://www.acmicpc.net/problem/2018
• 레벨 : 실버 5

문제 풀이 과정

• 연속된 부분 수열의 합을 구하여 목표 정수값인 M이 충족되는 개수를 리턴하면 된다.
• 문제를 풀면서 투 포인터에 대한 개념이 부족하여 개념을 다시한번 정리했다.

투포인터

• 리스트에 순차적으로 접근해야 할 때, 두 개의 점 위치를 기록하면서 처리하는 알고리즘
• 시작점과 끝점을 명시해서 접근해야할 데이터의 범위를 표현할 수 있다.
• 대표 문제 : 특정한 합을 가지는 연속된 부분 수열 찾기
• 문제 해결 아이디어
  • 시작점과 끝점을 첫번째 원소의 인덱스(0)을 가리기도록 한다.
  • 현재 부분이 합(M)과 같다면 개수를 카운트한다.
  • 현재 부분이 합(M)보다 작다면, end를 1 증가시킨다.
  • 현재 부분이 합(M)보다 크거나 같다면, start를 1 증가시킨다.
  • 모든 경우를 확인할 때까지 2번~4번 과정을 반복한다.

틀린 풀이

• 메모리 초과
• N만큼 배열을 생성하는 경우, 발생한다. 문제에서 주어진 N의 범위가 1 <= N <= 10,000,000 이다. 
• 파이썬에서 데이터 개수에 따른 메모리 사용량은 아래와 같다. (int형 데이터 1개 = 4byte)

데이터 개수	메모리 사용량
1,000	약 4KB
1,000,000	약 4MB
10,000,000	약 40MB

•  위 문제의 메모리 제한은 32MB이므로 N의 길이만큼 배열을 생성하게 되면 메모리 초과가 발생한다.

# 주어진 N에 대해서, 연속된 부분 수열의 합이 N이 되는 연속된 부분 수열의 총 개수를 리턴하면 된다.
N = int(input()) # 데이터의 개수이자 연속된 부분 수열의 합 (=부분합)
arr = [i for i in range(1, N+1)]
end = 0 # end 0으로 초기화
interval_total = 0 # 연속된 부분 수열의 합 초기화
ans = 0 # 부분합 개수 초기화

# start를 차례대로 증가시키며 반복시킨다.
for start in range(len(arr)) :
    # end를 N의 범위 내에서 가능한 만큼 이동시킨다.
    while interval_total < N and end < N :
        interval_total += arr[end]
        end += 1
    # 부분합이 N이면 개수를 센다.
    if interval_total == N :
        ans += 1
    # 부분합이 N보다 큰 경우 start 를 이동시킨다.
    interval_total -= arr[start]
print(ans)

 

문제 풀이

python

# 투포인터 (Two Pointers)
# 주어진 N에 대해서, 연속된 부분 수열의 합이 N이 되는 연속된 부분 수열의 총 개수를 리턴하면 된다.
N = int(input()) # 데이터의 개수이자 연속된 부분 수열의 합 (=부분합)
end = 1 # end 초기화
interval_total = 0 # 연속된 부분 수열의 합 초기화
ans = 0 # 부분합 개수 초기화

# start를 차례대로 증가시키며 반복시킨다.
for start in range(1, N+1) :
    # end를 N의 범위 내에서 가능한 만큼 이동시킨다.
    while interval_total < N and end <= N :
        interval_total += end
        end += 1
    # 부분합이 N이면 개수를 센다.
    if interval_total == N :
        ans += 1
    # 부분합이 N보다 큰 경우 start 를 이동시킨다.
    interval_total -= start
print(ans)