""" 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/92344 """ # 풀이 과정 """ 조건:행:m 열:n 적군 내구도가 0으로 되면 파괴 아군 내구도를 높임 타입1:적 타입2:아군 특이점:파괴된 건물도 공격받으면 내구도가 더 하락한다! 목표:파괴되지 않은 건물의 개수를 구하시오 생각방향:skill의 조건을 감안하면 skill의 한 번의 루프로 board를 구성하는 방향성에서 생각해보기 중복되는 면적에 대한 생각 사고 누적합 개념 적용여부 및 dp 생각방향 전환 """ def solution(board, skill): # 행 m = len(board) # 열 n = len(board[0]) result = 0 check = [[0] * (n + 1) for _ in range(m + 1)] # sol1: 시간 초과 # team: 아군 enemy: 적 """ for s in skill: ax,ay=s[1],s[2] bx,by=s[3],s[4] c=s[5] # 적 if s[0]==1: for x in range(ax,bx+1): for y in range(ay,by+1): before=board[x][y] board[x][y]-=c after=board[x][y] if before>0 and after<=0: result-=1 # 아군 else: for x in range(ax,bx+1): for y in range(ay,by+1): before=board[x][y] board[x][y]+=c after=board[x][y] if before<=0 and after>0: result+=1 """ # sol2:시간 초과 # for s in skill: # if s[0]==1: # for x in range(s[1],s[3]+1): # for y in range(s[2],s[4]+1): # check[x][y]-=s[5] # else: # for x in range(s[1],s[3]+1): # for y in range(s[2],s[4]+1): # check[x][y]+=s[5] # for i in range(m): # for j in range(n): # board[i][j]+=check[i][j] # if board[i][j]>0: # result+=1 # sol3 for enemy, r1, c1, r2, c2, degree in skill: check[r1][c1] += (-degree) if enemy == 1 else degree check[r2 + 1][c1] += degree if enemy == 1 else -degree check[r1][c2 + 1] += degree if enemy == 1 else -degree check[r2 + 1][c2 + 1] += (-degree) if enemy == 1 else degree # print(check) # 누적합 행 for i in range(len(check)): for j in range(len(check[0]) - 1): check[i][j + 1] += check[i][j] # print(check) # 누적합 열 for j in range(len(check[0])): for i in range(len(check) - 1): check[i + 1][j] += check[i][j] # print(check) for v in range(m): for w in range(n): board[v][w] += check[v][w] if board[v][w] > 0: result += 1 return result

