본문 바로가기

알고리즘69

C# 선택 정렬(Selection Sort)에 대해서 선택 정렬 최소값을 선택해서 맨 앞의 값과 교체한다. 그래서 선택 정렬이다! 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺸 나머지 리스트를 같은 방법으로 교체한다. 정렬 완료 시간 복잡도와 공간 복잡도 최고 시간 복잡도: O(n^2) 평균 시간 복잡도: O(n^2) 최악 시간 복잡도: O(n^2) 최고 공간 복잡도: O(1) 수도 코드 Initialize n = Length of Array SelectionSort (Array, n) { for i = 0 to n-2 { i_min = i for j = i+1 to n-1 { if Array[j] < Array[i_min] i_min = j } Swap(Array[j], Array[i_min]) } } .. 2024. 1. 17.
C# 삽입 정렬(Insertion Sort)에 대해서 삽입 정렬 삽입 정렬에 대해서 딱 들었을 때 드는 생각은 별도의 원소를 삽입하는 건가라는 생각이었다. 하지만 걱정하지 말자 추가적으로 원소를 삽입하거나 하지 않는다. 마치 손에 든 카드를 정렬하는 과정처럼 요소가 '마치' 삽입되기 때문에 삽입 정렬일 거라는 생각 한다. (버블 정렬의 경우 큰 수는 무조건 맨 뒤로 간다.) 2번째 요소부터 시작한다. 1번째 요소와 비교해서 1번째 요소보다 작으면 1번째 요소 앞에 배치한다. 3번째 요소로 이동한다. 1번째 요소와 2번째 요소와 비교한다. 이 과정을 배열의 길이 n - 1까지 반복한다. 시간 복잡도와 공간 복잡도 최고 시간 복잡도: O(n) 평균 시간 복잡도: O(n^2) 최악 시간 복잡도: O(n^2) 최고 공간 복잡도: O(1) 수도 코드(Pseudo C.. 2024. 1. 17.
C# 버블 정렬(Bubble Sort)에 대해서 버블 정렬(Bubble Sort) 누구나 한 번쯤은 들어봤을 버블 정렬(혹은 거품 정렬이라고도 불린다)에 대해서 알아보려고 한다. 버블 정렬은 구현이 직관적이고 간단하다. 아래의 과정을 배열의 길이 - 1번 반복한다. n번째 원소와 n + 1번째 원소를 비교한다. n번째 원소가 더 크다면 자리를 바꾼다. (Swap) n + 1번째 원소와 n + 2번째 원소를 비교한다. n + 1번째 원소가 더 크다면 자리를 바꾼다. (Swap) 배열 끝까지 이 과정을 반복한다. 이 과정을 통해 가장 오른쪽에 가장 큰 원소가 위치하게 된다. 시간 복잡도와 공간 복잡도 최고 시간 복잡도: O(n) 평균 시간 복잡도: O(n^2) 최악 시간 복잡도: O(n^2) 최고 공간 복잡도: O(1) 수도 코드(Pseudo Code) .. 2024. 1. 16.
[프로그래머스 Programmers] 2016년 문제 설명 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT 입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요. 제한 사항 2016년은 윤년입니다. 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. progr.. 2024. 1. 16.
[프로그래머스 Programmers] 숫자 짝궁 문제 설명 두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은 -1입니다. X, Y의 짝꿍이 0으로만 구성되어 있다면, 짝꿍은 0입니다. 예를 들어, X = 3403이고 Y = 13203이라면, X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 3, 0, 3으로 만들 수 있는 가장 큰 정수인 330입니다. 다른 예시로 X = 5525이고 Y = 1255이면 X와 Y의 짝꿍은 X와 Y에서 공통으로 나타나는 2, 5, 5로 만들 수 있는 가장 큰 정수인 552입니다(X에는 5가 3개, Y에는 5가.. 2024. 1. 15.
[프로그래머스 Programmers] 기사단원의 무기 문제 설명 숫자나라 기사단의 각 기사에게는 1번부터 number까지 번호가 지정되어 있습니다. 기사들은 무기점에서 무기를 구매하려고 합니다. 각 기사는 자신의 기사 번호의 약수 개수에 해당하는 공격력을 가진 무기를 구매하려 합니다. 단, 이웃나라와의 협약에 의해 공격력의 제한수치를 정하고, 제한수치보다 큰 공격력을 가진 무기를 구매해야 하는 기사는 협약기관에서 정한 공격력을 가지는 무기를 구매해야 합니다. 예를 들어, 15번으로 지정된 기사단원은 15의 약수가 1, 3, 5, 15로 4개 이므로, 공격력이 4인 무기를 구매합니다. 만약, 이웃나라와의 협약으로 정해진 공격력의 제한수치가 3이고 제한수치를 초과한 기사가 사용할 무기의 공격력이 2라면, 15번으로 지정된 기사단원은 무기점에서 공격력이 2인 무.. 2024. 1. 10.

티스토리툴바