Coding 공부

import sys
 
input = sys.stdin.readline
 
def combination(ind,len_string,combi):
    if ind == len_string:
        print(combi)
    else:
        for k in range(len_string):
            if visited[k]:
                temp = combi+string_list[k]
                if temp not in record:
                    visited[k] = False
                    record.add(temp)
                    combination(ind+1,len_string,temp)
                    visited[k] = True 
 
 
 
N = int(input())
 
for _ in range(N):
    string_list = list(input().strip())
    string_list.sort()
    len_string = len(string_list)
    visited = [True]*(len(string_list))
    record = set()
    combination(0,len_string,'')

import copy
def find_position(pools,num):
    for x in range(4):
        for y in range(4):
            if pools[x][y][0] == num:
                return (x,y)
    return False
def move_fish(pools,shark_x,shark_y):
    for fish_num in range(1,17):
        position = find_position(pools,fish_num)
        if position:
            x,y = position
            fish_dire = pools[x][y][1]
 
            for _ in range(8):
                nx = x + dx[fish_dire]
                ny = y + dy[fish_dire]
                if 0<=nx<4 and 0<=ny<4:
                    if not (nx == shark_x and ny == shark_y):
                        pools[x][y][0],pools[nx][ny][0] = pools[nx][ny][0],pools[x][y][0]
                        pools[x][y][1],pools[nx][ny][1] = pools[nx][ny][1],fish_dire
                        break
                fish_dire = (fish_dire+1)%8
 
 
def eating(x,y,pools):
    temp = []
    shark_dire = pools[x][y][1]
    for _ in range(3):
        nx = x + dx[shark_dire]
        ny = y + dy[shark_dire]
        if 0<=nx<4 and 0<=ny<4 and pools[nx][ny][0]>0:
            temp.append((nx,ny))
        x,y = nx,ny
    return temp
 
 
def solution(pools,shark_x,shark_y,cnt):
    global answer
    pools2 = [[col[:] for col in row]      for row in pools]
    eat_fish_size = pools2[shark_x][shark_y][0]
    pools2[shark_x][shark_y][0] = -1
    move_fish(pools2,shark_x,shark_y)
    find_fish = eating(shark_x,shark_y,pools2)
    answer = max(answer,eat_fish_size+cnt)
 
    for x,y in find_fish:
        solution(pools2,x,y,cnt+eat_fish_size)
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
 
pools = []
for x in range(4):
    arr = list(map(int,input().split()))
    temp = []
    for y in range(4):
        fish_number,dire = arr[2*y],arr[2*y+1]
        temp.append([fish_number,dire-1])
    pools.append(temp)
answer = 0
 
solution(pools,0,0,0)
print(answer)

def dfs(x,y,cnt):
    global result
    if cnt > result:
        return
    if x >= 10:
        result = min(result,cnt)
        return
    if y >= 10:
        dfs(x+1,0,cnt)
        return
    if arr[x][y] == 1:
        for paper_size in range(5,0,-1):
            if paper[paper_size]:
                if x + paper_size <= 10 and y + paper_size <= 10:
                    flag = False
                    for dx in range(paper_size):
                        for dy in range(paper_size):
                            if not arr[x+dx][y+dy]:
                                flag = True
                                break
                        if flag:
                            break
                    if not flag:
                        for dx in range(paper_size):
                            for dy in range(paper_size):
                                arr[x+dx][y+dy] = 0
                        paper[paper_size] -= 1
                        dfs(x,y+paper_size-1,cnt+1)
                        paper[paper_size] += 1
                        for dx in range(paper_size):
                            for dy in range(paper_size):
                                arr[x+dx][y+dy] = 1
    else:
        dfs(x,y+1,cnt)
 
        
 
 
arr = [list(map(int,input().split())) for _ in range(10)]
paper = [0]+[5]*5
result = float('inf')
dfs(0,0,0)
print(result if result != float('inf') else -1)

def check(x,y,size):
    if x + size > 10 or y + size >10:
        return False
    for dx in range(size):
        for dy in range(size):
            if not arr[x+dx][y+dy]:
                return False
    return True
 
 
