남남이루의 고군분투 🌳

프로그래머스 lv.2 양궁 대회문제 바로가기문제 요약어피치가 양궁을 먼저 다 쐈다. 화살의 수와 어피치의 과녘 현황을 입력값으로 줬을 때, 라이언이 어떻게 과녘을 맞춰야 최대 점수차이로 이길 수 있는지 반환해라.주의할 점최대 점수 차이가 같을 경우, 낮은 점수에 많이 맞은 경우를 답으로 처리한다.배열에 해당하는 과녘은 10점 과녘부터 0점까지 순서대로 주어진다.문제 접근완전 탐색에 조기종료 조건이 가능하므로 DFS를 사용한 백트래킹과녘의 수가 고정되어 있기 때문에 점수 현황을 고정 길이의 배열로 만들어서 과녘의 선택/ 미선택 두개의 정보를 담을 수 있다.조기 종료 조건 (유망함수)남은 화살이 더이상 없을 때.과녘의 끝에 다다랐을 때.오답노트1. recursive overflow 에러 발생.- DFS 접근..

문제 프로그래머스 문제 바로가기 요약 * 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(노드수 + ..