본문 바로가기
반응형

FOSCAR-(Autonomous Driving)/알고리즘 스터디

 (27)
[2025 1학기 알고리즘 스터디] 김규현 #2주차 1. 1로 만들기연산을 최소한으로 사용하여 정수 x를 1로 만드는 문제이다.3의 배수인 경우 3으로 나누기, 2의 배수이면 2로 나누기, 1을 빼주는 연산중에 선택할 수 있다. 입력된 정수를 위의 과정중 하나를 선택하여 연산하여야하는데  2의 배수나 3의 배수 둘다 아닌 경우는 1을 빼주는 것이 자명해 보인다. 3의 배수이면 3으로 나누어주는 것이 가장 좋아보인다. 1로 만드는 과정에서 수를 최대한 줄여야하는데 3가지 과정중에 3으로 나누어 주는 것이 가장 수를 작게 만드는 방법이기 때문이다. 문제는 2의 배수인 경우이다. x가 10인 경우 2로 나누어 (10 -> 5 -> 4 -> 2 -> 1) 계산하는 방법보다 (10 -> 9 -> 3 -> 1)이 최소한으로 계산하는 경우이이 때문이다. 따라서 -1을..
[2025 1학기 알고리즘 스터디] 신지은 #1주차 1. 수 정렬하기3(https://www.acmicpc.net/problem/10989)첫 번째 시도 - 실패, 그림 그리면서 열심히 했는데.. 메모리 초과 :(#includeusing namespace std;void SortFunction(int arr[], int n) { //정수 배열 정렬 for (int i = 1; i = 0 && arr[j] > k) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = k; }}int main() { int n; //몇 개의 정수를 입력할 것인지 결정 cin >> n; int* numbers = new int[n]; //정수형 포인터를 선언해서 ..
[2025 1학기 알고리즘 스터디] 1주차 박건민 1주차의 주제 정렬 알고리즘! 정렬이란 무엇인가...그래서 정렬 알고리즘에 대해 찾아봣습니다.  1. 정렬 알고리즘  종류(1) 선택 정렬 (Selection Sort)설명: 데이터 집합에서 최소값을 찾아 첫 번째 위치와 교환하고, 그 다음 최소값을 찾아 두 번째 위치와 교환하는 방식으로 정렬을 수행합니다. 이러한 과정을 반복하여 전체를 정렬합니다.특징: 구현이 간단하지만, 시간 복잡도가 O(n²)로 비효율적입니다. 안정성을 보장하지 않습니다.(2) 삽입 정렬 (Insertion Sort)설명: 데이터 집합을 순회하면서 각 요소를 적절한 위치에 삽입하여 정렬을 수행합니다. 이미 정렬된 부분과 비교하여 새로운 요소를 삽입하는 방식입니다.특징: 대부분의 요소가 이미 정렬되어 있는 경우 효율적이며, 최선의 경..
[2023 알고리즘 스터디] 2조 박주빈 5주차 - 백준 23882, 10989, 2751, 11650 FOSCAR 알고리즘 스터디 5주차 2조 블로깅 백준 23882번 : 알고리즘 수업 - 선택 정렬 2 https://www.acmicpc.net/problem/23882 23882번: 알고리즘 수업 - 선택 정렬 2 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 교환 횟수 K(1 ≤ K ≤ N)가 주어진다. 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109) www.acmicpc.net # a: 배열 크기 k: k번째 교환 a, k = map(int, input().split()) # 배열 int형으로 저장 num_list = [int(i) for i in input().split()] num_list_sorted = sorted(num..
[2023 알고리즘 스터디] 4조 이은선 5주차 - 백준 2075 우선순위 큐를 이용한 정렬 문제 입력 5 12 7 9 15 5-> 15 12 9 7 5 13 8 11 19 6-> 19 13 11 8 6 21 10 26 31 16-> 31 26 21 16 10 48 14 28 35 25-> 48 35 28 25 14 52 20 32 41 49 -> 52 49 41 32 20 다음과 같은 5X5 입력이 주어졌을 때, 5번째로 큰 수를 찾기 위해서 일단 입력 받은 줄별로 내림차순 정렬을 진행해보았다. 하지만, 5번째로 큰 수를 찾기 위해선 맨 마지막 줄에 있는 수들끼리만 비교하면 될게 아니라 필요에 따라선 그 위에 줄의 숫자도 함께 비교하며 N번째로 큰 수를 찾아나가야 한다. 그렇다고 해서 세로 방향으로는 정렬된 상태로 입력 받은 수들을 몽땅 하나의 리스트에 넣고 재정렬시..
[2023 알고리즘 스터디] 1조 정혁제 5주차 - 정렬 1. 단어정렬(1811) https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 강의를 참고하여 정렬 식을 사용해 풀어보았으나, 시간 초과의 문제로 다른 방법을 찾아보았습니다. 파이썬에 기본적으로 탑재되어있는 set, sort 함수를 이용해서 풀었습니다. 2. 수 정렬하기2(2751) https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주..
[2023 알고리즘 스터디] 3조 박제형 5주차 - 정렬 21강 선택정렬 정렬 알고리즘 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다. 선택정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] # 스와프 p..
[2023 알고리즘 스터디] 3조 선병범 4주차 - DFS & BFS 알고리즘 DFS 깊이 우선 탐색 자료라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이며 스택 자료구조를 아용한다. DFS의 구체적인 탐색 과정은 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. BFS 너비 우선 탐색 자료라고도 부르며 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이며 큐 자료 구조를 이용한다. DFS의 구체적인 탐색 과정은 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다. 2.. 큐에서 노드를 꺼낸 뒤에 해당..
반응형

티스토리툴바