Weeeeey Weeeeey

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제 조건 stones 배열의 크기는 1 이상 200,000 이하입니다. stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다. 처음에는 한번에 건널 뛸 수 있는 k 만큼 돌을 묶어서 그 안의 범위 중 최댓값을 찾고 또 그 최댓값 중 가장 작은 값을 결과로 출력함 하지만 이럴 경우 중간 중간 묶었을 때 발생하는 공백들로 인해 묶음의 범위가 또 ..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 투 포인터를 이용해서 모든 보석 종류를 수집하지 못했다면 end +1 모든 보석 종류를 수집해서 end까지의 최소 길이 구하기 위해 start+1 특정 보석의 갯수는 딕셔너리를 이용해서 체크 모든 보석 종류를 수집했는지는 r이라는 변수를 두고 수집 할 보석 갯수 nn 가 비교해서 알아냄 r==nn 이면 모든 보석을 수집한 것이므로 최소 길이를 구하기 위해 start를 +1 씩..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12979 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 n의 최댓값이 2억인데 채점 시 효율성 테스트까지 거치므로 시간 복잡도는 O(n)을 넘으면 안됨 n을 순회하기 보단 길이가 1만 이하인 stations를 활용해서 수학적으로 접근 한 지점에서 커버 하는 공간은 2*w + 1 이다. (좌우 + 자기 자신) 길이가 10이고 w가 1이면 10//3 을 통해 4개가 필요한 걸 알 수 있음 stations이 이미 있으므로 이것을 제외하..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 S에서 출발해서 a,b에 도착하는 최소한의 비용을 출력하는 문제 s->k->a , s->k->b 를 구해야함. 한 점을 지나쳐서 다른 점을 방문하는 것이므로 플로이드 와샬을 떠올릴 수 있음 n의 갯수도 200 이하 이므로 시간 복잡도 괜찮 하지만 나는 다익스트라 최단 경로를 이용해서 특정 점에서 a와 b에 도착하는 최단 경로를 구해줌(시간을 더 최적화 시켜줄려고) dikstr..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 BFS/DFS 중에서 BFS로 접근 경로가 여러개 일 경우 알파벳 순으로 사용하므로 ticket들 정렬 gr이라는 딕셔너리에 [출발 지역]:[tickets idx] 저장 큐에 현재 공항, 이용한 경로, 사용한 티켓 idx 를 담음 이용 경로의 갯수와 티켓+1 이 같으면 종료 (모두 사용한 거니까) 딕셔너리에서 키 값이 없는 것을 그냥 꺼내오면 에러가 나서 get으로 걸러내기 ..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 시작 노드가 주어지지 않는 채, 연결 정보들이 주어졌을 때의 모든 노드를 탐색 하는 최소 가중치(비용)를 구하는 문제 모든 노드를 탐색하면서 최소 가중치를 구하는 알고리즘을 짜야함. 이 때 크루스칼 알고리즘 떠올리는 짬이 있어야함 크루스칼은 주어진 정보들을 가중치를 기준으로 오름차순으로 정렬한 뒤, 하나하나 간선들을 이어나가는 과정 이 때, 특정 경로에서 하나의 왕복 루틴이 ..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1번 노드에서 출발 해서 각 노드들에 최단 경로로 도착하는데 그 중에 가장 멀리 떨어진 노드들의 갯수를 출력하는 문제 다익스트라로 풀었는데 노드 갯수만 적었다면 bfs dfs도 가능할듯? 소스 코드 import heapq INF = int(1e9) def solution(n, edge): answer = 0 gr = [[]for i in range(n+1)] dit = [IN..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1칸 띄워서 계산하는 문제이므로 개수가 3개 이하라면 그 수들 중 가장 큰 수가 정답이 됨. a, b, c 일 땐 a와 c도 합체가 안되므로 dp [n]=max(s [n]+dp [n-2], dp [n], s [n]+dp [n-3] ) 경우의 수 첫 번째 수부터 계산(이 경우 마지막 숫자는 빼줘야 함) 두 번째 수부터 계산(이 경우 마지막 숫자도 더하기 가능) 세 번째 수부터 ..