나만의 개발블로그

풀이 뭔가 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..

풀이 처음엔 단순히 같은 값으로 예를 들어 'EE', 'WW'의 경우 카운팅을 해주는 형식으로 했지만 어림도 없었고 이후 'EW'의 경우 카운팅을 해주고자 하니 'WE'의 경우엔 서로 다른 방향으로 가니 컨트롤 하기가 어려워서 고민하다가 그냥 반복문을 돌리면서 visit로 방문 체크를 하며 확인해볼까 해서 풀어보니 해결! import sys from collections import deque input = sys.stdin.readline n = int(input()) li = list(input().rstrip('\n')) visit = [0]*n result = 0 for i in range(n): if not visit[i]: q = deque([i]) visit[i] = 1 while q: s ..

풀이 해당 문제는 백트래킹 문제로 이전에 포스팅한 집합과 순열을 사용하면서 itertools에 있는 메서드를 가지고 온거에 대한 찝찝함으로 백트래킹 문제를 하나 풀고 싶었다..핳 무튼 해당 문제는 단순히 cnt와 x를 1씩 증가 시키는 형식으로 하여 cnt가 m이 될 경우 출력하며, x는 범위를 지정해주는 역할로 사용 그리고 li에 추가한 뒤 함수 실행 이후 return 되는 경우엔 다시 가장 최근 값을 pop 함수로 빼내는 형식으로 백트래킹 문제를 해결 def NM(cnt,x): global n,m if cnt == m: print(*li) return for i in range(x,n+1): li.append(i) NM(cnt+1,i+1) li.pop() return import sys input =..

풀이 처음엔 조합을 활용해서 풀면 되나 싶었지만 예제 1번의 출력 값을 확인 후 조합의 값으로는 6이 나오는데 7이 어떻게 나올 수 있을까 확인하다가 아래로 조금 더 스크롤 해보니 7이 되는 경우를 알려줘서 순열로 푸는 것을 확인할 수 있었다. 그리고 이번 문제는 k 개의 수끼리 순서대로 나열한 값의 중복되지 않는 개수를 출력하는 것이기에 숫자가 아닌 문자로 초기 셋팅을 해줘 더 편하게 해결. from itertools import permutations n,k = int(input()),int(input()) li = [str(input()) for _ in range(n)] result = set() for i in list(permutations(li, k)): val = '' for j in i:..

풀이 델타 탐색 중 아래와 오른쪽으로만 탐색하도록 하며, mtx의 di, dy의 값에 현재 위치 값을 더한 값이 범위 내에 있는지 확인 이후 가장 아래의 가장 오른쪽인 도착 지점에 위치했을 경우 flag를 True로 변경 후 q에 남아있어도 while문 탈출하도록 하기 또한 visit를 활용해서 같은 위치를 재방문하지 않도록 해서 해결 import sys from collections import deque input = sys.stdin.readline n = int(input()) mtx = [list(map(int,input().rstrip('\n').split())) for _ in range(n)] visit = [[0]*n for _ in range(n)] visit[0][0] = 1 q = ..