'Algorithm' 카테고리의 글 목록

Algorithm

퀵정렬(Quick-Sort) 알고리즘

2024.02.02

퀵정렬이란? 퀵정렬(Quick-Sort)은 평균 속도 (NlogN)을 자랑하는 매우 빠른 알고리즘이다. 분할정복(Divide & Conquer) 알고리즘의 하나로 다른 원소와 비교만으로 정렬을 수행하는 비교 정렬에 속하는 알고리즘이다. 정렬과정 퀵정렬은 임이의 피봇(pivot)을 기준으로 좌측에는 피봇보다 작은 값을 두고 우측에는 피봇보다 큰 값을 두는 방식으로 정렬한다. 피봇을 선택한다. left는 왼쪽에서 오른쪽으로 가면서 피봇보다 더 큰 수를 찾는다. right는 오른쪽에서 왼쪽으로 가면서 피봇보다 더 작은 수를 찾는다. 찾은 지점에서 left와 right를 교환한다. 위 과정을 left랑 right가 바뀔 때까지 반복한다. left랑 right가 바뀌면 피봇과 right를 교환한다. 위 과정을 거..

Algorithm/BOJ

백준(BOJ) 11047번 동전 0 [그리디(Greedy)/알고리즘/파이썬(python)]

2021.08.11

그리디 알고리즘이란? "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 거스름돈을 돌려주는 문제를 생각해보자. 우리는 대부분 거스름돈을 돌려줄때 큰 단위의 동전부터 거슬러준다. ex ) 500원을 돌려줘야 한다면, 100원을 5개 주는 것보다 500원을 1개 주는 편이 더 편하다. 하지만 만약에 동전의 단위가 100, 250, 300 이라면, (300 * 1) + (100 * 2) 로 3개로 거슬러주는 것보다는 250 * 2 의 방법으로 2개로 거슬러주는 것이 더 최적의 방법이다. 따라서 그리디 알고리즘은 항상 최적의 해를 제공해주는 것은 아니다. 하지만 만약 이 상황에서 큰 단위의 수부터 거슬러줘야하는 조건이 존재할 때 그리디 알..

Algorithm/BOJ

백준(BOJ) 1931번 회의실배정 [그리디(Greedy)/알고리즘/파이썬(python)]

2021.08.07

1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보..

Algorithm/BOJ

백준(BOJ) 11000번 강의실배정 [그리디(Greedy)/알고리즘/파이썬(python)/큐]

2021.08.06

11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < ..

Algorithm/PROGRAMMERS

프로그래머스 "완주하지 못한 선수" [알고리즘/해쉬/코딩테스트 연습/파이썬(python)]

2021.07.12

https://programmers.co.kr/learn/courses/30/parts/12077 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [ 문제 ] 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. [ 제한사항 ] 마라톤 경기에 참여한 선수의 수는 1명 이상 100..

Algorithm/BOJ

백준(BOJ) 1158번 요세푸스 [알고리즘/파이썬(python)/연결리스트]

2021.07.07

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net [문제] 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 ..

Algorithm/PROGRAMMERS

프로그래머스 "기능개발" [알고리즘/스택/ 큐/ 코딩테스트 연습/ 파이썬(python)]

2021.07.04

https://programmers.co.kr/learn/courses/30/parts/12081 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제] 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 ..

Algorithm/BOJ

백준(BOJ) 9012번 스택문제 [파이썬(python)]

2021.07.02

https://www.acmicpc.net/problem/9012 [문제] 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 ..

Algorithm/BOJ

백준(BOJ) 10828번 스택문제 [파이썬(python) / 시간초과 에러]

2021.06.28

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 백준 알고리즘 10828번 스택문제 [문제] 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수..

티스토리툴바