알고리즘

패션왕 신해빈

import sys input = sys.stdin.readline def BOJ9375() : T = int(input()) for _ in range(T) : n = int(input()) dict = {} for _ in range(n) : _, type = input().split() if type in dict : dict[type] += 1 else : dict[type] = 1 answer = 1 for i in dict.values() : answer *= (i+1) print(answer - 1) BOJ9375() 접근방법 : 1. 옷의 이름은 필요 없다. 입을지 말지 무엇을 입을지만 알고싶다. 2. 타입은 두개 옷의 종류는 각각 3개, 2개라 가정해보자, 아래의 이미지에 표현해두었다. ..

과제 [백준 - 13904] - python

def BOJ13904() : n = int(input()) answer = [0] * 10000 l = [] for _ in range(n) : l.append(list(map(int, input().split()))) l.sort(key= lambda x : (-x[1])) print(l) for i in range(n) : for j in range(l[i][0] -1, -1, -1) : # 그 날부터 거꾸로 가면서 비어있는칸에 넣어버리자!! if answer[j] == 0 : # 마감일보다 전의 날중에 0인 날이 있다면 값을 넣어 주면 됨 answer[j] = l[i][1] break print(sum(answer)) BOJ13904() 접근방법 : 1. 값을 기준으로 정렬을 시켜준다. 2. 마감..

그룹 단어 체커 [백준 - 1316] - python

def BOJ1316() : n = int(input()) count = 0 for _ in range(n) : pointer = '' dict = {} flag = True for k in list(input()) : if pointer != k and k not in dict : pointer = k dict[k] = 1 elif pointer == k and k in dict : continue elif pointer != k and k in dict : flag = False break if flag : count += 1 print(count) BOJ1316() 접근 방법 : 1. 포인터를 하나 추가 하였다. 이 포인터는 이전에 추가되고 있던 문자열 이거나 현재와는 다른 문자열 일수 있다. 2...

색종이 만들기[백준 2630] - python

import sys input = sys.stdin.readline def BOJ2630() : global N global graph global white global blue N = int(input()) graph = [] white = 0 blue = 0 def dfs(x, y, length) : global N global graph global white global blue flag = True for i in range(x, x + length) : for j in range(y, y + length) : if graph[x][y] != graph[i][j] and visited[i][j] == False and flag: flag = False break if flag : for i i..

최소 힙[백준 - 1927] - python

import heapq, sys def BOJ1927() : n = int(sys.stdin.readline()) list = [] for _ in range(n) : command = int(sys.stdin.readline()) if command == 0 : if len(list) == 0 : print(0) else : print(heapq.heappop(list)) else : heapq.heappush(list, command) BOJ1927() 접근 방법 : 1. 배열에 값을 넣고 매번 배열을 정렬할수 없으므로 heap을 사용하자 2. command가 0일때 와 아닐때 0일때는 비어있는지 아닌지만 판단해서 값을 잘 반환해주면 된다 장애물 이였던 것 : 1. 힙의 쓰임새가 익숙치 않았다. ht..

숨바꼭질 4

def BOJ13913(): n, k = map(int, input().split()) graph = [1e9] * 100001 queue = [] graph[n] = 0 queue.append([n, 0]) dict = {n: n} while queue: current_node, current_time = queue.pop(0) next_time = current_time + 1 next_node = current_node - 1 if 0

숨바꼭질 [백준 1697] - python

def BOJ1679(): n, k = map(int, input().split()) graph = [1e9] * 100001 queue = [] graph[n] = 0 queue.append([n, 0]) while queue: current_node, current_time = queue.pop(0) next_node = current_node - 1 if 0

케빈 베이컨의 6단계 법칙

def BOJ1389() : n, m = map(int, input().split()) temp = [[1e9] * n for _ in range(n)] for _ in range(m) : start, end = map(int, input().split()) temp[start-1][end-1] = 1 temp[end-1][start-1] = 1 for mid in range(n) : for start in range(n) : for end in range(n) : if mid != end and temp[start][mid] and temp[mid][end]: temp[start][end] = min(temp[start][end], temp[start][mid] + temp[mid][end]) resu..

가장 큰 증가 부분 수열[백준 11055] - python

import sys input = sys.stdin.readline def BOJ11055() : N = int(input()) array = list(map(int, input().split())) memo = list(array) for index in range(1, len(array)) : max_point = 0 for j in range(index) : if array[j] < array[index] and max_point < memo[j] + array[index] : max_point = memo[j] + array[index] memo[index] = max(memo[index], max_point) print(max(memo)) BOJ11055() 접근 방법 0. 다이나믹 프로그래밍 ..

LCS [백준 9251] - python

def BOJ9251() : first = input() second = input() array = [[0] * (len(second) + 1) for _ in range(len(first) + 1)] for i in range(1, len(first) + 1) : for j in range(1, len(second) + 1) : if first[i-1] == second[j-1] : array[i][j] = array[i-1][j-1] + 1 else : array[i][j] = max(array[i-1][j], array[i][j-1]) print(array[len(first)][len(second)]) BOJ9251() 접근방법 : 1. 이차원 배열로 접근 2. 비교하는 문자열이 같다면 대각선에서..