본문 바로가기
반응형

Algorithm

[백준 11399번] ATM | 삽입 정렬(insertion sort) 알고리즘
Algorithm 2023. 8. 12. [백준 11399번] ATM | 삽입 정렬(insertion sort) 알고리즘 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다..
[백준 1427번] 소트인사이드 | 선택정렬(Selection Sort) 알고리즘
Algorithm 2023. 8. 11. [백준 1427번] 소트인사이드 | 선택정렬(Selection Sort) 알고리즘 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자. 입력 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다. 슈도 코드 1. 입력 값 N을 받는다. 2. N을 문자열로 변환하고, 리스트로 변환하여 A에 저장한다. 3. 교환 정렬(Selection Sort) 알고리즘으로 리스트 A를 내림차순으로 정렬한다. a. i를 0부터 len(A) - 1까지 범위로 반복한다. i. Max를 i로 초기화한다..
[백준 2750번] 수 정렬하기 | 버블정렬(bubble sort) 알고리즘
Algorithm 2023. 8. 10. [백준 2750번] 수 정렬하기 | 버블정렬(bubble sort) 알고리즘 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 버블 정렬의 원리 버블 정렬은 인접한 두 원소를 비교해서 오름차순으로 정렬하는 과정을 여러 번 반복하는 정렬 알고리..
[백준 11286번] 절댓값 힙 | 큐(Queue)
Algorithm 2023. 8. 9. [백준 11286번] 절댓값 힙 | 큐(Queue) 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 ..
[백준 2164번] 카드2 | 데크(deque)
Algorithm 2023. 8. 8. [백준 2164번] 카드2 | 데크(deque) 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면..
[백준 1874번] 스택 수열 | 스택(stack)
Algorithm 2023. 8. 7. [백준 1874번] 스택 수열 | 스택(stack) 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있..
[알고리즘/자료구조] 스택(stack) | 백준 10828번: 스택
Algorithm 2023. 7. 23. [알고리즘/자료구조] 스택(stack) | 백준 10828번: 스택 - 스택(stack)은 한 쪽 끝에서만 데이터를 넣고 뺄 수 있는 자료구조이다. - 이러한 스택은 입구와 출구로의 이동이 제한되는 물건 창고에 비유된다. 즉, 창고의 공간이 제한되어 있으며 입구(스택의 맨 위)로만 물건을 넣을 수 있으며, 출구(스택의 맨 위)로만 물건을 뺄 수 있다. - 이러한 것을 Last In First Out (후입선출)이라고 한다. - 데이터를 넣고 뺄 때는 별다른 제약이 없으므로, 삽입(insert) 및 삭제(delete)가 빠르게 처리된다. - 파이썬에서는 스택(stack) 자료구조를 구현하기 위해 리스트(list)를 사용한다. - 리스트(list)는 파이썬에서 가장 일반적으로 사용되는 데이터 컨테이너(container) 중 하나이며, 리스트의 끝에 데이터를 추가하거나 삭제하..
[알고리즘/파이썬] 자료구조 - 투 포인터(Two pointers) | 백준 2018번: 수들의 합 5
Algorithm 2023. 7. 22. [알고리즘/파이썬] 자료구조 - 투 포인터(Two pointers) | 백준 2018번: 수들의 합 5 투 포인터(Two Pointers) 알고리즘 - 정렬된 배열의 부분합 또는 개수 구하기 등의 문제를 해결하는 데 자주 사용되는 알고리즘이다. - 기본 아이디어는 배열의 시작과 끝에서 하나씩 시작해서, 조건에 따라 양쪽 방향으로 포인터를 이동해 문제해결한다. - 문제에서 배열에 대한 순서나 시작점이 중요하지 않다면 이 알고리즘을 사용해서 빠르게 문제를 해결할 수 있다. 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 문제 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다..
[알고리즘/파이썬] 자료구조 - 슬라이딩 윈도우(Sliding window) | 백준 12891번: DNA 비밀번호
Algorithm 2023. 7. 18. [알고리즘/파이썬] 자료구조 - 슬라이딩 윈도우(Sliding window) | 백준 12891번: DNA 비밀번호 슬라이딩 윈도우(Sliding window) - 연속된 구간에서 일정 크기의 윈도우(슬라이딩)를 이동하면서 문제를 해결하는 것 - 배열 또는 리스트 등 순차적으로 접근할 수 있는 데이터에서 사용 접근방법 1. 데이터에서 일정 크기의 구간(윈도우)을 선택 2. 구간의 초기합을 계산 3. 구간을 우측으로 이동시키며, 구간의 값을 추가하거나 제거 4. 이동되면서 구간 속 값들을 계속 합산하며, 반복되는 계산으로 결과를 도출 5. 이동범위가 오른쪽으로 끝에 닿으면 알고리즘 종료 12891번: DNA 비밀번호 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을..
[알고리즘/파이썬] 자료구조 - 구간 합(Sum of Segment), 부분 합(Partial Sum) | 백준 11659번: 구간 합 구하기 4
Algorithm 2023. 7. 16. [알고리즘/파이썬] 자료구조 - 구간 합(Sum of Segment), 부분 합(Partial Sum) | 백준 11659번: 구간 합 구하기 4 구간 합 : 합 배열을 이용해 시간복잡도를 더 줄이기위한 알고리즘 > [1, 2, 3, 4, 5] - 부분합은 1, 3, 6, 10, 15 - 1~3 구간합 : 6 (1+2+3) 2~4 구간합 : 9 (2+3+4) 3~5 구간합 : 12 (3+4+5) 합 배열 s[i] = A[0] + A[1] + A[2] + _ + A[i-1] + A[i] #A[0]부터 A[i]까지의 합 합 배열 공식 S[i] = S[i-1] + A[i] 구간 합 공식 S[j] - S[i-1] #i에서 j까지 구간 합 11659번: 구간 합 구하기 4 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 ..
[알고리즘/파이썬] 자료구조 - 배열과 리스트 | 11720번: 숫자의 합, 1546번: 평균
Algorithm 2023. 7. 14. [알고리즘/파이썬] 자료구조 - 배열과 리스트 | 11720번: 숫자의 합, 1546번: 평균 배열의 특징 : 배열은 메모리에 연속된 공간에 값이 채워져있는 형태의 자료구조 인덱스를 사용해 값에 바로 접근가능하다. (장점) 값을 삽입하거나 삭제하려면 해당 인덱스 주변값을 이동시켜야 한다. 배열의 크기는 한번 선언하면 크기를 변경할 수 없다. (단점) 리스트의 특징 : 리스트는 노드(값과 포인터를 묶음)를 포인터로 연결한 자료구조 인덱스가 없어 순서대로 값에 접근해야한다.-속도가 느리다. (단점) 포인터로 연결되어 있어 삽입삭제 속도가 빠르다. 리스트의 크기가 가변적이다. -선언할때 크기지정필요x (장점) ⚠ 파이썬에서는 배열과 리스트를 구분하지 않는다. ⚠ 파이썬의 '리스트'는 배열의 특징까지 모두 가지도록 구현됨. 위에서 언급한 (장점)만 가져왔다. 11720번: 숫자의 합 11720번: 숫자의..
[알고리즘/파이썬] 시간복잡도 | 백준 2750번: 수 정렬하기
Algorithm 2023. 7. 13. [알고리즘/파이썬] 시간복잡도 | 백준 2750번: 수 정렬하기 코딩 테스트에서의 시간복잡도 코딩 테스트에서는 빅-오(O(n))(최악의 케이스)을 기준으로 수행시간을 계산하는 것이 좋다. 시간복잡도 도출기준 상수는 계산에서 제외 가장 많이 중첩된 반복문 수행횟수가 기단복잡도의 기준 연산횟수가 N, 3N 등 이라도 상수를 무시하므로 둘 다 시간복잡도는 O(n)으로 동일하다. 그러나 이중중첩문의 N**2의 경우 시간복잡도는 변화없이 N**2으로 유지된다. 백준 2750번: 수 정렬하기 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 ..
반응형

티스토리툴바