Awesome

https://programmers.co.kr/learn/courses/30/lessons/42839

문자열 형태로 주어지는 숫자로 만들 수 있는 모든 수에서 소수의 갯수를 찾는 문제이다. 이 문제를 두 개로 나누어보자. 

1) 문자열 형태로 주어지는 숫자로 만들 수 있는 모든 수를 구하기.

2) 소수를 찾기.

먼저 1)번을 보자. 문자열 형태로 주어지는 숫자란, "17", "011" 등을 말한다. 만약 "17"이 주어졌다면 "1", "7"로 만들 수 있는 모든 수를 구해야 한다.

문자열 형태든 무슨 형태든 일단 헷갈리니까  1과 7을 가지고 모든 수를 구하는 방법을 생각해보자.

모든 수를 구한다는 것은 가능한 모든 경우의 수를 구한다는 것이다. 순열을 구하는 방식으로 가능한 모든 경우의 수를 구할 수 있겠다. (조합이 아님)

그리고 매개변수가 문자열 형태로 주어지므로, "17"을 "1"과 "7"로 만들기 위해서 간단히 문자열을 리스트로 감싸주자. 

ex) list("17") --> ["1", "7"]

1)번 문제는 for문을 직접 돌며 재귀로 구할 수도 있고, itertools의 permutation을 이용해서 풀 수도 있다.

itertools 방식이 훨씬 깔끔하긴 하다.

2)번 소수를 찾는 문제에 대해 얘기해보자. 만약 작은 수부터 차례대로 소수를 구하는 문제였다면 소수 판별을 위해서 더 작은 소수로만 나눠보려고 했을 것이다.

하지만 이 문제에서는 "17"처럼 7보다 작은 소수인 2, 3, 5가 등장하지 않고 7이 제일 먼저 등장할 수도 있다.

그래서 자기보다 작은 소수로 나눠보는 방식으로 판별은 불가능하고(아니 복잡해지고), 1보다는 크고, 자신의 제곱근보다 같거나 작은 수로 나눠봐야 한다.

itertools를 사용하지 않은 코드

def dfs(n_list, checked, true_cnt, primes, selected):
    if true_cnt > 0:
        n = int("".join(selected))
        if is_prime(n):
            primes.add(n)
        if true_cnt == len(n_list):
            return

    for idx, ch in enumerate(checked):
        if not checked[idx]:
            checked[idx] = True
            selected.append(n_list[idx])
            dfs(n_list, checked, true_cnt+1, primes, selected)
            checked[idx] = False
            selected.pop()

    return primes


def solution(numbers):
    n_list = list(numbers)  # numbers의 길이를 알아내기 위해 리스트로 바꾼다.
    checked = [False for _ in n_list]
    return len(dfs(n_list, checked, 0, set(), []))

itertools를 사용한 코드

from itertools import permutations


def is_prime(n):
    prime = True
    if n < 2:
        prime = False
    for i in range(2, int(n ** 0.5)+1):  # n의 0.5제곱 = 제곱근
        if n % i == 0:
            prime = False
    return prime


def solution(numbers):
    answer = set()
    for i in range(1, len(numbers)+1):
        for p in permutations(numbers, i):
            n = int("".join(p))
            if is_prime(n):
                answer.add(n)
    return len(answer)

http://boj.kr/16637 

import sys


def _calc(n1, n2, oper):
    if oper == '+':
        return n1 + n2
    elif oper == '-':
        return n1 - n2
    elif oper == '*':
        return n1 * n2


def calc():
    global max_result
    buf = []  # 연산식을 담는데, 괄호는 미리 계산해서 담는다
    
    i = 0
    while i < len(arr):
        if i+2 < len(arr) and paren[i] == paren[i+2] == True:
            tmp = _calc(int(arr[i]), int(arr[i+2]), arr[i+1])  # 괄호 안의 식은 미리 계산
            buf.append(tmp)
            i += 3  
        else:
            if arr[i].isdigit():
                buf.append(int(arr[i]))
            else:
                buf.append(arr[i])
            i += 1

    i = 2
    ret = buf[0]
    while i < len(buf):
        ret = _calc(ret, buf[i], buf[i-1])
        i += 2
    max_result = max(max_result, ret)


