나만의 개발블로그

풀이 분명 정말 전까지 많이 풀었던 그래프 탐색 문제인데 로직은 이해가 가는데 기존 풀었던 로직과의 차이점으로 조금 걸렸다. 이유는 기존 로직은 해당 스팟에서부터 q에 요소가 없을 때까지 돌리는 문제인데 해당 문제는 모든 스팟 즉, 각 상어 위치로부터 점차 확장해 나가며 최대 허용거리를 측정하는 것이기에 모든 위치를 q에 넣은 다음 bfs로 풀어야 해결이 되는 문제였기에 오래걸렸다... import sys from collections import deque input = sys.stdin.readline n,m = map(int,input().split()) mtx = [list(map(int,input().rstrip('\n').split())) for _ in range(n)] q = deque([..

풀이 범위를 슬라이싱을 통해 역순까지 추가해준 다음 풀이 이후 해당 범위를 위해 start에 누적합을 적용 해당 범위안에 k의 값이 적용된다면 i가 n-1보다 클 경우엔 2*n-i로 작더가 같다면 i+1을 출력하여 해결 import sys input = sys.stdin.readline n,k = map(int,input().split()) li = list(map(int,input().rstrip('\n').split())) li = li+ li[::-1] start = 0 for i in range(2*n): if start

풀이 현재 위치에서 나이트가 갈 수 있는 방향대로 이동하여 이동 가능할 경우 해당 위치의 좌표와 이동 횟수를 함께 q에 넣으며, 방문 표시를 통해 재방문하지 않도록 하기! 그리고 check를 통해 초기 셋팅했던 상대편 말을 만났을 때 1 증가 시키며, 결국 m과 같을 경우 완전한 종료를 하도록 만듦 이후 상대편 말의 위치에 대한 이동 수를 출력하여 해결. import sys from collections import deque input = sys.stdin.readline n,m = map(int,input().split()) mtx = [[0]*n for _ in range(n)] visit = [[0]*n for _ in range(n)] x,y = map(int,input().split()) re..

풀이 예전 괄호 문제와 유사한 문제로 스택에 값을 넣으면서 스택의 마지막 값과 같은 또는 짝지어진 값의 경우 제거하여 해결 import sys input = sys.stdin.readline result = 0 for i in range(int(input())): val = input().rstrip('\n') stack = [] for j in range(len(val)): if len(stack) and stack[-1] == val[j]: stack.pop() else: stack.append(val[j]) if stack == []: result += 1 print(result)

풀이 뭔가 2중 for문을 사용해야할 것 같았는데 시간초과가 안날까? 생각했지만 2초라서 여유있게 통과 되었다. 그래서 해당 인덱스의 li 값보다 작을 경우 해당 인덱스의 dp값과 이전 인덱스 dp값 중 큰 값을 현재 dp에 넣고 안쪽 for문이 종료시 현재 dp에 +1 해줘 문제 해결 import sys input = sys.stdin.readline n = int(input()) li = list(map(int,input().rstrip('\n').split())) dp = [0]*n dp[0] = 1 for i in range(1,n): for j in range(i): if li[j]

풀이 예시를 확인해 보니 조합을 사용하면 될 것 같았고 같은 개수에서 같은 값이 나올 경우 여러번 출력하지 않는다는 것을 확인하여 set을 활용해 중복을 제거 후 오름 차순 정렬을 위해 sorted 메서드를 사용하여 해결 import sys from itertools import combinations input = sys.stdin.readline n,m = map(int,input().split()) li = sorted(list(map(int,input().rstrip('\n').split()))) for i in sorted(list(set(combinations(li,m)))): print(*i)

풀이 set 안에 있는 요소를 in 으로 찾을 경우 hash 값으로 찾다보니 빠르게 찾을 수 있다는 말을 들었어서 적용해보니 간단하게 문제를 해결할 수 있었다. import sys input = sys.stdin.readline for i in range(int(input())): n,note1 = int(input()),set(map(int,input().rstrip('\n').split())) m,note2 = int(input()),list(map(int,input().rstrip('\n').split())) for i in note2: if i in note1: print(1) else: print(0)

풀이 처음엔 문제를 이해하지 못하고 각 지역이 어디지 싶었는데 문제중 "1번부터 N번까지 번호가 매겨져 있는 도시들이 있고" 라는 문장을 보고 알게 되었다... 무튼 해당 문제는 정해져 있는 도시의 수가 아닌 N개의 도시의 수이기에 반복문으로 계속 탐색하는 건 무리가 있다고 판단해 재귀를 사용해 백트래킹 하여 문제를 해결하고자 했으며 그래서 열에 관련한 visit2와 행에 관련한 visit에 방문 체크를 통해 문제 해결 여기서 조건문인 val > result: return 의 가지치기를 활용해 시간 단축을 했다. import sys input = sys.stdin.readline def find(cnt,val,before): global result if cnt == n and result > val: ..

풀이 초기 생각한 방법은 초기 값 확인 이후 사이 값에 대한 조건을 추가해 확인했지만 역시 고려해야할 조건들이 생각보다 더 있어서 정규식을 생각 후 풀었는데 보통 GPT한테 이렇게 정규식 작성해줘로만 했지 직접 작성한적은 별로 없었어서 하나씩 적용하며 해봤는데 진짜 유용한 것 같다! 우선 import re를 사용해 정규표현식을 사용할 수 있다. 이후 pattern을 확인해보자면 [A-F]? [A-F]는 "A와 F 중" 을 의미하며 ? 는 있거나 없거나를 의미 A+ A가 최소 하나 이상 반복을 의미 이후 F와 C 를 확인 할 수 있음. $ 문자의 종료를 의미하여 이후 뒤에는 아무것도 없다를 선언해야 AFCP

풀이 초기 생각한 방법은 아래 두 번째 코드처럼 각 위치에서 슬라이싱한 값 까지의 합 중 가장 큰 값을 출력하고자 했지만 2% 에서 시간 초과 발생 그래서 dp를 활용한 문제 해결을 위해 현재 위치 전까지의 가장 큰 값(이전 dp값) + 현재 위치의 배열 값과 현재 배열의 값 중 큰 값을 현재 dp의 값에 저장하여 최종적으로 가장 큰 값을 출력하여 해결! 정답 코드 import sys input = sys.stdin.readline n = int(input()) li = list(map(int,input().rstrip('\n').split())) dp = [0]*n dp[0] = li[0] for i in range(1,n): dp[i] = max(dp[i-1]+li[i], li[i]) print(ma..