알고리즘

[알고리즘] 퀵정렬 / 병합정렬 / DFS&BFS / DP

불안정 정렬 다른 원소와의 바교만으로 정렬을 수행하는 비교정렬 분할 정복 알고리즘 --> 매우 빠른 수행속도 합병 정렬과 달리 리스트를 비균등하게 분할 분할정복방법 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 대개 순환 호출을 이용하여 구현 과정 설명 1. 리스트 안에 있는 한 요소를 선택. --> 피벗 이라고 한다. 2. 피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들로 옮겨진다. 3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬 분할된 부분 리스트에 대하여 순환호출을 이용하여 정렬을 반복 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복 4. 부분 리스트들이 더..

정렬 알고리즘

거품정렬(버블정렬) 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환한다. 선택정렬과 기본 개념이 유사 버블정렬 c언어 코드 # include # define MAX_SIZE 5 // 버블 정렬 void bubble_sort(int list[], int n){ int i, j, temp; for(i=n-1; i>0; i--){ // 0 ~ (i-1)까지 반복 for(j=0; jheap[i/2]; // 한 레벨 위로 올라단다. i /= 2; } h->heap[i] = item; // 새로운 노드를 삽입 } 2. 최대힙의 삭제 1. 최대 힙에서 최댓값은 루트 노드이므로 노드가 삭제된다. - 최대 힙에서 삭제 연산은 최댓값을 가진 요소..

[python] 프로그래머스 > 정렬 > H-Index

[문제] 1. 문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 2. 제한사항 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다. 논문별 인용 횟수는 0회 이상 10,000회 이하입니다. 3. 입출력 예..

[python] 프로그래머스 > 월간 코드 챌린지 > 3진법 뒤집기

[문제] 1. 문제 설명 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 2. 제한사항 n은 1 이상 100,000,000 이하인 자연수입니다. 3. 입출력 예 n result 45 7 125 229 4. 입출력 예 설명 입출력 예 #1 답을 도출하는 과정은 다음과 같습니다. n (10진법) n (3진법) 앞뒤 반전(3진법) 10진법으로 표현 45 1200 0021 7 따라서 7을 return 해야 합니다. 입출력 예 #2 답을 도출하는 과정은 다음과 같습니다. n (10진법) n (3진법) 앞뒤 반전(3진법) 10진법으로 표현 125 11122 22111 229 따라서 229를 ret..

자료구조와 알고리즘

input -> process -> output ↑↓ Store 데이터의 흐름과 저장 - 자료구조 시간과 공간 효율성 - 알고리즘 자료구조 때와 장소에 맞는 자료구조를 사용해야한다. 알고리즘 - 좋은 알고리즘의 조건 1. 적절한 입력.출력 2. 명확성(목적) 3. 유한성(무한루프X) 4. 효율성 - 자료구조와 알고리즘의 관계 자료구조가 알고리즘에 쓰인다.(자료구조를 활용하여 어떤 문제를 해결) 자료를 직접 구현하려면 알고리즘이 필요하다. => 서로 뗄 수 없는 사이

[python] 프로그래머스 > 가장 큰 수

1. 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 2. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 3. 입출력 예 numbers return..

[python] 프로그래머스 > 해시 > 완주하지 못한 선수

1. 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 2. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 3. 입출력 예 participant completion return [le..

[python] 프로그래머스 > 동적계획법(DP) > 정수삼각형

1. 문제 설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 2. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 3. 입출력 예 triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 ..