• 문제
  • 2170번: 선 긋기
• 해결

import sys

N = int(sys.stdin.readline())
nlist = [list(map(int, x.strip().split())) for x in sys.stdin.readlines()]
nlist.sort()

cumulative_length = 0
cumulative_right_point = -sys.maxsize

for current_left, current_right in nlist:
    if current_left >= cumulative_right_point:
        cumulative_length += (current_right - current_left)
    else:
        if current_right > cumulative_right_point:
            cumulative_length += (current_right - cumulative_right_point)
    cumulative_right_point = max(current_right, cumulative_right_point)
print(cumulative_length)

• 포인트
  • input을 정렬하고(O(NlogN)) 좌측부터 우측으로 O(N)만 함
  • 이를 sweep line 기법이라 함

• 문제
  • 1978번: 소수 찾기
• 해설

import sys

candidate_count = int(sys.stdin.readline())

def is_prime(n):
    if n == 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        else:
            i += 6
    return True

candidates = [int(x) for x in sys.stdin.readline().split()]
prime_count = 0
for candidate in candidates:
    if is_prime(candidate):
        prime_count += 1
print(prime_count)

• 포인트
  • while 문 안에 소수찾는 로직이 중요
    • 제곱이 n보다 작은 자연수이면서 6으로 나눴을 때 나머지가 1, 5인 것만 확인

• 문제
  • 1934번: 최소공배수
• 해설

import sys

test_case_count = int(sys.stdin.readline())

def get_gcd(less, larger):
    if larger == 0:
        return less
    else:
        return get_gcd(larger, less % larger)

for i in range(test_case_count):
    a, b = [int(x) for x in sys.stdin.readline().split()]
    if b > a:
        a, b = b, a
    gcd = get_gcd(a, b)
    print(int((a * b) / gcd))

• 포인트
  • 쉬움

• 문제
  • 2차원 배열이 주어진다. 이 때 이웃한 네개의 영역의 합의 최댓값을 구하시오.
  • 이웃한다란, 위, 아래, 좌, 우로 이동할 수 있음을 가리킨다.
• 해결

import sys

height, width = [int(x) for x in sys.stdin.readline().split()]

mapping = [list(map(int, x.split())) for x in sys.stdin.readlines()]
case_to_sub = {
    0: 2,
    1: 1,
    2: 8,
    3: 4,
    4: 4
}

def case_sub_to_available(case, sub, total_row, total_col):
    if case == 0 and sub == 0:
        return total_row, total_col - 3, 0, 0
    elif case == 0 and sub == 1:
        return total_row - 3, total_col, 0, 0

    elif case == 1 and sub == 0:
        return total_row - 1, total_col - 1, 0, 0

    elif case == 2 and sub == 0:
        return total_row - 2, total_col - 1, 0, 0
    elif case == 2 and sub == 1:
        return total_row - 1, total_col - 2, 0, 0
    elif case == 2 and sub == 2:
        return total_row - 2, total_col - 1, 0, 0
    elif case == 2 and sub == 3:
        return total_row - 1, total_col - 2, 1, 0

    elif case == 2 and sub == 4:
        return total_row - 2, total_col - 1, 2, 0
    elif case == 2 and sub == 5:
        return total_row - 1, total_col - 2, 0, 0
    elif case == 2 and sub == 6:
        return total_row - 2, total_col - 1, 0, 0
    elif case == 2 and sub == 7:
        return total_row - 1, total_col - 2, 0, 0

    elif case == 3 and sub == 0:
        return total_row - 2, total_col - 1, 0, 0
    elif case == 3 and sub == 1:
        return total_row - 1, total_col - 2, 1, 0

    elif case == 3 and sub == 2:
        return total_row - 2, total_col - 1, 1, 0
    elif case == 3 and sub == 3:
        return total_row - 1, total_col - 2, 0, 0

    elif case == 4 and sub == 0:
        return total_row - 1, total_col - 2, 0, 0
    elif case == 4 and sub == 1:
        return total_row - 2, total_col - 1, 1, 0
    elif case == 4 and sub == 2:
        return total_row - 1, total_col - 2, 1, 0
    elif case == 4 and sub == 3:
        return total_row - 2, total_col - 1, 0, 0

