Algorithm

💭 나의 접근 방법 증가하는 부분 수열 : 일부 혹은 전체가 오름차순인 수열을 의미한다. 문제를 읽고 다이나믹프로그래밍으로 접근하는구나를 알게 되었고, 시각화하여 점화식을 찾으려고 하였다. list[i-1] < list[i] 를 판단하여 dp[i] = dp[i-1] +1 로 생각하였다. 다만 바로 뒤 인수만 판단하는 것은 전체 인수에서 오름차순을 찾을 수 없는 방법이었다. 따라서 이중 반복분을 이용해서 앞에있는 인수를 모두 확인하는 방법으로 접근한다. 💡 결과 # 11053 가장 긴 증가하는 부분 수열 S2 import sys input = sys.stdin.readline N = int(input()) lst = list(map(int,input().split())) dp = [1]* N for i i..

💭 나의 접근 방법 학생이 X의 마을에 갔다가 돌아오는거까지의 결과에서 가장 오래걸리는 시간을 구하는 문제이다. X를 제외하고 한 학생 당 다익스트라 알고리즘을 2번 실행하게 된다. (N-1 번의 시간) 💡결과 # 1238 파티 G3 import heapq import sys input = sys.stdin.readline N,M,X = map(int,input().split()) INF = int(1e8) result = [0] * (N+1) graph = [[] for _ in range(N+1)] for _ in range(M): a,b,c = map(int,input().split()) graph[a].append((b,c)) def dijkstra(start,end): distance = [IN..

💡 나의 접근 방법 문제를 읽고 다익스트라, 플로이드 와샬 알고리즘으로 푸는 문제임을 알았다. 시간 제한이 0.5 초 이므로 다익스트라 알고리즘으로 풀기로 했다. 💡 결과 # 1916 최소 비용구하기 G5 import heapq import sys input = sys.stdin.readline N = int(input()) M = int(input()) INF = 1e8 graph = [[] for _ in range(N+1)] distance = [INF] * (N+1) for i in range(M): a,b,c = map(int,input().split()) graph[a].append((b,c)) start,end = map(int,input().split()) def dijkstra(start..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 나의 접근 방법 1. "문자열" + x 를 이중 반복문을 통해서 확인한다? -> 최악의 경우 O(n^1) 시간발생 2. 해시로 모든 값을 저장하고 replace() 이용? 3. 정렬을해 길이가 짧은것부터 탐색한다? ✨ 정답 정렬을 이용하는 방법 정렬 sort를 이용하지만, 나는 각 인덱스의 len() 순서대로 정렬을 생각했다. 문제에서는 숫자로 된 문자열이였고, 이는 정렬에 활용할 수 있다. 1️⃣ 접근 방법 1 문자열을 정렬시 오름차순으로 정렬하게 되어있다. 숫자 문자열의 경우 앞에서부터 차례대로 오름차..

💡 나의 접근 방법 해시 딕셔너리를 이용해 접근하는 문제임을 알고 시작하였다. 1. 동명이인의 경우, 그 사람이 정답이 됨. 2. 동명이인이 없는 경우, completion에 없는 사람이 정답이 됨. 이렇게 동명이인의 경우를 나눠서 생각하였다. - 틀린 코드 def solution(participant, completion): answer = '' # dic = {} dic = {key:1 for key in completion} for i in participant: if i in dic.keys(): #해시에 있는 경우 dic[i] -= 1 else: #해시에 없는 경우 answer = i return answer else: for key,value in dic.items(): if value == ..

aAb1B2cC34oOp 이와 같은 문자열에서 숫자를 찾아 합하는 문제 -> 1 + 2 + 34 = 37 방법 1. 영문자를 ‘ ‘ 공백으로 변환하고 split() 을 이용해 리스트를 분할하여 숫자만 계산한다. def solution(my_string): # 알파벳이면 공백으로 변환하기 for i in my_string: if i.isalpha(): my_string = my_string.replace(i,' ') my_string = map(int,my_string.split()) return sum(my_string) 방법 2. 정규표현식 이용 정규표현식 (Regular expressions) 은 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용하는 형식 언어이다. 정규 표현식을 이용해 문자열 내..