📦 아카이브10 삽입 정렬은 뭐야? 개념 삽입 정렬은 다른 정렬 방식과는 다르게 정렬된 배열 A[1..n]에 정렬할 원소를 삽입할 인덱스를 계산하여 삽입하는 정렬 알고리즘입니다. 구현 방법 오름차순 정렬을 기준으로 살펴본 삽입 정렬의 구현 방법은 다음과 같습니다. 배열을 순환하며 정렬할 원소 new_item을 선택한다. new_item을 제외한 배열을 순환한다. new_item보다 큰 원소를 찾게되면 해당 원소와 new_item의 위치를 교환한다. 파이썬 구현 코드 def insertion_sort(array): for i in range(1, len(array)): # 1. prev = i - 1 new_item = array[i] while prev >= 0 and new_item < array[prev]: # 2. array[prev.. 2022. 8. 2. 선택 정렬은 뭐야? 개념 선택 정렬은 배열 A[1... n]에서 가장 작은 원소를 찾아 배열의 앞자리에 있는 A[i]와 바꾸는 것으로 원소를 넣을 위치는 결정된 상태에서 넣을 원소를 선택하는 것 알고리즘입니다. 구현 방법 오름차순을 기준으로 본 선택 정렬의 구현 방법은 다음과 같습니다. 배열을 순환하며 가장 작은 원소의 인덱스를 선택한다. 1의 결과를 정렬되지 않은 배열의 맨 앞 값과 교환한다. 배열의 길이 -1만큼 1을 반복한다. 파이썬 구현 코드 def selection_sort(array): for i in range(len(array) - 1): # 1. min_index = i for j in range(i + 1, len(array)): if array[j] < array[min_index]: min_index .. 2022. 8. 1. 버블 정렬은 뭐야? 개념 버블 정렬은 배열 A[1...n]에서 인접한 두 원소를 비교하며 조건(내림차순 또는 오름차순)에 맞게 자리를 교환하는 정렬 알고리즘입니다. 구현 방법 오름차순 정렬을 기준으로 본 버블 정렬의 구현 방법은 다음과 같습니다. 배열을 순환하며 가장 큰 원소를 배열의 끝에 위치시킨다. 원소 하나가 정렬되었기 때문에 배열의 크기를 감소시킨다. 배열의 길이만큼 1을 반복한다. 파이썬 구현 코드 def bubble_sort(number_list): for i in range(len(number_list) - 1): # 1. for j in range(1, len(number_list) - i): # 2. if number_list[j-1] > number_list[j]: # 3. number_list[j-1],.. 2022. 7. 29. 프로그래머스 76502 괄호 회전하기 괄호 회전하기 문제에 대한 설명은 다음 링크를 참고해주시기 바랍니다. 문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 괄호 회전하기 문제는 주어진 문자열 s를 한 문자씩 회전한 결과들 중에 올바른 괄호를 가진 개수를 구하는 문제입니다. 따라서 문자열 s를 사용하여 나올 수 있는 모든 경우의 수를 탐색하는 완전 탐색 문제입니다. 따라서 문제를 해결하기 위한 순서는 다음과 같습니다. 올바른 괄호를 만들 수 있는 문자열인지 확인한다. 1의 결과가 참이라면 문자열 s를 순환하며 가능한 후보군을 배열에 저장한다. 거짓이라면 0을 반환한다. 후보군을 순환하.. 2022. 7. 28. 프로그래머스 42583 다리를 지나는 트럭 다리를 지나는 트럭 문제에 대한 설명은 다음의 링크를 참고해주시기 바랍니다. 문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 우선, 다리를 지나는 트럭은 truck_weights로 주어진 트럭의 순서가 변경될 수 없습니다. 따라서 정해진 순서를 기반으로 모든 트럭이 다리를 건너는 최소 시간을 정답으로 구합니다. 예시는 자세한 설명을 동반하고 있어 질문하기 목록에 있는 예시 테스트 케이스 중 하나로 문제 해결 순서를 확인해보겠습니다. 질문하기 bridge_length = 5, weight = 5, truck_weights = [2, 2, 2, 2,.. 2022. 7. 22. 프로그래머스 42747 H-Index H-Index 문제에 대한 설명은 다음 링크를 확인하면 됩니다. 문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr H-Index는 논문 n개 중, h번 이상 인용된 논문이 h 편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 H-Index가 됩니다. 처음 문제에 대한 설명을 읽었을 때 "이게 무슨 소리지?"라는 생각이 들었습니다. 이해를 더 쉽게 하기 위해서는 예시를 자세하게 봐보는 것이 도움이 되기 때문에 문제에서 예시로 제시한 입출력이 어떻게 정답을 반환하는지 알아보겠습니다. citations = [3, 0, 6, 1, 5] 내림.. 2022. 7. 20. 프로그래머스86971 전력망 둘로 나누기 전력망 둘로 나누기 문제 설명은 다음 링크를 참고하면 됩니다. 문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 노드의 총합 n과 노드의 연결 정보를 가지고 있는 wires를 활용하여 두 그래프의 노드의 개수의 차이를 최대로 하는 결과를 반환하는 문제입니다. 하나의 그래프에서 임의의 노드 연결을 제거하였을 때 노드의 차이를 구하기 위해서는 모든 경우를 찾아보지 않고는 답을 확실하게 구할 수 없어 모든 경우의 수를 탐색하였습니다. 구현 방법은 다음과 같습니다. (그래프 연결 정보는 인접 리스트 표현법에 따라 저장한다) 인접 리스트 표현법으로 그래프의.. 2022. 7. 19. 연결리스트는 뭐야? 연결 리스트는 구조를 봐도 알 수 있듯이 연결되어 있는 리스트이다. 연결 리스트는 배열과 거의 같은 기능을 한다. 2가지 자료 구조에 대해서 장단점을 연결 리스트를 중점으로 알아보겠다. 연결 리스트의 장점 연결 리스트 중간에 값을 삽입하는 것이 편한다. 데이터를 저장할 때마다 동적으로 공간을 만들어서 쉽게 추가할 수 있다. 연결 리스트의 단점 데이터와 함께 포인터를 저장해야 하므로 메모리를 많이 차지한다. 배열에 비해 상대적으로 구현이 어렵다. i번째 데이터에 대해서 순차적으로 탐색을 해야 한다. 장점과 단점을 잘 비교하여 필요한 자료 구조를 잘 선정하면 될 것 같다. 다음은 연결 리스트의 구조체이다. typedef int element; typedef struct { element data; struc.. 2022. 7. 8. 큐는 뭐야? 스택과 마찬가지로 큐를 1 문장으로 요약하면 "선입선출의 특성을 가진 자료구조"라고 할 수 있다. 선입선출은 사실 실생활에서도 굉장히 많이 사용된다. 예를 들어 은행에 갔을 때 번호표를 뽑는 것, 맛집에 갔을 때 순서표를 뽑고 기대리는 것, 편의점 물류 정리 등이 있다. 다음은 컴퓨터 공학에서 큐의 활용 예시이다. 키보드, 마우스 등 입력 장치 관리 모니터, 프린터 등 출력 장치 관리 운영체제 작업 스케줄링 선입선출의 특성을 가지기 위해서는 원소를 저장하기 위한 배열 data와 맨 앞 원소를 가리킬 front, 맨 뒤 원소를 가리킬 rear 변수가 필요하다. 특성에 맞게 구조체로 표현하면 다음과 같다. typedef int element; typedef struct { int front, rear; el.. 2022. 7. 5. 스택은 뭐야? "스택은 후입 선출(LIFO) 형식의 자료구조이다." 정도의 개념은 다들 한 번씩 들어봤을 거라고 생각한다. 스택의 개념은 이렇게 한 줄로 설명할 수 있지만 스택은 프로그래밍 언어, 시스템 기능 등 많은 부분에서 활용되고 있다. 스택 활용 예시는 다음과 같다. 함수 호출 및 실행 웹페이지 또는 핸드폰의 뒤로 가기 기능 후위표기식을 사용한 수식 계산 스택을 구현하기 위해서는 원소를 저장하기 위한 data와 가장 최근에 입력되었던 원소의 인덱스 위치를 가리키는 top이 필요하다. 구조체로 표현하면 다음과 같다. typedef int element; typedef struct { element data[STACK_SIZE]; int top; } StackType; 위와 같은 구조를 가진 스택을 구현하기 위해서.. 2022. 7. 4. 이전 1 다음