def dfs(i):
    while i < len(arr) - 2:  # 마지막 괄호를 쳐볼 수 있는 숫자는 끝에서 두 번째 숫자이다
        if paren[i] == False:
            paren[i] = paren[i+2] = True  # 이번 숫자와, 다음 숫자에 괄호를 표시
            dfs(i+2)
            paren[i] = paren[i+2] = False  # 재귀 함수에서 돌아온 이후에는 괄호를 체크 해제
        i += 2
    calc()
    return


input = sys.stdin.readline
N = int(input())
arr = list(input()[:-1])  # 숫자와 연산자를 모두 한 배열에 담는다.
paren = [False for _ in range(len(arr))]  # 괄호쳤음을 표시
max_result = float('-inf')
dfs(0)
print(max_result)

http://boj.kr/16637 

모든 경우를 살펴야 하는 완전탐색 문제이다. 각 숫자를 처음부터 보면서, 이번 숫자가 먼저 계산되는 경우와 괄호 때문에 나중에 계산되는 경우를 각각 나눠서 재귀를 호출하면 모든 경우를 다 볼 수 있다.

1+2*3 가 있다고 하고, 이번 숫자는 1이라고 해보자. 1이 먼저 계산되는 경우는 (1+2)*3 일 것이고, 먼저 계산되지 않는 경우는 괄호가 뒤에 있어서 1+(2*3)인 경우일 것이다. 모든 숫자에 대해서 가능한 케이스는 먼저 계산되는 케이스이거나, 괄호 때문에 나중에 계산되는 케이스가 전부이므로 이렇게 두 경우를 보면 모든 케이스를 다 살펴볼 수 있다.

재귀함수의 매개변수는 idx, ret인데 idx는 연산자의 인덱스를 말한다. 왜 갑자기 연산자의 인덱스를 보냐?고 할 수도 있는데, 뭐 숫자의 인덱스나 연산자의 인덱스나 똑같다. ret는 지금까지 계산된 결과이다. 문제에서 식은 순서대로 계산되며, 두 번 괄호가 쳐질 수 없다고 했으므로 앞에서부터 ret을 계산하면 된다.

다시 돌아가서, 이번 숫자가 먼저 계산되는 경우, 그러니까 (1+2)*3일 때는 사실 순서대로 계산하면 된다. 이번 숫자가 1이고 다음 숫자가 2이므로, 1과 2를 더하면 된다. 그리고 재귀함수를 호출할 때는 이번 숫자에 대한 계산이 끝났으므로 idx를 1 증가시켜서 호출하면 된다.

나중에 계산되는 경우, 그러니까 1+(2*3)같은 경우는 2*3을 먼저 계산한 후, 1+(2*3의 결과)를 다시 계산해서 그 다음에 그 결과를 가지고 재귀를 호출한다. 여기서 결과라는건 계산의 결과인 ret을 의미한다. 여기서 주의해야 할 점은 이번에 본 숫자는 1인데 2칸 앞서 나가서 3까지 계산해버렸으므로, 다음 idx는 2를 더한 idx+2가 될 것이다. 

import sys


def divide_num_operator(string, num, operator):
    for i in string[:-1]:
        if i.isdigit():
            num.append(int(i))
        else:
            operator.append(i)


def calc(n1, n2, operator):
    if operator == '*':
        return n1 * n2
    elif operator == '+':
        return n1 + n2
    elif operator == '-':
        return n1 - n2


def dfs(idx, ret):
    global max_sum
    if idx >= len(operator):
        max_sum = max(max_sum, ret)
        return

    # 이번에 계산 되는 경우
    dfs(idx+1, calc(ret, num[idx+1], operator[idx]))

    # 이번에 계산되지 않는 경우->뒤에가 먼저 계산되는 경우(괄호가 나보다 뒤에 있음)
    if idx+1 < len(operator):
        dfs(idx+2, calc(ret, calc(num[idx+1], num[idx+2], operator[idx+1]), operator[idx]))


