나의 개발일지

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/60057 🔑 문자열을 자르고 현재, 현재+1을 비교하기 현재, 현재+1 이 같은 동안에는 개수만 증가 다른 문자가 나오면 그동안 누적한 개수 + 문자를 변수에 연결시키기 개수가 1이라면 문자만 변수에 연결 처음에는 1도 같이 연결시키고 마지막에 replace로 1을 없애주었다. 이 경우 10, 11.. 같은 개수가 있을 때 1을 없애버려서 실패, 그래서 조건문에서 걸러주었다. def solution(s): answer = 987654321 for i in range(1, len(s) + 1): slice = [] # n개 단위로 자른 문자열 리스트 compress = "" # 압축한 문자열 ..

문제 : https://www.acmicpc.net/problem/1916 🔑 Dijkstra 알고리즘 import sys from collections import defaultdict from heapq import heappush, heappop input = sys.stdin.readline n = int(input()) # 도시 개수 m = int(input()) # 버스 개수 graph = defaultdict(list) for i in range(m): s, e, c = map(int, input().split()) graph[s].append((c, e)) # 출발지 : [(비용, 도착지)] start, end = map(int, input().split()) INF = int(1e9) c..

문제 : https://www.acmicpc.net/problem/18352 🔑 다익스트라 알고리즘 사용 import sys from collections import defaultdict from heapq import heappush, heappop input = sys.stdin.readline n, m, k, x = map(int, input().split()) # 도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호 graph = defaultdict(list) for i in range(m): key, value = map(int, input().split()) graph[key].append(value) INF = int(1e9) dist = [INF] * (n+1) # 거리 초기화 di..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/81302 🔑 P 일 때 자기 자리와 상하좌우 자리의 값을 -1 하고 최종적으로 -2 이하인 값이 있는 대기실은 거리두기 실패 파티션의 위치는 큰 값을 주고 -2 아래로 내려가는 일을 없게 한다. -2가 있다는 것은 맨해튼 거리 2 내에 사람이 있다는 의미이다. def makeMap(p): # 겹치는 구간 표시 할 5*5 리스트 newMap = [[0] * 5 for _ in range(5)] for i in range(5): for j in range(5): if p[i][j] == 'X': # 파티션은 100으로 지정하자 newMap[i][j] = 100 return newMap def s..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/68645 🔑 직각 삼각형을 만들자 n = 4 [1, 0, 0, 0] [2, 9, 0, 0] [3, 10, 8, 0] [4, 5, 6, 7] 밑으로 쭉, 오른쪽으로 쭉, 왼쪽 위 대각선으로 쭉 반복 def solution(n): answer = [[0] * n for _ in range(n)] x, y = -1, 0 # 시작 위치 i = 1 # 들어갈 값 if n == 1: return [1] for _ in range(n//2): while True: # 밑으로 x += 1 if x >= n or answer[x][y] != 0: x -= 1 break answer[x][y] = i i +=..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/67257 🔑 조합을 구하고, 스택으로 계산, eval() from itertools import permutations def solution(expression): answer = 0 op = [] # 연산자 종류 if '+' in expression: op.append('+') # 무슨 연산자가 쓰였나 찾아보자 if '-' in expression: op.append('-') if '*' in expression: op.append('*') exp = [] st = 0 for i in range(len(expression)): # 문자열로 된 표현식을 리스트로 바꾸자 if expressi..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/60058 🔑 설명 그대로 구현하는 것? 올바른 괄호 검사와 u, v를 나누는 코드는 함수로 따로 빼는 게 보기 편하다. 그리고 설명대로 코드 짜면 되는데 설명 이해하기가 굉장히 어려웠음,, def check(p): # 올바른 괄호일까? if p[0] == ')': return False else: stack = [0] * len(p) k = -1 for i in p: if i == '(': k += 1 stack[k] = '(' elif stack[k] == '(' and i == ')': k -= 1 else: return False return True def make_uv(p): # u..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/64062 🔑 이진 탐색 처음 풀이는 k 크기의 슬라이딩 윈도우로 각 윈도우의 최댓값을 저장하고 그중 최솟값을 반환했다. 정확성은 다 맞지만 효율성이 집에 가라고 했다. 그래서 이진 탐색으로 풀이를 했다. mid 명이 건너면서 연속으로 k개가 부서졌으면 사람 수를 줄였다. 무사히 건널 수 있으면 사람 수를 늘려서 최대로 몇 명이 건널 수 있는지를 구했다. def solution(stones, k): l = 1 r = 200_000_000 while l