본문 바로가기
반응형

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

 (24)
[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.. 큐에서 노드를 꺼낸 뒤에 해당..
[2023 알고리즘 스터디] 2조 김준명 4주차 - 백준 1388 2606 1260 11725 DFS(Depth-First Search) ○ DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. ○ DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적인 동작 과정은 다음과 같습니다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. ★더 자세한 내용은 아래의 동영상 참조 [이것이 코딩 테스트다 with Python] 18강 DFS 알고리즘 - YouTube BFS(Breadth-Fi..
[2023 알고리즘 스터디] 5조 #4주차 - DFS & BFS 알고리즘 FOSCAR 알고리즘 스터디 4주차 5조 블로깅 - 이승찬 13913 숨바꼭질 4 - 코드 리뷰 박병규 알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색 문제 링크 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS를 사용하여 풀었습니다 queue에 position과 cost값을 저장해두고 방문하지 않은 position에 대해 다음 풀이를 진행할 수 있도록 하였습니다. x-1, x+1, x..
[2023 알고리즘 스터디] 4조 변준형 4주차 - 백준 7562 BFS(Breadth First Search, 너비우선탐색) 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 탐색을 할 때 너비를 우선으로 탐색. 즉 가까운 것 위주로 탐색한다. 이러한 특징때문에 최단경로를 찾는 문제에서 주로 사용. 자료구조 큐(Queue)를 사용함. 문제링크 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제설명 나이트가 이동 가능한 좌표를 dx, dy의 형태로 만들어줍니다. 이동할 때 마다 방문 횟수에 1을 더합니..
반응형

티스토리툴바