def solution(arr):
    divide_num_operator(arr, num, operator)

    dfs(0, num[0])


max_sum = float('-inf')
input = sys.stdin.readline
N = int(input())
arr = input()
num, operator = [], []
solution(arr)
print(max_sum)

http://boj.kr/12100 

보드는 동서남북으로 기울일 수 있으므로 임의로 각 방향마다 0~4까지 번호를 정해주었다. 

그리고 미리 가능한 방향들의 경우의 수를 모두 구한 후에 그대로 기울여본 후 최대값을 갱신하는 방식으로 진행했다.

가능한 방향들의 경우의 수를 구하는 방법은, 뽑을 수 있는 가짓수(방향)는 4개이고 총 5개를 뽑아야 하므로 4개 중 5개를 중복을 허용하는 순열로 뽑았다. 기울이는 순서에 따라 결과도 달라지므로 조합이 아니라 순열로 뽑아야 한다.

한 가지 방향으로 기울이는 방법만 알면 나머지 방향은 조금씩만 수정하면 되므로, 위로 기울이는 방법을 보자.

위로 기울인다는 것은 (0, 0) 원소 입장에서 (1, 0) 에 있는 원소들을 땡겨온다는 뜻이다. 

여기서 두 케이스가 있을 수 있다. 기준 원소 (0, 0)의 값이 0인 케이스와 0이 아닌 케이스가 있을 수 있다.

먼저 값이 0이면 다음 행에 있는 것들 중 0이 아닌 값을 찾아서 가져와야 한다. 즉, 먼저 밀어주어야 한다. 

이제 기준 원소의 값이 0이 아니게 되었으면, 거기서부터 다시 그 다음 행에서 0이 아닌 값들을 가져와서 비교한다.

비교해서 같은 값이면 합쳐준다. 다른 값이면 아무 행동도 하지 않는다. 어차피 다음 반복문에서 그 원소를 땡겨오거나 사용하게 될 것이다.

남쪽으로 밀어줄 때는 기준 원소가 0에서 시작하는 것이 아니라 N-1에서 시작해서 1로 끝난다는 점이 달라진다.

마지막이 (1, y)가 되고 비교 원소가 (0, y)가 될 것이므로 마지막 row가 0이 아닌 1이 된다. 마지막 row를 0으로 두면 그 다음 비교 원소가 -1이 되므로, out of index가 되거나 비교문을 한번 넣어줘야 한다.

주의해야 할 점은 한 번의 기울임마다 두 번 합쳐질 수 없다는 뜻이지, 한번 합쳐진 원소는 두번 다시 못 합쳐진다는 뜻이 아니므로 한번 기울여진 적이 있음을 체크하는 배열을 계속 초기화해줘야 된다는 점이다. (여기서는 added를 계속 새로 선언했다.)

import sys
from copy import deepcopy


