• 문제
  • 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 문제인 걸 알기

• 문제
  • 1476번: 날짜 계산
• 해설

  • import sys
    
    earth, sun, moon = tuple([int(x) for x in sys.stdin.readline().split()])
    total = 15 * 28 * 19
    
    
    def mod(value, base):
        if value == 0:
            return base
        else:
            return value
    
    
    for i in range(1, total + 1, 1):
        if (earth, sun, moon) == (mod(i % 15, 15), mod(i % 28, 28), mod(i % 19, 19)):
            print(i)
            break

• 포인트
  • 중국인의 나머지 정리를 통해, 해가 15 * 28 * 19 내에 유일하다는 점을 파악
  • BruteForce
  • 해를 찾을 때 까지만 반복

1260 DFS와BFS

• 문제
  • 1260번: DFS와 BFS (acmicpc.net)
• 해설

  • import sys
    import queue
    
    sys.setrecursionlimit(99999)
    
    vertex_count, edge_count, start_vertex = [int(x) for x in sys.stdin.readline().strip().split()]
    edges = [list(map(int, x.strip().split())) for x in sys.stdin.readlines()]
    
    adj_dict = dict()
    chk_dict = dict()
    
    for edge in edges:
        vertex_1, vertex_2 = edge
        if vertex_1 not in adj_dict:
            adj_dict[vertex_1] = [vertex_2]
        else:
            adj_dict[vertex_1].append(vertex_2)
        if vertex_2 not in adj_dict:
            adj_dict[vertex_2] = [vertex_1]
        else:
            adj_dict[vertex_2].append(vertex_1)
    
    for vertex in adj_dict:
        chk_dict[vertex] = False
        adj_dict[vertex] = sorted(list(set(adj_dict[vertex])))
    
    sorted_vertex = sorted(list(chk_dict.keys()))
    chk_dict_bfs = chk_dict.copy()
    dfs_ans = []
    bfs_ans = []
    queue_for_bfs = queue.Queue()
    
    
    def dfs(vertex):
        chk_dict[vertex] = True
        dfs_ans.append(vertex)
        for k in adj_dict[vertex]:
            if not chk_dict[k]:
                dfs(k)
    
    
    def bfs(vertex):
        chk_dict_bfs[vertex] = True
        bfs_ans.append(vertex)
        for k in adj_dict[vertex]:
            if not chk_dict_bfs[k]:
                chk_dict_bfs[k] = True
                queue_for_bfs.put(k)
        if queue_for_bfs.qsize():
            bfs(queue_for_bfs.get())
    
    
    if start_vertex in adj_dict.keys():
        dfs(start_vertex)
        bfs(start_vertex)
        print(' '.join([str(x) for x in dfs_ans]))
        print(' '.join([str(x) for x in bfs_ans]))
    else:
        print(start_vertex)
        print(start_vertex)

• 포인트
  • BFS와 DFS를 구현

• 문제
  • 1182번: 부분수열의 합
• 해설

  • import sys
    
    int_cnt, target_sum = [int(x) for x in sys.stdin.readline().split()]
    
    given_seq = [int(x) for x in sys.stdin.readline().split()]
    
    
    def go(seq, cur_sum, cur_ind, used_inds):
        res = 0
    
        # 정답
        if cur_sum == target_sum and cur_ind == len(seq) and used_inds:
            return 1
    
        # 불가능
        if cur_ind == len(seq):
            return 0
    
        if cur_ind < len(seq):
            # 현재 idx를 사용한 경우
            res += go(seq, cur_sum + seq[cur_ind], cur_ind + 1, used_inds + [cur_ind])
            # 현재 idx를 사용하지 않은 경우
            res += go(seq, cur_sum, cur_ind + 1, used_inds)
    
        return res
    
    
    print(go(given_seq, 0, 0, []))

• 포인트
  • BruteForce임을 눈치챈다.
  • 첫 원소가 포함될 때 안될 때, 각 경우마다 두번째 원소가 포함될 떄 안될 때, ... 재귀 구현

• 문제
  • 10971번: 외판원 순회 2
