본문 바로가기
반응형

알고리즘70

[백준 BAEKJOON] 17215번 볼링 점수 계산 문제 소현이는 친구들과 함께 볼링을 치러 볼링장에 갔다. 그런데 볼링장의 시스템 오류로 인해 점수판에 점수가 집계 되지 않는 문제가 있었다. 밖이 너무 추운 나머지 소현이와 친구들은 그냥 치기로 하였고 1게임이 끝났지만 각자 점수가 얼마나 되는지를 계산하지 못하고 있다. 소현이와 친구들을 위해 볼링 점수를 계산해주는 프로그램을 작성해 보자. 볼링 규칙 1게임은 총 10프레임으로 구성되어 있다. 각 프레임마다 볼링핀 10개를 세워두고 공으로 쓰러뜨리는 것이며 기본적으로 볼링핀 1개당 1점이다. 각 프레임마다 2번의 기회가 주어지며 첫 번째 기회에 10개의 핀을 모두 쓰러뜨리는 것을 스트라이크(S)라고 한다. 두 번째 기회까지 사용하여 10개의 핀을 쓰러뜨리는 것을 스페어(P)라고 한다. 스트라이크를 치면 .. 2024. 1. 22.
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.

티스토리툴바