def solve(selected):
    board = deepcopy(board_o)
    for direct in selected:
        added = [[False for _ in range(N)] for _ in range(N)]
        if direct == 0:  # UP
            for r in range(N-1):
                for c in range(N):
                    next_r = r + 1
                    
                    # 기준 원소의 값이 0일 때 -> 0이 아닌 값을 찾아서 땡겨온다.
                    if board[r][c] == 0:
                        while next_r < N:
                            if board[next_r][c] == 0:
                                next_r += 1
                            else:
                                board[r][c] = board[next_r][c]
                                board[next_r][c] = 0
                                break
                                
                    # 기준 원소의 값이 0이 아닐 때 -> 다음 줄에 있는 원소 중 0이 아닌 것을 땡겨온다.
                    while next_r < N:
                        if board[next_r][c] == 0:
                            next_r += 1
                        else:  # 0이 아닌 것을 땡겨 왔으면 비교 후 같으면 합쳐준다.
                            if board[r][c] == board[next_r][c] \
                                    and not added[next_r][c] and not added[r][c]:
                                board[r][c] = board[r][c] * 2
                                board[next_r][c] = 0
                                added[r][c] = True
                                added[next_r][c] = False
                            break
        elif direct == 1:  # DOWN
            for r in reversed(range(1, N)):
                for c in range(N):
                    next_r = r - 1
                    if board[r][c] == 0:
                        while next_r >= 0:
                            if board[next_r][c] == 0:
                                next_r -= 1
                            else:
                                board[r][c] = board[next_r][c]
                                board[next_r][c] = 0
                                break
                    while next_r >= 0:
                        if board[next_r][c] == 0:
                            next_r -= 1
                        else:
                            if board[r][c] == board[next_r][c] \
                                    and not added[next_r][c] and not added[r][c]:
                                board[r][c] = board[r][c] * 2
                                board[next_r][c] = 0
                                added[r][c] = True
                                added[next_r][c] = False
                            break
        elif direct == 2:  # LEFT
            for r in range(N):
                for c in range(N - 1):
                    next_c = c + 1
                    if board[r][c] == 0:
                        while next_c < N:
                            if board[r][next_c] == 0:
                                next_c += 1
                            else:
                                board[r][c] = board[r][next_c]
                                board[r][next_c] = 0
                                break
                    while next_c < N:
                        if board[r][next_c] == 0:
                            next_c += 1
                        else:
                            if board[r][c] == board[r][next_c] \
                                    and not added[r][next_c] and not added[r][c]:
                                board[r][c] = board[r][c] * 2
                                board[r][next_c] = 0
                                added[r][c] = True
                                added[r][next_c] = False
                            break
        elif direct == 3:  # Right
            for r in range(N):
                for c in reversed(range(1, N)):
                    next_c = c - 1
                    if board[r][c] == 0:  # 땡기기
                        while next_c >= 0:
                            if board[r][next_c] == 0:
                                next_c -= 1
                            else:
                                board[r][c] = board[r][next_c]
                                board[r][next_c] = 0
                                break
                    while next_c >= 0:
                        if board[r][next_c] == 0:
                            next_c -= 1
                        else:
                            if board[r][c] == board[r][next_c] \
                                    and not added[r][next_c] and not added[r][c]:
                                board[r][c] = board[r][c] * 2
                                board[r][next_c] = 0
                                added[r][c] = True
                                added[r][next_c] = False
                            break

    ret = max([max(r) for r in board])
    return ret


def dfs(count, selected):
    global maxRet
    if count == 5:
        maxRet = max(maxRet, solve(selected))
        return
    for i in range(4):
        dfs(count+1, selected+[i])
    return maxRet


maxRet = 0
input = sys.stdin.readline
N = int(input())
board_o = [list(map(int, input().split())) for _ in range(N)]
print(dfs(0, []))

http://boj.kr/17609 

 
먼저 is_palindrome 은 회문인지 알아보는 함수이다. str[i] == str[길이-i-1] 인지 검사해서 회문인지 알아낸다. i의 범위는 range(0, 스트링 길이의 절반+1) 이다. 스트링 길이의 절반+1인 이유는 직접 해보면 알겠지만 range (a,b) 는 a부터 b-1까지 리턴하기 때문이다.
회문이 아니라면 이제 한번더 기회를 줘서 유사회문인지 알아봐야 한다.
방법이 두가지가 있는데, 양쪽을 비교했는데 서로 다른 문자를 발견하면 1) 왼쪽 문자를 무시하거나 2) 오른쪽 문자를 무시하는 방법이 있다.
왼쪽 문자를 무시하는 방법은 i -> i+1 이고,
오른쪽 문자를 무시하는 방법은 스트링길이-i-1 -> 스트링길이-i-1-1 이다.
두 방법을 모두 시도해본 후에 그렇게 한 문자를 무시하니 회문이 된다면 유사 회문이고,
그랬는데도 서로다른 문자가 나오면 이것도 저것도 아닌 문자열이다.

import sys


# 왼쪽을 +1 해서 탐색, i는 다른 문자가 나온 위치
def can_palindrome_left(str, i, length): 
    for j in range(i, length):
        if str[j+1] != str[-j-1]:
            return 2
    return 1


