들어가며본 포스팅에서는 다익스트라 최단 경로 알고리즘에 대해 소개합니다.📌 다익스트라 최단 경로 알고리즘이란?다익스트라 최단 경로 알고리즘이란, 가장 짧은 경로를 찾기 위한 알고리즘으로, 음의 간선(0보다 작은 값을 가진 간선)이 없을 때에 적용할 수 있는 알고리즘입니다. 1️⃣ 출발 노드를 설정합니다.2️⃣ 최단 거리 테이블 초기화(무한으로 설정)합니다.3️⃣ 방문하지 않은 노드 중에 최단 거리 테이블에서 최단 거리가 가장 짧은 노드를 선택합니다.4️⃣ 선택한 노드를 거쳐 다른 노드로 가는 거리를 계산합니다.5️⃣ 계산된 거리가 최단 거리 테이블의 거리보다 짧을 경우, 갱신합니다.6️⃣ 위의 3️⃣4️⃣5️⃣를 반복합니다.  가장 최단 거리의 노드를 선택하여 주변 간선을 확인합니다. 더 짧은 거리가 ..

들어가며 본 포스팅에서는 순차 탐색(Sequential Search)과 이진 탐색(Binary Search)에 대해 소개합니다. 📌 순차 탐색이란? 순차 탐색(Sequential Search)이란, 특정 데이터를 찾기 위해 앞에서부터 차례대로 값을 비교해나가는 탐색 방식입니다. 1️⃣ 가장 첫 번째 데이터를, 찾고자하는 데이터(타겟)과 비교합니다. 2️⃣ 값이 서로 일치하지 않는다면, 다음 데이터로 이동하여 비교합니다. 3️⃣ 이를 반복하며 일치할 때, 탐색을 종료합니다. ✅[ CODE ] def sequential_search(n, target, arr): for i in range(n): if arr[i] == target: return i + 1 i + 1 번째의 데이터가 타겟과 동일하다는 결과를 ..

📌 계수 정렬(Count Sort)계수 정렬이란, 리스트의 원소의 개수를 세어, 개수만큼 출력하여 정렬하는 방식이다. 예를 들어 arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] 를 정렬해본다고 하자면, 각 원소별로 몇 개가 존재하는지 수를 센 후, 인덱스 0을 시작으로 각 개수만큼 수를 출력해내어 정렬하는 방식이다.위의 그림처럼, 리스트의 데이터에 해당하는 인덱스의 값을 1씩 추가하여 해당 원소가 몇 개인지 수를 세어준다. 따라서, 인덱스 0부터 차례대로 세어진 수만큼 반복 출력해주면 정렬된 리스트를 확인해볼 수 있다. ✅[ CODE ]arr = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] def count(arr): ma..

📌 퀵 정렬(Quick Sort)퀵 정렬(Quick Sort)이란 기준 데이터인 피벗(pivot)을 정하고, 피벗보다 큰 데이터와 작은 데이터의 위치를 변경하는 정렬 방식이다. 피벗이 설정되어 리스트가 분할되는 방법에 따라 여러 퀵 정렬이 구분된다고 하는데, 호어 분할 방식에 따른 코드 구현을 진행해보았다. 호어 분할 방식에는 리스트에서 첫 번째 데이터를 피벗으로 설정한다는 규칙이 있다. 1️⃣ 리스트의 첫 번째 데이터를 피벗으로 설정한 후, 리스트의 왼쪽에서 오른쪽으로 이동하며 피벗보다 큰 데이터를 찾는다. 또한, 리스트의 오른쪽에서 왼쪽으로 이동하며 피벗보다 작은 데이터를 찾는다. 2️⃣ 큰 데이터와 작은 데이터의 위치를 서로 바꾼다. 3️⃣ 이와 같은 과정을 반복하되, 큰 데이터의 위치와 작은 데이..

📌 삽입 정렬(Insertion Sort)삽입 정렬은 순차적으로 데이터를 확인하며, 적절한 위치에 삽입해주는 정렬 방식이다. 그림을 보면, 인덱스 1번째 수부터 시작하여 차례대로 각자 적절한 위치에 삽입해주는 것을 확인해볼 수 있다. 적절한 위치인 곳을 찾는 방법은, 빨간 박스로된 수를 기준으로 왼쪽으로 한 칸씩 이동하며 값을 비교한다. 빨간 박스의 수보다 작은 수를 만나게 되는 순간, 바로 그 위치에 삽입해주면 된다. ✅ [ CODE ]arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(arr)): idx = i for j in range(i, -1, -1): if arr[i] < arr[j]: idx = j val = arr[i] arr[idx +..

📌 선택 정렬(Selection Sort)그림을 보면, 파란색으로 칠해진 수들 중 가장 작은 수를 골라, 빨간색으로 칠해진 수와 바뀌는 것을 확인해볼 수 있다. 이처럼, 선택 정렬은 가장 작은 수를 차례대로 선택하여 정렬하는 방식이다. ✅ CODEarr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(arr)): for j in range(i + 1, len(arr)): if arr[i] > arr[j]: temp = arr[i] arr[i] = arr[j] arr[j] = temp print(arr)매번, 작은 수가 나올 때마다 위치를 바꿔주어 주도록 구현을 해보았는데, 작은 수가 나올 때마다 바꿔주는 것이 조금 비효율 적인 것 같다는 생각이 들었다. ✅ C..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 파이썬 H-Index 풀이 42747더보기문제 설명) H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 타겟 넘버 파이썬 16173더보기문제 설명) n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항) 주어지는 숫자의 개수는..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 파이썬 PCCP 모의고사 1회 4번 운영체제 121686 더보기 문제 설명 개발자 준모는 운영체제를 만들었습니다. 준모가 만든 운영체제는 프로그램의 우선순위와 호출된 시각에 따라 실행 순서를 결정합니다. 모든 프로그램에는 1부터 10까지의 점수가 매겨져 있으며, 이 점수가 낮을수록 우선순위가 높은 프로그램입니다. 각 프로그램들은 실행 시간이 정해져 있으며 프로그램이 호출되면 대기상태에 있다가 자신의 순서가 되면 실행 시간 동안 실행된 뒤 종료됩니다. 준모가 만든 운영체제는 호출된 프로그램들 중 우선순위..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 파이썬 가장 큰 수 42746더보기문제 설명0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.제한 사항..