남남이루의 고군분투 🌳

문제 프로그래머스 문제 바로가기 요약 * 1. 정해진 시간이 되면 과제를 시작한다. * 2. 진행중이던 건 멈춘다. * 3. 정해둔거 끝나면 멈춰둔거 한다 * 4. 멈춰둔거 여러개면 마지막에 하던거 한다 => 스택 접근 ''' CASE 1. done : 다음꺼까지 남은 시간 >= 소요시간 1-1. wait 리스트 소모 CASE 2. not done : 다음꺼까지 남은 시간 < 소요시간 2-1. wait 으로 넘김 남은 시간 업데이트 ''' def solution(plans): # 과목 , 시작, 소요시간 def getTime(time_str): h, m = map(int, time_str.split(':')) time_int = h*60+m return time_int wait = [] done = []..

문제 : 연속된 부분 수열의 합 프로그래머스 문제 바로가기 조건 1. 오름차순으로 정렬된 배열 조건 2. 배열의 길이 ≤ 1,000,000 요구사항 : 구간합이 특정 값이 되었을 때, 구간의 인덱스를 반환하라 단, 여러 구간이라면 길이가 짧은 구간을 채택하고, 길이마저 같다면 시작인덱스가 작은 구간을 채택하라. 접근 배열의 크기가 10^6이기 때문에 O(n^2) 알고리즘은 사용할 수 없다. 정렬된 배열의 특성을 최대한 이용한다. 구간합에 관한 문제이기 때문에 투포인터를 사용할 수 있다. (이진탐색은 특정 값을 찾는 데 사용) 내 풀이 def solution(sequence, k): sp = 0 ep = 1 tot = sequence[0] sequence+=[0] answer = [] chance = 1 ..

문제 : 프로그래머스 lv2. 뉴스클러스터링 (바로가기)[https://school.programmers.co.kr/learn/courses/30/lessons/17677] 문제 요구사항 // 1. str1과 str2를 정규식을 사용하여 영문만 남기고 숫자, 특수문자 등은 모두 " " 공백처리한다. // 2. 문자열 배열을 구한다. // 영문이 연속으로 나와야 문자열이 유효하다. 따라서 두번째 문자에 " " 공백이 있으면 제외한다. // 3. 문자열 배열의 합집합을 구한다. // 4. 문자열 배열의 교집합을 구한다. // 5. 답을 구한다.내 풀이 def solution(str1, str2): def getJachard(a,b): common=[] for each in a: if each in b: b...

https://school.programmers.co.kr/learn/courses/30/lessons/120956# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 순열 조합으로 풀어 봄 틀린 풀이 from itertools import permutations def solution(babb): answer = 0 possible = ["aya", "ye", "woo", "ma"] cand = set() for i in range(1,5): for comb in permutations(possible, i): cand.add(''.join(comb)) #..

문제 문제 바로가기 유클리드 호제법이란 정수 A와 B가 있다. A * s + B * t = r 을 만족하는 정수 s와 t가 있다는 것을 전제로 최대공약수 r을 구한다. 128과 42를 예시로 식을 풀어보자면, 128_s + 42_t = 최대공약수 r 128 = 42 * 어떤 몫 + r 형식으로 표현하고, 42와 r을 계속해서 풀어나가다 보면 나머지가 0이 된다. 그 때 마지막으로 대입됐던 수(이전 식의 나머지였던 수)가 128과 42의 최대 공약수가 된다. 128과 54 예시 128 = 54 * 2 + 20 54 = 20 * 2 + 14 20 = 14 * 1 + 6 14 = 6 * 2 + 2 6 = 2 * 3 + 0 따라서 2가 128과 54의 최대공약수이다. gcd는 최대공약수를 구할 때 사용한다. 파..

https://school.programmers.co.kr/learn/courses/30/lessons/120869 아래의 문제 조건이 집합으로 풀 수 있게 했음 dic과 spell 모두 중복된 원소를 갖지 않습니다. 집합을 이용한 풀이 def solution(spell, dic): spell = set(spell) for word in dic: if not spell-set(word): return 1 return 2 원래 내 풀이 def solution(spell, dic): answer = 2 checked = [0]*len(spell) check_dir = {key:idx for idx, key in enumerate(spell)} for word in dic: for letter in word:..

백준 9184. 신나는 함수실행 문제 요약 : 재귀함수로 돌리면 너무 오래 걸린다! 어떻게 할까? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15) a, b..

문제 문제링크 로봇은 90도 회전하거나, 평행이동을 한다 한 번 이동할 때 시간이 1씩 증가한다 n,n에 도착했을 때의 시간을 구해라 아이디어 q에서 꺼내서 if 끝 : 횟수 out 이동 조건 맞으면 q에 (좌표, 횟수) 넣기 평행이동 회전 가로 => 세로 세로 => 가로 알고리즘, 시간복잡도 BFS 시간 복잡도 O(V+E)? 자료구조 q = [[x1,y1,x2,y2], 횟수] hist = [[x1,y1,x2,y2], [...], ...] # q에 들어갔던 좌표인지 확인, x1 y1 x2 y2 => 왼오상하 순서로 넣고 뺀다 함수 move : 이동후 좌표 리스트 반환 bfs : 큐돌기 ''' 회고 블록의 회전이 꽤나 까다로웠다. 블록 회전 부분을 for 반복문으로 하면 코드가 더 간결해질 거 같다. 회전..

플로이드는, 다익스트라, 벨만 포드 알고리즘은 모두 한 시작점에서 다른 모든 정점까지의 거리를 구한다. 하지만 모든 쌍 간의 최단 거리를 구하기 위해서 보다 빠르고 간단한 방법이 플로이드 이다. 모든 쌍에 대한 최단 거리 알고리즘 알고리즘 특징 경유점이 존재 목적지를 갈 때 중간에 다른 노드를 거치는 것이 더 비용이 적을 수 있음. graph[u][v] 정점 u에서 v로 가는 최단 거리를 저장 논리 자체는 어렵지 않았고, 플로이드는 중간 노드를 기준으로 for 를 세 번 돈다는 점 (중간 노드가 최상단 반복문) 그래서 그래프가 크지 않을 때 쓸 수 있다는 점 (시간 복잡도가 n**3)을 명심명심~ 무한 값을 변수에 할당해서 쓰면 편함 핵심 구조 g = [[무한 값] for _ in range(노드수 + ..

메모리 초과 ➔ 정답처리 ➔ 개선 분석한 차이점 메모리 초과 케이스 (1차코드) : 56번쯤 라인에 바다 & 거리값 입력 안되어있으면 지금까지 온 거리 +1 이랑 기존 입력값이랑 min 비교하는데, 안해도 됨.. . BFS가 어떤 식으로 전개되는지 잘 안그려진다. 이 조건이 2차 코드에서 왜 없어도 되는지 이해가 잘 안간다. BFS는 칸마다 최단거리로 채워진다는 특징 때문인듯, 이미 방문했으면 굳이 안채워도 되나봐 secChecked 라고 구획을 그린 그래프를 별도로 두고, 이거로 visited도 판단함.. 그래프가 커질수록 부하가 걸렸나 => 메모리 초과의 원인인 듯 정답처리 된 케이스 (2차코드) : 섬 입력받은 표에 그대로 구획을 표시한거로 활용하고, visited True False 로 접근해서 ..