# 오른쪽을 -1 해서 탐색, i는 다른 문자가 나온 위치
def can_palindrome_right(str, i, length):  
    for j in range(i, length):
        if str[j] != str[-j-1-1]:
            return 2
    return 1


def is_palindrome(str):
    length = (len(str) // 2) + 1
    for i in range(length):
        if str[i] != str[-i-1]:
            if can_palindrome_left(str, i, length) == 2:
                if can_palindrome_right(str, i, length) == 2:
                    return 2
                else:
                    return 1
            else:
                return 1
    return 0


input = sys.stdin.readline
N = int(input())

for _ in range(N):
    print(is_palindrome(list(input()[:-1])))

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

4개의 방향을 중복 순열로 가능한 가짓수를 모두 뽑아서(4^5) 각각 이동을 시키는 방법(n^2)으로 풀었다. 

BFS,DFS로 푸는 방법도 있던데 이 방법은 완전탐색에 가까운 것 같다.

import sys
import collections
from copy import deepcopy
WEST, EAST, NORTH, SOUTH = 1, 2, 3, 4


def Print(lst):
    for i in lst:
        for j in i:
            print(j, end=" ")
        print("")
    print("")


def move_north(board):
    queue = collections.deque()
    joinable = [[True for _ in range(n)] for _ in range(n)]  # 한번 합쳐진 블록은 False로 표시
    
    # 작업할 큐를 만듦
    for row in range(n):
        for col in range(n):
            if board[row][col] != 0:  # 0이 아니면 추가
                queue.append([row, col])
            else:  # 0이면 0이 아닌 값을 땡겨와서 추가
                for sub_row in range(row+1, n):
                    if board[sub_row][col] != 0:
                        board[row][col] = board[sub_row][col]
                        board[sub_row][col] = 0
                        queue.append([row, col])
                        break

    while queue:
        row, col = queue.popleft()
        if 0 <= row + 1 < n:
            if board[row][col] == 0 and board[row+1][col] != 0:  # 처음에는 0이 아니었지만 합쳐지면서 0이 된 경우
                board[row][col] = board[row+1][col]  # row+1을 땡겨온다. joinable도 땡겨옴
                board[row+1][col] = 0
                joinable[row][col] = joinable[row+1][col]
                joinable[row+1][col] = True
                if joinable[row][col]:
                    queue.append([row, col])
            elif board[row][col] == board[row+1][col]:  # 합침
                board[row][col] = board[row][col]*2
                board[row+1][col] = 0
                joinable[row][col] = False


def move_south(board):
    queue = collections.deque()
    joinable = [[True for _ in range(n)] for _ in range(n)]
    for row in reversed(range(0, n)):
        for col in range(0, n):
            if board[row][col] != 0:
                queue.append([row, col])
            else:
                for sub_row in reversed(range(0, row)):
                    if board[sub_row][col] != 0:
                        board[row][col] = board[sub_row][col]
                        board[sub_row][col] = 0
                        queue.append([row, col])
                        break

    while queue:
        row, col = queue.popleft()
        if 0 <= row - 1 < n:
            if board[row][col] == 0 and board[row-1][col] != 0:  # 처음에는 0이 아니었지만 합쳐지면서 0이 된 경우
                board[row][col] = board[row-1][col]
                board[row-1][col] = 0
                joinable[row][col] = joinable[row-1][col]
                joinable[row-1][col] = True
                if joinable[row][col]:
                    queue.append([row, col])
            elif board[row][col] == board[row-1][col]:
                board[row][col] = board[row][col]*2
                board[row-1][col] = 0
                joinable[row][col] = False


def move_east(board):
    queue = collections.deque()
    joinable = [[True for _ in range(n)] for _ in range(n)]
    for row in range(n):
        for col in reversed(range(0, n)):
            if board[row][col] != 0:
                queue.append([row, col])  # board[row][col][1] = True
            else:  # 값이 0이면 땡겨오고나서 큐에 추가
                for sub_col in reversed(range(0, col)):
                    if board[row][sub_col] != 0:
                        board[row][col] = board[row][sub_col]
                        board[row][sub_col] = 0
                        queue.append([row, col])
                        break

    while queue:
        row, col = queue.popleft()
        if 0 <= col-1 < n:
            if board[row][col] == 0 and board[row][col-1] != 0:  # 처음에는 0이 아니었지만 합쳐지면서 0이 된 경우
                board[row][col] = board[row][col-1]
                board[row][col-1] = 0
                joinable[row][col] = joinable[row][col-1]
                joinable[row][col-1] = True
                queue.append([row, col])
            elif board[row][col] == board[row][col-1]:
                board[row][col] = board[row][col]*2
                board[row][col-1] = 0
                joinable[row][col] = False
                joinable[row][col-1] = True


def move_west(board):
    queue = collections.deque()
    joinable = [[True for _ in range(n)] for _ in range(n)]  # 한 번 합쳐진 블록은 False로 표시

    # 작업할 큐를 만듦
    for row in range(n):
        for col in range(n):
            if board[row][col] != 0:  # 0이 아닌 값만 큐에 추가
                queue.append([row, col])
            else:  # 값이 0이면 0이 아닌 것을 뒤에서 땡겨와서 그 값을 큐에 추가
                for sub_col in range(col+1, n):
                    if board[row][sub_col] != 0:
                        board[row][col] = board[row][sub_col]
                        board[row][sub_col] = 0
                        queue.append([row, col])
                        break

    while queue:
        row, col = queue.popleft()
        if 0 <= col+1 < n:
            if board[row][col] == 0 and board[row][col+1] != 0:  # 처음에는 0이 아니었지만 합쳐지면서 0이 된 경우
                board[row][col] = board[row][col+1]
                board[row][col+1] = 0
                joinable[row][col] = joinable[row][col+1]
                joinable[row][col+1] = True
                if joinable[row][col]:
                    queue.append([row, col])
            elif board[row][col] == board[row][col+1]:
                board[row][col] = board[row][col]*2
                board[row][col+1] = 0
                joinable[row][col] = False
                joinable[row][col+1] = True


###
# 중복 순열에 뽑힌 방향 순서대로 보드를 이동시키는 함수
###
def move(directions):
    global maxValue
    board = deepcopy(board_origin)  # 원본 보드가 변경되면 안되므로 deepcopy 필요

    for way in directions:
        if way == WEST:
            move_west(board)
        elif way == EAST:
            move_east(board)
        elif way == NORTH:
            move_north(board)
        elif way == SOUTH:
            move_south(board)

    # 최댓값 비교
    for line in board:
        maxValue = max(maxValue, max(line))


###
# 동서남북을 중복을 허용하면서 재귀적으로 5가지를 뽑은 후
# count가 5가 되면 그 방향대로 이동을 시작시키는 함수
###
def get_permutation_directions(count, selected):
    if count == 5:
        move(selected)
        return

    for way in [WEST, EAST, NORTH, SOUTH]:
        selected.append(way)
        get_permutation_directions(count+1, selected)
        selected.pop()


if __name__ == '__main__':
    maxValue = 0
    n = int(sys.stdin.readline())

    board_origin = []
    for _ in range(n):
        board_origin.append(list(map(int, sys.stdin.readline().split())))

    get_permutation_directions(0, [])

    print(maxValue)

동적 프로그래밍 하다가 이건 아닌 것 같아서 완전탐색부터 시작.

범위가 1~1000000이었기 때문에 완전탐색이라는 것은 쉽게 알아낼 수 있을 것 같다.

하지만 완전탐색 중에서도 범위를 줄여낼 수 있었던 문제.

enter = int(input())
answer = 0
for i in range(enter-54, enter):
    if i <= 0:
        continue
    tmp = i
    ins = i  # 분해합
    while tmp > 0:
        if tmp < 1:
            ins += tmp
            break
        else:
            ins += tmp % 10
            tmp = tmp // 10
    if ins == enter:
        answer = i
        break

print(answer)