""" 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/118668 """ # 풀이 과정 # 알고력: 0이상의 정수 코딩력: 0이상의 정수 # 조건: 알고력, 코딩력, 알고력 증가량, 코딩력 증가량, 걸리는 시간 # 목표: 모든 문제를 푸는 코딩력,알고력을 얻는 최단 시간 (최단 시간안에 역량 얻기) # 중요포인트:모든 문제 다 안풀어도 됨,같은 문제 여러번 풀기 가능 # 생각 접근 및 방향 변화: 최대로 걸리는 시간을 산정 후 그 시간에 도달하기 전 코딩력 알고력 체크 # 도달해야 될 알고력과 코딩력을 확인 후 최단 시간에 도달하는 방향으로 나아가는 생각 # 완탐 불가능 # 효율1 알고력 효율2 코딩력을 기준으로 가장 효율이 좋은 것을 넣는 방식 고민 # 시간 대비 효율 # 시간 효율로 dp 구성 가능한지 여부(반복되는 문제를 통해 답을 찾는 과정이라 생각이 들기 때문이다.) # 요구력에 제일 근사한 값이 두 개 나올 시 dp에 넣을지 생각 # 효율이 떨어져도 검증해야될 필요성 느낌: 문제 푸는데 최소한의 역량 확보와 효율과 차이가 날 수 있음 import heapq def solution(alp, cop, problems): # 목표 역량 algorism, coding = 0, 0 for a, c, algo, code, time in problems: algorism = max(a, algorism) coding = max(c, coding) # dp를 활용하기 위한 최대 시간 계산 if alp >= algorism: plus_alp = 0 else: plus_alp = algorism - alp if cop >= coding: plus_cop = 0 else: plus_cop = coding - cop max_time = plus_alp + plus_cop if max_time == 0: return 0 dp = [[float("inf")] * (plus_cop + 1) for _ in range(plus_alp + 1)] q = [[alp, cop, 0]] check = 0 while q: al, co, t = q.pop() for a, c, alco, code, time in problems: if al >= a and co >= c and (t + time) <= max_time: if al + alco >= algorism and co + code >= coding: if dp[plus_alp][plus_cop] > (time + t): dp[plus_alp][plus_cop] = time + t elif al + alco >= algorism and co + code < coding: if dp[plus_alp][(co + code) - cop] > (time + t) and time + t < dp[plus_alp][plus_cop]: dp[plus_alp][(co + code) - cop] = time + t q.append([algorism, co + code, time + t]) elif al + alco < algorism and co + code >= coding and time + t < dp[plus_alp][plus_cop]: if dp[(al + alco) - alp][plus_cop] > (time + t): dp[(al + alco) - alp][plus_cop] = time + t q.append([al + alco, coding, time + t]) elif al + alco < algorism and co + code < coding and time + t < dp[plus_alp][plus_cop]: if dp[(al + alco) - alp][(co + code) - cop] > (time + t): dp[(al + alco) - alp][(co + code) - cop] = time + t q.append([al + alco, co + code, time + t]) if (al + 1) <= algorism and t + 1 < dp[plus_alp][plus_cop]: if co >= coding: if dp[al + 1 - alp][plus_cop] > t + 1: q.append([al + 1, coding, t + 1]) else: if dp[al + 1 - alp][co - cop] > t + 1: dp[al + 1 - alp][co - cop] = t + 1 q.append([al + 1, co, t + 1]) if (co + 1) <= coding and t + 1 < dp[plus_alp][plus_cop]: if al >= algorism: if dp[plus_alp][co + 1 - cop] > t + 1: q.append([algorism, co + 1, t + 1]) else: if dp[al - alp][co + 1 - cop] > t + 1: dp[al - alp][co + 1 - cop] = t + 1 q.append([al, co + 1, t + 1]) return dp[-1][-1]

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12949 """ # 풀이 과정 from collections import deque def solution(arr1, arr2): result = [] new = [] count = 0 while count < len(arr2[0]): check = [] for k in range(len(arr2)): check.append(arr2[k][count]) new.append(check) count += 1 arr1 = deque(arr1) while arr1: check = [] i = arr1.popleft() for j in new: count = 0 for v, w in zip(i, j): count += v * w check.append(count) result.append(check) return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/59404 """ """ 풀이 과정 SELECT ANIMAL_ID,NAME,DATETIME from ANIMAL_INS order by NAME asc,DATETIME desc """

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/77485 """ # 풀이 과정 def solution(rows, columns, queries): import copy from collections import deque result = [] map = [[False for col in range(columns)] for a in range(rows)] count = 1 # 기본 맵 for a in range(rows): for b in range(columns): map[a][b] = count count += 1 # 맵 모양 변경 for c in queries: num_list = [] x_1 = c[0] y_1 = c[1] x_2 = c[2] y_2 = c[3] tmp = map[x_1 - 1][y_1 - 1] # 맨 왼쪽 for g in range(x_1 - 1, x_2 - 1): map[g][y_1 - 1] = map[g + 1][y_1 - 1] num_list.append(map[g][y_1 - 1]) # num_list.append("first") # 맨 아랫줄 ok for f in range(y_1 - 1, y_2 - 1): map[x_2 - 1][f] = map[x_2 - 1][f + 1] num_list.append(map[x_2 - 1][f]) # num_list.append("second") # 맨 오른쪽 ok for e in range(x_2 - 1, x_1 - 1, -1): map[e][y_2 - 1] = map[e - 1][y_2 - 1] num_list.append(map[e][y_2 - 1]) # num_list.append("third") # 맨 윗줄 ok for d in range(y_2 - 1, y_1, -1): map[x_1 - 1][d] = map[x_1 - 1][d - 1] num_list.append(map[x_1 - 1][d]) # print(num_list) map[x_1 - 1][y_1] = tmp num_list.append(map[x_1 - 1][y_1]) result.append(min(num_list)) # num_list.append("fourth") # print(num_list) return result

""" 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/131129 """ # 풀이 과정 # 점수를 깎아서 0점으로 만듬 단, 남은 점수보다 큰 점수로 득점하면 버스트 후 실격 # 조건: # 싱글: 해당 점수 더블:해당 점수 2배 트리플: 해당 점수 3배 # 불, 아우터 불: 50점 # 승리 조건: 더 빨리 0점 만든 선수(같은 라운드의 경우 그 중 싱글 또는 불을 더 많이 던진 선수) # 빨리 0점을 만들면서 싱글 또는 불을 최대한 많이 던지는 방법 # 목표:[다트 던진 횟수,싱글 횟수+불 횟수] # 생각방향: 무조건 1번에 끝나지 않는 경우 불과 싱글과 함께된 조합으로 동일한 횟수로 해결 가능할 경우 그 경우의 수 조합 생각 # 불과 싱글인 수로 뺀 것 그렇지 않은 경우 두 가지 밖에 없다 # 기본 전제 생각 조건: 가장 빨리 끝나는 라운드에서 싱글과 불이 제일 많아야한다 # dfs로 생각 후 접근 방향 생각! > 시간초과 # 같은 수들로 끊임없이 작게 만들어 원하는 값을 얻는 방식 > dp 접근 # 다트의 수가 차이나는 순간에 대하여 고찰 후 문제를 접근 > 시간 단축 및 정답! import heapq from collections import deque import sys sys.setrecursionlimit(10 ** 6) result = [] def dfs(count, sb, num, s, d): global result for i in range(len(s) - 1, -1, -1): if num - s[i] >= 0: if s[i] in d and num - s[i] == 0: result.append([count + 1, sb + 1]) elif not s[i] in d and num - s[i] == 0: result.append([count + 1, sb]) elif s[i] in d and num - s[i] > 0: if len(result) > 0: if count + 1 >= result[0][0]: break dfs(count + 1, sb + 1, num - s[i], s, d) break elif not s[i] in d and num - s[i] > 0: if len(result) > 0: if count + 1 >= result[0][0]: break dfs(count + 1, sb, num - s[i], s, d) return result def solution(target): t = target global result # 다트판 (싱글 가능판) d = [k + 1 for k in range(20)] # 점수 얻을 수 있는 판 s = [] for i in d: s.append(i) s.append(i * 2) s.append(i * 3) s.append(50) s = list(set(s)) d.append(50) s.sort() count, sb, num = 0, 0, t if t > 300: count += (t - 300) // 60 num = 300 + (t - 300) % 60 dfs(count, sb, num, s, d) result = sorted(result, key=lambda x: (x[0], -x[1])) return result[0]

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/131127 """ # 풀이 과정 def solution(want, number, discount): from collections import deque discount = deque(discount) result = 0 check = {} for k in range(len(want)): check[want[k]] = number[k] result_check = check.copy() check_2 = deque([]) while discount: t = discount.pop() check_2.append(t) if len(check_2) >= 10: flag = False for l in check_2: if l in result_check: if result_check[l] > 0: result_check[l] -= 1 if result_check[l] == 0: del result_check[l] if len(result_check) == 0: result += 1 check_2.popleft() result_check = check.copy() flag = True break if flag == False: check_2.popleft() result_check = check.copy() return result