def set_position(x,y,size,val):
    for dx in range(size):
        for dy in range(size):
            arr[x+dx][y+dy] = val
def dfs(x,y,cnt):
    global result
    if cnt >= result:
        return
    finish = True
    while x < 10:
        while y < 10:
            if arr[x][y] == 1:
                finish = False
                for paper_size in range(5,0,-1):
                    if paper[paper_size] and check(x,y,paper_size):
                        set_position(x,y,paper_size,0)
                        paper[paper_size] -= 1
                        dfs(x,y+paper_size-1,cnt+1)
                        paper[paper_size] += 1
                        set_position(x,y,paper_size,1)
                return
            y += 1
        x += 1
        y = 0
    if finish:
        result = min(result,cnt)
        
 
 
arr = [list(map(int,input().split())) for _ in range(10)]
paper = [0]+[5]*5
result = float('inf')
dfs(0,0,0)
print(result if result != float('inf') else -1)

def founded(cnt):
    global result
    if cnt == 15:
        if sum(list(map(sum,win_draw_defeat))) == 0:
            result = 1
            return
    else:
        origin_number = origin_team[cnt]
        next_number = next_team[cnt]
        for idx in range(3):
            origin_team_score = idx
            next_team_score = 2-idx
            if win_draw_defeat[origin_number][origin_team_score] > 0 and win_draw_defeat[next_number][next_team_score]:
                win_draw_defeat[origin_number][origin_team_score] -= 1
                win_draw_defeat[next_number][next_team_score] -= 1
                founded(cnt+1)
                win_draw_defeat[origin_number][origin_team_score] += 1
                win_draw_defeat[next_number][next_team_score] += 1
 
 
from collections import deque
origin_team = [0,0,0,0,0,1,1,1,1,2,2,2,3,3,4]
next_team = [1,2,3,4,5,2,3,4,5,3,4,5,4,5,5]
answer = []
for _ in range(4):
    score = deque(map(int,input().split()))
    win_draw_defeat = []
    result = 0
    for _ in range(6):
        temp = []
        for _ in range(3):
            temp.append(score.popleft())
        win_draw_defeat.append(temp)
    founded(0)
    answer.append(result)
print(*answer)

def check(cnt,total,di):
    global result
    if cnt == arr[0]:
        temp = 1
        for k in di:
            temp *= arr[dire.index(k)+1]/100
        result += temp
        return
    else:
        cu_x,cu_y = total[-1]
        for i in range(4):
            nx = cu_x + dx[i]
            ny = cu_y + dy[i]
            if (nx,ny) not in total:
                check(cnt+1,total+[(nx,ny)],di+[dire[i]])
    
 
 
# 동 서 남 북
dx = [0,0,1,-1]
dy = [1,-1,0,0]
dire = ['E','W','S','N']
arr = list(map(int,input().split()))
result = 0
check(0,[(0,0)],[])
print(ccnt)

def dfs(x,y,persent,cnt):
    global revers_persen,N,total
    if arr[x][y] == 1:
        revers_persen += persent
        return
    if cnt == N:
        return
    arr[x][y] = 1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if persentlist[i]:
            dfs(nx,ny,persent*persentlist[i],cnt+1)
    arr[x][y] = 0
 
 
 
N,e,w,s,n = map(int,input().split())
 
e,w,s,n = e/100,w/100,s/100,n/100
dx = [0,0,1,-1]
dy = [1,-1,0,0]
persentlist = [e,w,s,n]
arr = [[0]*29 for _ in range(29)]
 
revers_persen = 0
dfs(14,14,1,0)
print(f'{1-revers_persen:.10f}')

from itertools import combinations
 
N,K = map(int,input().split())
ord_dict = {}
if K <5:
    print(0)
    exit()
elif K == 26:
    print(N)
    exit()