• 해설

  • import sys
    
    N = int(sys.stdin.readline())
    matrix = [list(map(int, x.strip().split())) for x in sys.stdin.readlines()]
    base_idx = [x for x in range(N)]
    
    
    def next_permutation(list):
        last_asc_idx = 0
        for i in range(len(list) - 1):
            if list[i] < list[i + 1]:
                last_asc_idx = i
    
        val_at_last_asc_idx = list[last_asc_idx]
        last_idx_larger_than_val_at_last_asc_idx = 0
        for j in range(last_asc_idx + 1, len(list), 1):
            if val_at_last_asc_idx < list[j]:
                last_idx_larger_than_val_at_last_asc_idx = j
    
        if last_asc_idx == 0 and last_idx_larger_than_val_at_last_asc_idx == 0:
            return False
        else:
            list[last_asc_idx], list[last_idx_larger_than_val_at_last_asc_idx] = \
                list[last_idx_larger_than_val_at_last_asc_idx], list[last_asc_idx]
            last_idx_larger_than_val_at_last_asc_idx = len(list) - 1
            while (last_asc_idx + 1 < last_idx_larger_than_val_at_last_asc_idx):
                list[last_asc_idx + 1], list[last_idx_larger_than_val_at_last_asc_idx] = \
                    list[last_idx_larger_than_val_at_last_asc_idx], list[last_asc_idx + 1]
                last_asc_idx += 1;
                last_idx_larger_than_val_at_last_asc_idx -= 1
            return True
    
    
    def factorial(k):
        if k == 0 or k == 1:
            return 1
        else:
            res = k
            for i in range(1, k, 1):
                res *= i
            return res
    
    
    total_available_count = factorial(N - 1)
    
    res = []
    for j in range(total_available_count):
        cost = 0
        out_inner_loop = False
    
        # 마지막 도시에서 처음 도시로 가지 못하는 경우 발견
        if matrix[base_idx[N - 1]][base_idx[0]] == 0:
            # 다음 이동 경로 체크
            next_permutation(base_idx)
            continue
        else:
            cost += matrix[base_idx[N - 1]][base_idx[0]]
    
        for i in range(N - 1):
            # 이동이 불가능한 도시의 경우
            if matrix[base_idx[i]][base_idx[i + 1]] == 0:
                out_inner_loop = True
                break
            else:
                cost += matrix[base_idx[i]][base_idx[i + 1]]
        if out_inner_loop:
            # 다음 이동 경로 체크
            next_permutation(base_idx)
            continue
    
        # 가능한 경우가 처음 나왔을 때
        if len(res) == 0:
            res.append(cost)
    
        # 가능한 경우를 이전과 비교  
        else:
            if cost < res[0]:
                res[0] = cost
    
        # 다음 이동 경로 체크
        next_permutation(base_idx)
    
    print(res[0])

• 포인트
  • BruteForce임을 알아채야한다.
  • next permutation을 구현할 수 있어야한다.

문제:www.acmicpc.net/problem/14888

비고:

-Brute force

-next permutation만 있으면 해결됨

-난이도중

문제:www.acmicpc.net/problem/10819

비고:

-Brute force

-다 세지 않고선 규칙을 발견하기 힘들며, 영역 나누기도 힘들어 보이며, 주어진 조건이 가용 시간/메모리 내에 해결 가능

-이런 문제에서 모든 경우를 세기 위해서 next permutation함수를 잘 짜야 한다.

-입력받은 list을 next permutation으로 바꾸며, return은 True/False로 작성

-next permutation을 처음작성하는 거라면 난이도가 있다.

  -기본 규칙은, 배열의 index 0부터(=좌측부터) 우측으로 훑으며 "마지막" 증가(increase)인 index(i)를 찾는다.

  ex) 124653에서 46가 마지막 증가(<)고 4의 index인 2

  -마지막 증가에서의 값보다 크며 가장 우측에 존재하는 값의 index(j)를 찾는다.

  ex) 124653에서 65중에서 5가 더 오른쪽, 5의 index인 4

  -i,j에서의 값 교환

  ex) 124653 -> 125643

  -j보다 우측의 값들을 정렬시킨다.

-난이도중

내소스코드:

boj.kr/33b0cb84fe5d4b48b02c860081023606