def get_val(case, sub, r, c, d):
    if case == 0 and sub == 0:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r][c + 3]
    elif case == 0 and sub == 1:
        return d[r][c] + d[r + 1][c] + d[r + 2][c] + d[r + 3][c]

    elif case == 1 and sub == 0:
        return d[r][c] + d[r + 1][c] + d[r][c + 1] + d[r + 1][c + 1]

    elif case == 2 and sub == 0:
        return d[r][c] + d[r + 1][c] + d[r + 2][c] + d[r + 2][c + 1]
    elif case == 2 and sub == 1:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r + 1][c]
    elif case == 2 and sub == 2:
        return d[r][c] + d[r][c + 1] + d[r + 1][c + 1] + d[r + 2][c + 1]
    elif case == 2 and sub == 3:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r - 1][c + 2]

    elif case == 2 and sub == 4:
        return d[r][c] + d[r][c + 1] + d[r - 1][c + 1] + d[r - 2][c + 1]
    elif case == 2 and sub == 5:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r + 1][c + 2]
    elif case == 2 and sub == 6:
        return d[r][c] + d[r][c + 1] + d[r + 1][c] + d[r + 2][c]
    elif case == 2 and sub == 7:
        return d[r][c] + d[r + 1][c] + d[r + 1][c + 1] + d[r + 1][c + 2]

    elif case == 3 and sub == 0:
        return d[r][c] + d[r + 1][c] + d[r + 1][c + 1] + d[r + 2][c + 1]
    elif case == 3 and sub == 1:
        return d[r][c] + d[r][c + 1] + d[r - 1][c + 1] + d[r - 1][c + 2]
    elif case == 3 and sub == 2:
        return d[r][c] + d[r][c + 1] + d[r - 1][c + 1] + d[r + 1][c]
    elif case == 3 and sub == 3:
        return d[r][c] + d[r][c + 1] + d[r + 1][c + 1] + d[r + 1][c + 2]

    elif case == 4 and sub == 0:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r + 1][c + 1]
    elif case == 4 and sub == 1:
        return d[r][c] + d[r][c + 1] + d[r - 1][c + 1] + d[r + 1][c + 1]
    elif case == 4 and sub == 2:
        return d[r][c] + d[r][c + 1] + d[r][c + 2] + d[r - 1][c + 1]
    elif case == 4 and sub == 3:
        return d[r][c] + d[r + 1][c] + d[r + 1][c + 1] + d[r + 2][c]

max_ = 0
for case in case_to_sub.keys():
    for sub in range(case_to_sub[case]):
        row_cnt, col_cnt, start_row, start_col = case_sub_to_available(case, sub, height, width)
        for r in range(start_row, start_row + row_cnt, 1):
            for c in range(start_col, start_col + col_cnt, 1):
                val = get_val(case, sub, r, c, mapping)
                if val > max_:
                    max_ = val
print(max_)

• 포인트
  • 테트로미노와 같다.
  • Bruteforce로 해결한다.

• 문제
  • 수열이 주어졌을 때 서로 다른 두 요소의 합의 최댓값을 구하시오. 단, 두 요소는 연속해서는 안된다.
    • 각 요소는 정수이다.
    • 수열의 길이는 최대 1,000,000
  • 예시
    • 1 2 6 7 8 → 6 + 8 =14 가 정답
    • 9 8 7 9 → 9 + 9 = 18 가 정답
• 해설

import sys

numbers = [int(x) for x in sys.stdin.readline().split()]

# 수열의 길이가 3일 때
if len(numbers) == 3:
	print(numbers[0] + numbers[2])

# 수열을 한번 돌면서 top-4 element의 값과 index를 저장한다.
top_four_values = {1:0, 2:0, 3:0, 4:0}
top_four_indexs = {1:0, 2:0, 3:0, 4:0}
for idx, val in enumerate(numbers):
	# 현재까지 1등보다 컸다면
	if val > top_four_values[1]:
		top_four_values[4] = top_four_values[3]
		top_four_indexs[4] = top_four_indexs[3]
		top_four_values[3] = top_four_values[2]
		top_four_indexs[3] = top_four_indexs[2]
		top_four_values[2] = top_four_values[1]
		top_four_indexs[2] = top_four_indexs[1]
		top_four_values[1] = val
		top_four_indexs[1] = idx
		
	# 현재까지 1등보다는 작지만 2등보다 컸다면
	elif val > top_four_values[2]:
		top_four_values[4] = top_four_values[3]
		top_four_indexs[4] = top_four_indexs[3]
		top_four_values[3] = top_four_values[2]
		top_four_indexs[3] = top_four_indexs[2]
		top_four_values[2] = val
		top_four_indexs[2] = idx

	# 현재까지 2등보다는 작지만 3등보다 컸다면
	elif val > top_four_values[3]:
		top_four_values[4] = top_four_values[3]
		top_four_indexs[4] = top_four_indexs[3]
		top_four_values[3] = val
		top_four_indexs[3] = idx

	# 현재까지 3등보다 작지만 4등보다 컸다면
	elif val > top_four_values[4]:
		top_four_values[4] = val
		top_four_indexs[4] = idx

