알고리즘

[Algorithm/Python] 다익스트라 최단 경로 알고리즘이란? || dijkstra

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

[Algorithm/Python] 이진 탐색(Binary Search)란?

들어가며 본 포스팅에서는 순차 탐색(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 번째의 데이터가 타겟과 동일하다는 결과를 ..

[Algorithm/Python] 계수 정렬(Count Sort)이란?? || Sort

📌 계수 정렬(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..

[Algorithm/Python] 퀵 정렬(Quick Sort)이란? || Sort

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

[Programmers/Python] 운영체제

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

[Programmers/Python] 가장 큰 수 || 정렬

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

[Programmers/Python] 폰켓몬, 전화번호 목록 || Hash

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 파이썬 폰켓몬 1845더보기문제 설명 )당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 ..

[Algorithm/Python] 파이썬 itertools에서 combinations, permutations를 사용하지 않고, 조합과 순열 구현

파이썬에서는 순열과 조합을 간단하게 바로 구해볼 수 있다. 그러나, itertools가 기억이 나지 않는 경우를 대비하여 순열과 조합을 직접 구현해보도록 하자. 📌 itertools 패키지의 combinations, permutations 활용 먼저 itertools를 통해 조합과 순열을 구하는 방법이다. ✅ [ CODE ] # 조합 from itertools import combinations arr = [0, 1, 2, 3] print(list(combinations(arr, 2))) # [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] ✅ [ CODE ] from itertools import permutations arr = [0, 1, 2] print(lis..

[Programmers/Java] 올바른 괄호 || Stack & Queue

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 자바 올바른 괄호 12909 더보기 문제 설명 ) 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요. 제한..

[Programmers/Python] 올바른 괄호 || Stack & Queue

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr프로그래머스 파이썬 올바른 괄호 12909 더보기 문제 설명 ) 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요. 제..