새벽의 블로그

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 최단 거리를 구하는 문제.가까운 노드부터 탐색하도록 그래프 탐색법 중 BFS를 이용했다.공식 쓰듯이 사용했더니, 이용하지 않으면 시간이 지나고 까먹곤 해서.. 기초부터 다시 보았고, 한 티스토리의 기본 코드를 참고했다.나중에 다시 BFS와 DFS를 정리해서 포스팅하겠다.  풀이 1. 시작점은 0,0 노드이다.2. 노드에서 이동 가능한 dx, dy를 리스트로 정의한다.이는 순서대로 left..

풀이 논리  1. 레이저는 두 괄호가 붙어서 등장한다. 따라서 "(" ")" 가 연속으로 인식되면 이를 레이저로 처리할 수 있다.2. 레이저는 지금까지 등장한 막대기를 잘라낸다. 따라서 등장한 막대기의 개수만큼 누적값을 증가시킬 수 있다.3. 막대기의 종료점이 등장하는 경우, 해당 막대기가 잘려나가는 효과와 동일하므로 누적값을 +1 증가시킬 수 있다.4. 막대기가 등장해서, 종료되기 전까지 이 열린 괄호를 스택에 관리한다.  정답 코드input = input()stack = [] answer = 0temp = ''for i in input: if i == '(': stack.append("(") elif i == ')' : stack.pop() if tem..

그리디 알고리즘을 적용하는 프로그래머스 문제,  파이썬 풀이생각의 흐름앞 순서의 학생부터, "해당 학생의 앞 학생 검사 - 양도 실패 시 뒷 학생 검사" 를 실행하여 양도가 가능하면 양도 받게 한다. *놓친 점 1 : 이 주의 메세지를 보지 않아서 reserve에 포함되지만, 본인의 필요에 의해 양도가 불가능한 경우를 고려하지 않았다.여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.-> 이후 조건을 보고 해당 케이스를 위해 각 리스트의 차집합, 교집합을 고려하였다.오답 코드def solution(n, lost, reserve): answer = n - len(l..

문제두 정수 N과 F가 주어진다. 지민이는 정수 N의 가장 뒤 두 자리를 적절히 바꿔서 N을 F로 나누어 떨어지게 만들려고 한다. 만약 가능한 것이 여러 가지이면, 뒤 두 자리를 가능하면 작게 만들려고 한다.예를 들어, N=275이고, F=5이면, 답은 00이다. 200이 5로 나누어 떨어지기 때문이다. N=1021이고, F=11이면, 정답은 01인데, 1001이 11로 나누어 떨어지기 때문이다.입력첫째 줄에 N, 둘째 줄에 F가 주어진다. N은 100보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. F는 100보다 작거나 같은 자연수이다.출력 첫째 줄에 마지막 두 자리를 모두 출력한다. 한자리이면 앞에 0을 추가해서 두 자리로 만들어야 한다.  저번에 계속 오답 나오던 코드.. ..

문제오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자.O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki/Big_O_notation)과 다를 수 있다.함수 f(n) = a1n + a0, 양의 정수 c, n0가 주어질 경우 O(n) 정의를 만족하는지 알아보자.입력첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 ≤ |ai| ≤ 100)다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 10..

def solution(clothes): closet = {} total = 1 for cloth, typ in clothes: closet[typ] = closet.get(typ,0) + 1 for typ in closet: total *= closet.get(typ)+1 return total-1  def solution(clothes): mapi = {} for cloth in clothes: if cloth[1] not in mapi.keys(): mapi[cloth[1]] = 1 else: mapi[cloth[1]] = mapi[cloth[1]]+1..

접두어가 될 번호를 대상으로 검사하려고 했다.  전화번호부에 ["11","119","45234"] 가 있다면, 11, 119, 45234에 대해서 for loop를 돌고, 내부 for loop로 나머지 번호에 대해서 검사한다. 이때 11, 119, 45234를 for 도는 방식이면 나머지 비교번호를 이 길이만큼으로 잘라야 해서, 이중 for loop를 쓸 수 밖에 없다. 이렇게 되면 시간초과가 발생한다.def solution(phone_book): dict1 = {} for i in range(len(phone_book)): dict1[i] = phone_book[i] for num in phone_book: if any(nums.startswith(num) an..

*  프로그래머스 - 최소직사각형(lv.1)def solution(sizes): big = [] small = [] for size in sizes: big.append(max(size)) small.append(min(size)) return max(big)*max(small) 가로 세로 회전이 가능한 경우에 어떻게 비교해야 할지 아이디어가 떠오르지 않아서 해설을 참고했다.제시된 명함의 길이 중 큰 것은 더 큰 값들 사이에 속해야 묻어갈 수 있고, 작은 것은 더 작은 값들에 속해야 묻어가거나 값을 최소화 할 수 있다는 것을 조금만 더 생각했더라면 .. 싶다. *  프로그래머스  - 소수찾기(lv.2)from itertools impor..