# 네 개의 indexs와 values로 정답찾기
maximum = 0
for i in range(1, 4, 1):
	for j in range(2, 5, 1):
		if abs(top_four_indexs[i] - top_four_indexs[j]) > 1:
			if maximum < (top_four_values[i] + top_four_values[j]):
				maximum = (top_four_values[i] + top_four_values[j])

print(maximum)

• 포인트
  • top-1,2,3,4 정보만 알면 된다는 것

• 문제
  • N(1≤N≤200)개의 직사각형(x1,y1,x2,y2, 좌측하단 좌표와 우측상단 좌표의 tuple)이 주어진다. 이 때 정확히 두 개의 직사각형에만 속하는 단위정사각형의 개수를 구하여라.
• 해설

import sys

number_rectangles = int(sys.stdin.readline())
rectangles = [list(map(int, x.split())) for x in sys.stdin.readlines()]
# number_rectangles = 3
# rectangles = [
#     [1, 1, 4, 4],
#     [3, 2, 5, 5],
#     [2, 5, 4, 6]
# ]

intersecting_number = 2

# Create slices
slices = []
for rectangle in rectangles:
    slices.append(rectangle[1])
    slices.append(rectangle[3])
slices = list(set(slices))
slices.sort()  # O(NlogN), slice는 rectangle 개수에 선형적으로 증가하기 때문

# Determine where the rectangle belonging to slices
rectangles.sort(key=lambda x: x[1])  # O(NlogN)
slice_to_rectangles = {idx: [] for idx in range(len(slices) - 1)}

def binary_search(arr, target, low=None, high=None):  # O(logN)
    low, high = low or 0, high or len(arr) - 1
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] > target:
        return binary_search(arr, target, low, mid)
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)

previous_start_slice_idx = 0
for idx_rec, rectangle in enumerate(rectangles):  # O(NlogN)
    start_slice_idx = binary_search(slices, rectangle[1], low=previous_start_slice_idx)
    end_slice_idx = binary_search(slices, rectangle[3], low=previous_start_slice_idx) - 1
    for idx_slice in range(start_slice_idx, end_slice_idx + 1, 1):
        slice_to_rectangles[idx_slice].append(idx_rec)
    previous_start_slice_idx = start_slice_idx

# Iterate from slices, left x + 1, right x - 1하여 cumulative sum==k 세기
def get_cumulative_sum(list_of_tuples):
    result = [list_of_tuples[0]]
    cum_sum = list_of_tuples[0][1]
    for tp in list_of_tuples[1:]:
        cum_sum += tp[1]
        result.append((tp[0], cum_sum))
    return result

answer = 0
for idx_slice in range(len(slices) - 1):  # O(N^2 * logN)
    rectangle_idxs = slice_to_rectangles[idx_slice]
    sorted_xs = []
    for rectangle_idx in rectangle_idxs:
        sorted_xs.append((rectangles[rectangle_idx][0], +1))
        sorted_xs.append((rectangles[rectangle_idx][2], -1))
    sorted_xs.sort(key=lambda x: x[0])
    xs_with_cumulative_sum = get_cumulative_sum(sorted_xs)
    for ind, (x, cum_sum) in enumerate(xs_with_cumulative_sum):
        if cum_sum == intersecting_number:
            width = xs_with_cumulative_sum[ind + 1][0] - x
            height = slices[idx_slice + 1] - slices[idx_slice]
            answer += width * height
print(answer)

• 포인트
  • sweep line개념으로 y1좌표를 기준으로 아래에서 위로 line segment 만들어서 접근
  • left는 +1, right는 -1을 두고 cumulative sum으로 intersecting 횟수 세기

• 문제
  • 1929번: 소수 구하기
• 해설

import sys

minimum, maximum = [int(x) for x in sys.stdin.readline().split()]


def prime_candidate_generator_less_than(n):
    # 5, 7, 11, 13, 17, 19, ...
    candidate = 5
    increment = 2
    increment_changer = {2: 4, 4: 2}
    while candidate <= n:
        yield candidate
        candidate += increment
        increment = increment_changer[increment]


