느낌표 공장

Stack 활용하여 푼 코드 t = int(input()) for idx in range(1, t+1): # 노드 개수 v, 간선개수 e v, e = map(int, input().split()) # 인접행렬 만들기 (인덱스 사용 편하게 하기 위해 range(v+1) 해주었음) arr = [[0 for _ in range(v+1)] for _ in range(v+1)] # 인접행렬에 방향성 표시하기 for _ in range(e): # 출발노드 d, 도착 노드 a d, a = map(int, input().split()) arr[d][a] = 1 # 한방향이므로 반대로도 설정해주면 (arr[a][d] == 1) 안됨 # 경로 존재 확인할 출발 노드 s, 도착 노드 g s, g = map(int, inpu..

재귀 방식으로만 푼 코드 # 규칙 (입력 받은 숫자 n) # n-20 * 2 + n - 10 # 맨 처음, 즉 n = 10일때부터 구해나가서, 입력받은 숫자 n까지 도달할때까지 구한다. def paper_use(n): if n == 10: return 1 elif n == 20: return 3 else: return 2 * paper_use(n-20) + paper_use(n-10) t = int(input()) for t in range(1, t+1): n = int(input()) print('#{} {}'.format(t, paper_use(n))) DP 코드 (점화식 이용) # 점화식을 이용하기 위해 n의 크기마다 경우의 수를 저장할 리스트 만들기 # 규칙이 (현재의 수-2) * 2 + (현재의..

# 괄호의 짝을 찾기 위해 딕셔너리 활용 b_dict = {'(':')', '{':'}', '[':']'} t = int(input()) for idx in range(1, t+1): code = input() stack = [] answer = 0 for c in code: # c가 여는 괄호 중 하나라면 stack에 추가 if c in b_dict.keys(): stack.append(c) # c가 닫는 괄호 중 하나라면 elif c in b_dict.values(): # stack이 비어있지 않다면 stack에서 괄호 빼오기 try: pop_b = stack.pop() # 만약 pop한 여는 괄호가 c(현재 닫는 괄호)와 짝이 아니라면 아예 답이 틀린거 -> 중단 if b_dict[pop_b] !=..

def dfs(s): global answer visited[s] = 1 # 현재 노드 방문 처리 for i in arr[s]: if i == 99: # 목표 노드 99까지 도달했으면 answer = 1 answer = 1 if answer: # 이미 목표 노드 도달했으면 재귀 들어가지마 return if not visited[i]: # 목표노드 가는 중이고, 방문한 곳 아니라면 재귀 dfs(i) for idx in range(1, 11): # 테스트 케이스 순서 idx, 순서쌍의 개수 n idx, n = map(int, input().split()) # 순서쌍 리스트 pair_list = list(map(int, input().split())) arr = [[] for _ in range(100)] #..

tc = int(input()) for idx in range(1, tc+1): n = int(input()) # 파스칼 삼각형의 크기 temp = [1] # 첫번째 줄 # 2차원 리스트로 만들지 않고 바로바로 프린트 해주기 위해 # 테스트케이스의 번호와 첫번째 줄을 먼저 프린트해준다. print('#{}'.format(idx)) print(*temp) # 두번째 줄부터 시작하기 때문에 삼각형 크기-1(n-1)까지 반복 for i in range(n-1): stack = [0] + temp + [0] # 맨 처음과 끝에 있는 1은 더할게 없으니 현재의 위 라인의 양 끝에 0을 붙여준다. temp = [] # 해당 라인의 숫자를 저장할 임시 리스트 # 여기서 pop()은 맨 마지막 원소를 뽑는다. # 파스..

Dynamic Progamming? 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 원리 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그 문제를 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 하위 문제의 수가 기하급수적으로 증가할 때 유용하다. 언제 사용할까 ? 최적화 문제 경우의 수 구하기 과정 문제를 부분 문제로 분할한다. 부분 문제로 나누는 일을 끝냈으면 가장 작은 부분 문제부터 해를 구한다. 그 결과는 테이블에 저장하고, 테이블에 저장된 부분 문제의 해를 이용하여 상위 문제의 해를 구한다. ✔︎ Memoizat..

tc = int(input()) # 딕셔너리 for idx in range(1, tc+1): str1 = input() str_cnt = {s:0 for s in str1} str2 = input() for s in str2: if s in str_cnt: str_cnt[s] += 1 print('#{} {}'.format(idx, max(str_cnt.values()))) print(str_cnt)

in 을 이용한 간단한 풀이 코드 tc = int(input()) for idx in range(1, tc+1): str1 = input() str2 = input() str1_l = len(str1) answer = 0 if str1 in str2: answer = 1 print('#{} {}'.format(idx, answer)) 보이어무어 알고리즘을 이용하여 푼 코드 tc = int(input()) for idx in range(1, tc+1): str1 = input() str2 = input() str1_l = len(str1) answer = 0 # 건너뛸 리스트 만들기 str_skip = {str1[i]:str1_l - i -1 for i in range(str1_l)} print(str_s..

def is_palindrome(i, j, k, board): len_board_h = len(board)//2 if len(board) % 2: start = board[:len_board_h] # 구간의 처음 ~ 중간까지의 범위 end = board[:len_board_h:-1] # 중간 ~ 구간의 끝 까지의 범위 (비교할 수 있도록 반대로 슬라이싱하였다.) # [구간의 끝 : 중간 : -1] # 회문의 길이가 홀수일 떄 else: start = board[:len_board_h] # 구간의 처음 ~ 중간 글자 이전 end = board[:len_board_h-1:-1] # 중간글자 다음부터 ~ 구간의 끝 # 비교한 두 범위가 같다면 정답을 반환한다. if start == end: return boa..

처음 풀이 (search 함수 인덱싱이 조금 복잡해 보인다.) # 문자열 같은지 같지 않은지 비교 def search(i, j, board): # 회문의 길이가 홀수일 때랑 짝수일 때 슬라이싱의 범위가 다르므로 조건문 설정 # 회문의 길이가 짝수일 때 if m % 2: start = board[i][j:m_half + j] # 구간의 처음 ~ 중간까지의 범위 end = board[i][m + j:m_half + j:-1] # 중간 ~ 구간의 끝 까지의 범위 (비교할 수 있도록 반대로 슬라이싱하였다.) # [구간의 끝 : 중간 : -1] # 회문의 길이가 홀수일 떄 else: start = board[i][j:m_half + j] # 구간의 처음 ~ 중간 글자 이전 end = board[i][m + j:m..