728x90 반응형 프로그래머스182 [프로그래머스] 가장 먼 노드 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 경로를 통해 노드를 탐색하며 1번 노드에서 각 노드까지 최단거리를 구한 뒤, 가장 멀리 떨어진 노드의 개수를 구하면 되는 문제이다.1번 노드에서 각 노드까지 최단거리를 구하기 위해 BFS 알고리즘을 활용하여 각 노드를 탐색해 나간다.연결된 노드를 탐색하며 다음 노드에서 최단거리는 이전 노드에서 최단거리에 1을 더해주면 된다.거리를 저장할 리스트를 생성하고 연결된 노드를 탐색해 나갈 때마다 다음 노드에서의 최단거리를 저장해 나간다. BFS 알고리즘을 활용할 때 deque 자료.. 2024. 5. 4. [프로그래머스] 섬 연결하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 모든 섬이 이어질 때 그 비용이 최소가 되어야 한다.비용이 최소가 되어야 하므로 그리디 알고리즘을 활용하여 비용이 작은 것부터 섬을 연결하면 된다.하지만 여기서 섬들을 연결할 때 사이클이 존재하면 안 되기 때문에 이를 방지하고자 크루스칼 알고리즘을 활용하여 문제를 해결한다. 이를 유니온 파인드(union-find) 알고리즘으로 해결한다. 유니온 파인드 알고리즘은 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속.. 2024. 4. 28. [프로그래머스] 줄 서는 방법 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 가능한 모든 조합 중에서 k번째의 조합을 출력하는 문제이다.간단하게 순열을 생각하여 permutations() 함수를 사용해 모든 조합을 구한 뒤, k번째 조합을 출력하면 효율성에서 에러 즉, 시간초과가 발생하게 된다.하여 다른 방법으로 문제를 해결하기 위해 생각하던 중, 해당 자릿수는 각 n과 k의 값에 따라 n의 팩토리얼 값에 관련이 있다는 것을 알아냈다. k를 n - 1에서부터 0까지 각 팩토리얼 값으로 나눈 몫에 해당하는 숫자를 정답 리스트에 추가해 나가면 된다.이후.. 2024. 4. 25. [프로그래머스] 배달 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 1번 마을에서 각 마을까지 배달하는데 최소 시간을 모두 구하고 구한 최소 시간이 주어진 제한 시간 K보다 작거나 같은 마을의 개수를 세어주면 된다.해당 문제를 해결하기 위해서 다익스트라 알고리즘을 활용한다.다익스트라 알고리즘을 실행할 때 방문하지 않은 인접 노드를 방문하는 부분이 있는데, 이 부분에서 우선순위 큐를 사용하면 현재까지 발견된 가장 짧은 거리의 노드에 대해서 먼저 계산할 수 있고 더 긴 거리로 계산되었을 경우 스킵도 가능하다. 우선순위 큐를 사용하기 위해 hea.. 2024. 4. 21. [프로그래머스] 징검다리 건너기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 이분 탐색과 슬라이딩 윈도우로도 해결할 수 있지만 정렬로 직관적으로 해결할 수도 있다.우선 리스트를 생성하여 디딤돌에 적힌 숫자(밟을 수 있는 횟수)와 디딤돌의 위치를 묶어 리스트에 추가하고 디딤돌에 적힌 숫자를 기준으로 오름차순 정렬을 한다.숫자가 적을수록 먼저 밟혀 없어질 것이기 때문이다.디딤돌의 숫자가 적은 돌부터 불러오며 다리를 건너가고 디딤돌을 제거한다.현재 디딤돌이 빠지면서 다음 디딤돌과 이전 디딤돌 사이의 길이를 확인하여 주어진 K보다 큰지 판별한다.K보다 크면.. 2024. 4. 19. [프로그래머스] 숫자 카드 나누기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 설명 2. 풀이과정 해당 문제는 두 조건 중 하나라도 만족하는 가장 큰 양의 정수를 구하는 문제이다. 각 조건을 만족하는지 판별하는 방법은 각 카드 리스트의 최대 공약수를 구하여 구한 최대 공약수를 다른 리스트의 카드 값에 나누어 봤을 때 모두 나누어 떨어지지 않으면 된다. 각 리스트의 최대 공약수를 구할 때는 math 라이브러리의 gcd() 함수를 사용한다. 그렇게 구한 각 리스트의 최대 공약수를 다른 리스트의 값들과 모두 나누어 0이면 True를, 0이 아니면 False 값으로 저장한 후 0이 .. 2024. 3. 23. [프로그래머스] 시소 짝꿍 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 설명 2. 풀이과정 해당 문제는 가능한 시소 짝꿍의 수를 구하는 문제이다. 가능한 짝꿍의 조합을 하나하나 판별하는 것은 많은 시간이 걸린다. 하여 각 무게별로 가능한 조합인지 판별하고 해당 조합이 총 몇 쌍 나올 수 있는지 구하는 방법으로 해결하고자 하였다. 우선 동일한 무게를 가지는 사람은 서로 동일한 거리에만 앉으면 되므로 동일한 무게를 가지는 사람의 수를 세어 그중 2명을 뽑는 경우의 수를 구한다. 다른 무게를 가지는 사람들 중 서로 짝꿍이 될 수 있는 조합을 구한다. 이후 전체 인원 중 해당.. 2024. 3. 18. [프로그래머스] 마법의 엘리베이터 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 설명 2. 풀이과정 해당 문제는 마법의 돌을 최소한으로 사용하여 0층으로 갈 때의 마법의 돌 개수를 구하는 문제이다. 마법의 돌을 최소한으로 사용하려면 각 자릿수마다 -의 돌을 사용할지, +을 돌을 사용할지 결정하는 방법이 중요하다. 1의 자릿수부터 어떤 종류의 돌을 사용할지 정하며 전체 사용하는 돌의 개수에 더해준다. 만약 해당 자릿수의 값이 5 미만의 수이면, 그냥 -의 돌을 사용하여 내려온다. 만약 해당 자릿수의 값이 5를 초과하는 수이면, 반대로 그냥 +의 돌을 사용하여 올라간 후 한 번에 .. 2024. 2. 4. [프로그래머스] 보석 쇼핑 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 설명 2. 풀이과정 해당 문제는 보석의 모든 종류를 포함하는 구간 중 가장 짧은 구간을 구하는 문제이다. 해당 문제에서는 시작부터 끝까지 구간의 끝을 늘려가면서 딕셔너리를 활용해 각 보석의 개수를 저장하고 딕셔너리의 보석의 종류가 전체 구매할 보석의 종류와 일치하면 현재 구간에서 가능한 모든 구간을 구한다. 가능한 모든 구간을 구했다면 구간의 길이가 짧은 순서대로 정렬하여 가장 짧은 구간을 찾는다. 보석의 종류를 저장한다. num = len(set(gems)) 가능한 구간을 저장할 리스트를 생성한다.. 2023. 11. 17. [프로그래머스] 호텔 대실 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 호텔 예약의 입실 시각, 퇴실 시각을 기준으로 최소한의 방을 사용하는 문제이다. 우선 입실 시각을 기준으로 정렬하고 입실 시각이 우선인 예약부터 방을 배정한다. 방은 00:00부터 23:59까지 예약이 가능하므로 예약 가능 시각을 모두 분으로 변경하여 각 분을 한 칸으로 지정해 예약 가능한지 판별한다. 방 하나를 가지고 모든 예약 시각을 불러오며 최대한의 예약을 채우고, 방을 예약하면 예약 시각에서 제거하고 예약 시각이 비워질 때까지 반복한다. 예약 시각을 deque 자료구.. 2023. 11. 15. 이전 1 2 3 4 5 6 7 ··· 19 다음 728x90 반응형