""" 출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/72415 """ # 풀이 과정 """ 조작횟수: enter+방향키 목표:남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값 생각방향: 카드를 하나 고르면 무조건 그 짝을 무조건 찾아야한다 그 다음 카드를 선택하는 기준은? 배열 자체가 작기 때문에 크기가 중요하진 않다 모든 경우의 수 고려가능 칸 16개이기 떄문에 카드 종류 최대 8개 뽑을 순서의 카드를 미리 정한 후 그 순서에 맞춰서 뽑은 후 순서 정하기 # 시간적으로 코드가 문제가 없으므로 논리의 틀린 부분이 없기에 수정 후 풀이가능 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다. < 중요한 생각의 포인트 기점 """ import copy from itertools import combinations from itertools import permutations from collections import defaultdict from collections import deque # 두 점 사이의 이동 (현재 위치, 이동할 위치, 이동 횟수, 해당 게임판) def start(now_x, now_y, nex_x, nex_y, fir): """ if now_x==nex_x and now_y==nex_y: return 0 queue, visit = deque([[now_x, now_y, 0]]), {(now_x,now_y)} while queue: # BFS x, y, c = queue.popleft() for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]: nx, ny = x+dx, y+dy # Normal move cx, cy = x, y while True: # Ctrl + move cx, cy = cx+dx, cy+dy if not (0 <= cx <= 3 and 0 <= cy <= 3): cx, cy = cx-dx, cy-dy break elif fir[cx][cy] != 0: break if (nx, ny) == (nex_x,nex_y) or (cx, cy) == (nex_x,nex_y): # 도착 최단 경로 return c+1 if (0 <= nx <= 3 and 0 <= ny <= 3) and (nx, ny) not in visit: queue.append((nx, ny, c+1)) visit.add((nx, ny)) if (cx, cy) not in visit: queue.append((cx, cy, c+1)) visit.add((cx, cy)) """ q = deque([[now_x, now_y, count]]) num = float("inf") dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] visit = set([]) q = deque([(now_x, now_y, 0)]) while q: i, j, c = q.popleft() # 방문 기록 visit = visit | set([(i, j)]) if i == nex_x and j == nex_y: return c for nx, ny in zip(dx, dy): x, y = i, j if 0 <= x + nx < 4 and 0 <= y + ny < 4: if not (x + nx, y + ny) in visit: q.append((x + nx, y + ny, c + 1)) visit = visit | set([(x + nx, y + ny)]) ctrlx, ctrly = i, j while True: ctrlx += nx ctrly += ny if not 0 < ctrlx < 4 or not 0 < ctrly < 4: if nx == 1: if not (3, ctrly) in visit: q.append((3, ctrly, c + 1)) visit = visit | set([(3, ctrly)]) elif nx == -1: if not (0, ctrly) in visit: q.append((0, ctrly, c + 1)) visit = visit | set([(0, ctrly)]) elif ny == 1: if not (ctrlx, 3) in visit: q.append((ctrlx, 3, c + 1)) visit = visit | set([(ctrlx, 3)]) elif ny == -1: if not (ctrlx, 0) in visit: q.append((ctrlx, 0, c + 1)) visit = visit | set([(ctrlx, 0)]) break elif fir[ctrlx][ctrly] == 1: if not (ctrlx, ctrly) in visit: q.append((ctrlx, ctrly, c + 1)) visit = visit | set([(ctrlx, ctrly)]) break return 0 # k:카드 뽑는 순서, 게임판, 현 위치, 총 움직인 순서 def count(k, distance): order, game, location, count = k[0], k[1], k[2], k[3] x, y = location[0], location[1] result = float("inf") q = deque([[order, game, [x, y], count]]) while q: new_order, new_game, new_location, new_count = q.popleft() new_x, new_y = new_location[0], new_location[1] new_order = deque(new_order) if len(new_order) == 0: # print(new_count,result) result = min(result, new_count) continue # print(new_order,"before") num = new_order.popleft() # print(new_order,"after") # one > two count_one = new_count # two > one count_two = new_count # 같은 카드는 2개이므로 어느쪽으로 갈지 택해야한다 fir = copy.deepcopy(new_game) # 새로운 게임판1 fir_x, fir_y = distance[num][0] # one 위치 sec = copy.deepcopy(new_game) # 새로운 게임판2 sec_x, sec_y = distance[num][1] # two 위치 # location > one > two one = start(new_x, new_y, fir_x, fir_y, fir) count_one += (one + 1) one = start(fir_x, fir_y, sec_x, sec_y, fir) count_one += (one + 1) # fir 변형 fir[fir_x][fir_y] = 0 fir[sec_x][sec_y] = 0 order_one = copy.deepcopy(new_order) q.append([order_one, fir, [sec_x, sec_y], count_one]) # location > two > one two = start(new_x, new_y, sec_x, sec_y, sec) count_two += (two + 1) two = start(sec_x, sec_y, fir_x, fir_y, sec) count_two += (two + 1) # sec 변형 sec[fir_x][fir_y] = 0 sec[sec_x][sec_y] = 0 order_two = copy.deepcopy(new_order) q.append([order_two, sec, [fir_x, fir_y], count_two]) # if count_one>=count_two: # q.append([order_one,fir,[sec_x,sec_y],count_one]) # else: # q.append([order_two,sec,[fir_x,fir_y],count_two]) return result def solution(board, r, c): result = float("inf") # 카드 위치 distance = defaultdict(list) # 현재 위치 d = [r, c] # 카드 종류 card = [] for i in range(4): for j in range(4): if board[i][j] != 0: card.append(board[i][j]) card = list(set(card)) for i in card: for v in range(4): for w in range(4): if board[v][w] == i: distance[i].append([v, w]) turn = list(permutations(card, len(card))) turn = list(map(list, turn)) # print("turn",turn) q = [] # 카드 뽑는 순서,게임판,현 위치, 총 움직인순서 for i in turn: new = copy.deepcopy(board) q.append([i, new, [r, c], 0]) while q: k = q.pop() check = count(k, distance) result = min(check, result) return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12945 """ # 풀이 과정 def solution(n): count = 2 func_1 = 1 func_0 = 0 while count <= n: count += 1 func_2 = func_1 + func_0 result = func_2 func_1, func_0 = func_2, func_1 return result % 1234567

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/17676 """ # 풀이 과정 # 누적합 from collections import defaultdict Data = [0] * 24 * 60 * 60 * 1000 # for s in range(24*60*60): # Data[s]=0 def time_to_sec(x, y): global Data t = x.split(":") hour, minu, sec = int(t[0]), int(t[1]), float(t[2]) end_time = (int(hour) * 60 * 60 + int(minu) * 60 + sec) * 1000 blank = list(y) blank.pop() y = "".join(blank) # 시작 시간, 끝 시간 start = end_time - float(y) * 1000 + 1 start = max(0, start) end_time = min(24 * 60 * 60 * 1000 - 1, end_time + 999) start, end = int(start), int(end_time) for tra in range(start, end + 1): Data[tra] += 1 return 0 def solution(lines): global Data for l in lines: d = l.split(" ") time = time_to_sec(d[1], d[2]) result = 0 count = 0 result = max(Data) return result