else:
    # 2**승으로 만들어 주기 위한 곳
    for k in range(26):
        ord_dict[chr(k+97)] = k
 
    K = K - 5
    comb_bits = 0
    # 무조건 있는 애들을 기본적으로 comb_bits로 만들어준다.
    for k in ['a','n','t','i','c']:
        comb_bits = comb_bits + 2**ord_dict[k]
    word_list = []
 
 
    for _ in range(N):
        # 앞뒤 고정 부분은 필요없으니 자른다.
        temp = set(list(input())[4:-4])
        word_list.append(temp)
    # 고정적으로 잇는 부분 제외하고 나머지를 뽑는다.
    combi_word = set(ord_dict.keys()) - set(['a','n','t','i','c'])
    result = 0
    for pick_words in combinations(combi_word,K):
        check_bits = comb_bits
        for pick_word in pick_words:
            # OR 연산을 해줘서 BIT 형식으로 만들어준다.
            check_bits = check_bits | 1<< ord_dict[pick_word]
 
        word_cnt = 0
        for word in word_list:
            for wo in word:
                # 만약에 AND 연산을 했는데 False가 나오면 그만둔다.
                if not (check_bits & 1<<ord_dict[wo]):
                    break
            else:
                word_cnt += 1
        result = max(word_cnt,result)
                
    print(result)

어렵지 않은 문제인데 python을 이용해서 풀려면 참 난감해진 문제였다. 조합을 잘 짜면, 시간을 넘지않을수도 있지만, 

시간초과에 걸리는 경우가 많았다.

그래서 조합을 구하는 방식을 비트마스킹을 통해 만들었따. 2**(k)승의 형태로 만들어주고, and 연산을 해서 우리가 만든 조합에 포함되어있는지 아닌지 확인하는 방식이다.

from itertools import combinations
 
N,K = map(int,input().split())
ord_dict = {}
 
for k in range(26):
    ord_dict[chr(k+97)] = k
 
K = K - 5
if K <0:
    print(0)
    exit(0)
else:
    origin_word = set(['a','n','t','i','c'])
    word_bit_list = list()
    combination_word = set()
    answer = 0
    for _ in range(N):
        temp = set(list(input())[4:-4]) - origin_word
        if len(temp) == 0:
            answer += 1
        elif len(temp) <=K:
            word_bit = 0
            for w in temp:
                word_bit = word_bit + 2**ord_dict[w]
            word_bit_list.append(word_bit)
            combination_word |= temp
 
    word_lens = len(combination_word)
    if K > word_lens:
        K = word_lens
    chk_cnt = 0
    for pick_words in combinations(combination_word,K):
        cnt = 0
        temp = 0
        for pick_word in pick_words:
            temp = temp + 2**ord_dict[pick_word]
        for word_bit in word_bit_list:
            if word_bit & temp == word_bit:
                cnt += 1
 
        chk_cnt = max(chk_cnt,cnt)
 
    print(answer + chk_cnt)

위의 방식보다 훨씬 빠른 방식이다. 이 방식은 기본적인 컨셉은 비슷하다.

하지만 2가지가 다르다.

첫번째는 전체 알파벳 26개중에서 K개를 뽑던거에서 고정적으로 들어간 a,c,i,n,t를 무조건 뽑는다고 생각하고,

그리고 주어진 단어들에 있는 단어들 중에서 나머지 K-5개를 뽑는것이다.

두번째는 각 단어들의 BIT를 비교했던것에서 단어 전체의 bit를 저장해준뒤, 우리가 만든 combination bit와 and 연산을해서, 원래 word_bit가 유지되는지 확인을 해주는 방식이다.

이러한 방법을 통해 시간을 줄일 수 있다.

import sys
input = sys.stdin.readline
 
def check_sdouk(x,y):
    index_set = set(range(1,10))
    occupy_set = set()
    for checky in range(9):
        if sdoku[x][checky]:
            occupy_set.add(sdoku[x][checky])
    for checkx in range(9):
        if sdoku[checkx][y]:
            occupy_set.add(sdoku[checkx][y])
    squarex = x//3*3
    squarey = y//3*3
    for checkx in range(squarex,squarex+3):
        for checky in range(squarey,squarey+3):
            if sdoku[checkx][checky]:
                occupy_set.add(sdoku[checkx][checky])
    return index_set-occupy_set
 
 
 