def get_primes_by_sieve_less_than(n):
    if n == 1:
        return []
    elif n == 2:
        return [2]
    elif n == 3:
        return [2, 3]
    else:
        prime_list = [2, 3]
        sieve_list = [True] * (n + 1)
        for candidate in prime_candidate_generator_less_than(n):
            if sieve_list[candidate]:
                prime_list.append(candidate)
                for i in range(2, 1 + (n // candidate)):
                    sieve_list[candidate * i] = False
        return prime_list


res = get_primes_by_sieve_less_than(maximum)
for i in res:
    if i >= minimum:
        print(i)

• 포인트
  • 에라토스테네스 체(sieve) 사용

1759 암호 만들기

• 문제
  • 1759번: 암호 만들기
• 해설

  • import sys
    
    target_length, C = [int(x) for x in sys.stdin.readline().split()]
    
    available_alphabets = sorted(sys.stdin.readline().split())
    
    
    def is_available(test_password):
        total_jaum = set('aeiou')
        if len(total_jaum & set(test_password)) >= 1 and len(set(test_password) - total_jaum) >= 2:
            return True
        else:
            return False
    
    
    def recursive_finder(test_password):
        # 불가능한 경우
        if len(test_password) > target_length:
            return None
    
        # 정답인 경우
        if len(test_password) == target_length and is_available(test_password):
            print(test_password)
    
        # 계속 호출인 경우
        if len(test_password) == 0:
            for i in available_alphabets:
                recursive_finder(test_password + i)
    
        if 0 < len(test_password) < target_length:
            for i in available_alphabets[1 + available_alphabets.index(test_password[-1]):]:
                recursive_finder(test_password + i)
    
    
    recursive_finder('')

• 포인트
  • Bruteforce
  • Recursive function

1707 이분 그래프

• 문제
  • 1707번: 이분 그래프
• 해설

  • import sys
    
    sys.setrecursionlimit(99999)
    
    test_case_count = int(sys.stdin.readline().strip()[0])
    input_gen = (list(map(int, x.strip().split())) for x in sys.stdin.readlines())
    
    
    def trans(x):
        return -x
    
    
    def dfs(vertex, adj, chk, label_history, prev, res):
        chk[vertex] = True
    
        # labeling 한 적 없었으면 labeling
        if vertex not in label_history:
            label_history[vertex] = trans(prev)
    
        for neighbor in adj[vertex]:
            # Not bipartite인 경우 dfs 종료
            if neighbor in label_history and label_history[neighbor] == label_history[vertex]:
                res.append(1)
                break
            if not chk[neighbor]:
                dfs(neighbor, adj, chk, label_history, label_history[vertex], res)
    
    
    def check_bipartite(adj, chk):
        res = []
        first = True
        for vertex in adj:
            if first:
                dfs(vertex, adj, chk, {}, 1, res)
                first = False
            if chk[vertex] == False:
                dfs(vertex, adj, chk, {}, 1, res)
        if res:
            print('NO')
        else:
            print('YES')
    
    
    for case in range(test_case_count):
        vertex_count, edge_count = next(input_gen)
        chk = [False] * (vertex_count + 1)
        adj = {}
        for y in range(edge_count):
            vertex_1, vertex_2 = next(input_gen)
            if vertex_1 not in adj:
                adj[vertex_1] = [vertex_2]
            else:
                adj[vertex_1].append(vertex_2)
            if vertex_2 not in adj:
                adj[vertex_2] = [vertex_1]
            else:
                adj[vertex_2].append(vertex_1)
        check_bipartite(adj, chk)

• 포인트
  • DFS 설정

• 문제
  • 1697번: 숨바꼭질
• 해설

  • import sys
    from collections import deque
    
    sys.setrecursionlimit(1000000)
    
    subin, sister = [*map(int, sys.stdin.readline().strip().split())]
    
    # 시작부터 수빈이가 선두인 경우는 수빈이가 뒷걸음치는 것만 가능
    if subin >= sister:
        print(subin - sister)
        sys.exit()
    
    q = deque()
    map_ = [0] * 200000
    
    
    def bfs(subin_position, current_seconds):
        candidates = [subin_position - 1, subin_position + 1, 2 * subin_position]
        candidates = [candidate for candidate in candidates
                      if 0 <= candidate <= 100000 and map_[candidate] == 0]
        next_seconds = current_seconds + 1
        for candidate in candidates:
            # 수빈이가 동생 찾았을 때
            if candidate == sister:
                print(next_seconds)
                sys.exit()
    
            map_[candidate] = next_seconds
    
            q.appendleft((candidate, next_seconds))
        if len(q):
            bfs(*q.pop())
    
    
    bfs(subin, 0)

• 포인트
  • BFS 문제인 걸 알기