def sdoku_input(cnt):
    global check_max,result
    if cnt == check_max:
        result = [row[:] for row in sdoku]
        for row in result:
            print(*row)
        sys.exit()
        return
    else:
        a = check_sdouk(*check_list[cnt])
        if a:
            for number in a:
                sdoku[check_list[cnt][0]][check_list[cnt][1]] = number
                sdoku_input(cnt+1)
                sdoku[check_list[cnt][0]][check_list[cnt][1]] = 0
        else:
            return
 
 
 
 
sdoku = []
check_list = []
for x in range(9):
    input_list = list(map(int,input().split()))
 
    for y in range(9):
        if not input_list[y]:
            check_list.append((x,y))
    sdoku.append(input_list)
result = []
check_max = len(check_list)
sdoku_input(0)

재귀를 이용해서 풀었다.

sys.exit()를 통해 최초의 결과가 나오면 바로 나오게 해줬다.

import sys
input = sys.stdin.readline
 
 
 
def check(cnt):
    if cnt == len(check_list):
        for row in sdoku:
            print(*row)
        sys.exit()
    else:
        x,y = check_list[cnt]
        square_ind = x//3*3 + y//3
        for number in range(1,10):
            if row_index[x][number] + col_index[y][number] + square_index[square_ind][number] == 0:
                row_index[x][number] = 1
                col_index[y][number] = 1
                square_index[square_ind][number] = 1
                sdoku[x][y] = number
                check(cnt+1)
                row_index[x][number] = 0
                col_index[y][number] = 0
                square_index[square_ind][number] = 0
                sdoku[x][y] = 0
 
 
row_index = [[0]*10 for _ in range(9)]
col_index = [[0]*10 for _ in range(9)]
square_index = [[0]*10 for _ in range(9)]
 
 
sdoku = []
check_list = []
for x in range(9):
    input_list = list(map(int,input().split()))
 
    for y in range(9):
        if input_list[y]:
            row_index[x][input_list[y]] = 1
            col_index[y][input_list[y]] = 1
            square_ind = x//3*3 + y//3
            square_index[square_ind][input_list[y]] = 1
        else:
            check_list.append((x,y))
    sdoku.append(input_list)
 
 
check(0)

  위는 시간이 오래걸려서 개선된 버전이다. 이 방법은 col,row,square 마다 1~9까지의 list를 만들어놓고 거기서 바로 판단이 가능하게 바꿨다.

# 1759 암호 만들기
def check(input_val,vowel):
    
    check_list = [0,0]
    for val in input_val:
        if val in vowel:
            check_list[0] += 1
        else:
            check_list[1] += 1
 
    if check_list[0] >= 1 and check_list[1] >= 2:
        return True
    else:
        return False 
 
 
 
 
def dfs(cnt,ind,result):
    global vowel
    if ind == C:
        if cnt == L and check(result,vowel):
            total.append(result)
            return
    else:
        dfs(cnt+1,ind+1,result+input_list[ind])
        dfs(cnt,ind+1,result)
 
 
 
 
L,C = map(int,input().split())
vowel = 'aeiou'
input_list = list(input().split())
input_list.sort()
 
total = list()
dfs(0,0,'')
for val in total:
    print(val)

재귀를 이용해서 조합을 만들어준 것과 같다. 각 인덱스에 들어와서, 해당 문자를 포함하거나 포함하지 않는 경우를 구분해서 재귀를 돌려주었다.

그리고 주어진 길이만큼 되면, 그 안에 모음과 자음 숫자에 따라 True False를 반환해주고, True일때 결과값에 추가해줬다.

from itertools import combinations
 
L,C = map(int,input().split())
 
input_value = list(input().split())
 
input_value.sort()
vowel = set(['a','e','i','o','u'])
for combi in combinations(input_value,L):
    password = set(combi)
    if password & vowel:
        if len(password-vowel)>=2:
            print(''.join(combi)) 

좀 더 간단한 풀이이다. 위에서 말했듯이 이것은 조합을 구하는것과 동일하다.

combinations 라이브러리를 활용해 전체 combinations을 구하고, 집합의 특성을 이용해, 교집합이 존재하는지, 차집합을 통해 길이가 2이상인지 구분해줘서, 만약 두개다 통과하다면, 원하는 값이므로 출력해주는 방식으로 풀었다.