선택은 나의 것

문제 BOJ 2178 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 접근 BFS를 통해 간단히 답을 구할 수 있다. 이때 임의의 칸(x, y)에 도착하는 가장 빠른 길이 아니라면 더이상 진행하지 않는 것이 시간을 줄이는 관건이다. 이는 visit 배열을 만들어 관리해 줄 수 있다. 코드 from collections import deque n, m = map(int, input().split()) miro = [] for i in range(n): s = input() ..

문제 BOJ 2799 : https://www.acmicpc.net/problem/2799 2799번: 블라인드 문제 봄이 오고 있다. 해는 높이 떠서 환하게 빛나고 있다. 사람들은 햇볕을 가리기 위해 블라인드를 내린다. 상근이는 이웃들이 무엇을 하는지를 염탐하고, 이것에 대해서 뒷담화를 하는 주부�� www.acmicpc.net 접근 나는 아파트의 상태를 한 줄씩 입력받아 그 줄에서 펼쳐진 블라인드의 개수('*'의 수 / 4)를 확인했다. 아파트는 제일 위의 벽('######')상태가 있고 그 밑으로 4칸 동안 창문의 상태가 주어지는데 이는 현재 줄의 번호를 5로 나눈 나머지 값으로 창문의 몇 번째 줄인지를 확인했다. (그래야 블라인드가 몇 칸이나 펼쳐져 있는지 알 수 있기 때문) 만약 이전 줄과 다음..

문제 BOJ 1822 : https://www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1≤n(A), n(B)≤500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소가 www.acmicpc.net 접근 나는 인덱스의 값을 비교해 보며 두 값이 다르면 정답 배열인 ans에 추가해주고 같다면 인덱스값만 올려주고 넘어가는 식으로 구현했다. 코드를 보면 단순하고 직관적이어서 빠르게 이해가 갈 것이다. 나는 python 초보라 이렇게 풀었지만 사실 python의 set을 이용하면 훨씬 손쉽게 차집합을 구할 수 있다. ex) set_a - set..

퀵 정렬(Quick Sort) 비교 방식 알고리즘(Comparisons Sorting Algorithm) 퀵 정렬은 특정한 값인 피벗(Pivot)을 기준으로 큰 숫자와 작은 숫자를 구분하여 정렬한다. 퀵 정렬은 Sorting 알고리즘 중에 가장 빠르다고 하여 Quick이라는 이름이 붙여졌지만, Worst Case에서는 그렇지 않다. 퀵 정렬은 분할 정복 알고리즘을 이용하며 시간 복잡도는 평균 O(N * logN) 이지만 Worst Case에서는 O(n^2)의 시간복잡도를 갖는다. #include #include using namespace std; vector arr = {2, 8, 1, 3, 6, 4, 7, 5, 9}; void quickSort(int start, int end) { if (start..

삽입 정렬(Insertion Sort) 비교 방식 알고리즘(Comparisons Sorting Algorithm) 삽입 정렬은 앞의 원소보다는 크고, 뒤의 원소보다는 작은 위치에 데이터를 삽입하는 방식이다. 삽입 정렬의 시간 복잡도는 O(n^2)이다. #include #include using namespace std; int main() { // ex vector arr = {9, 2, 7, 3, 1}; // 삽입 정렬 for (int i = 1; i = 0 && arr[j] > save; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = save; } // ..

선택 정렬(Selection Sort) 비교 방식 알고리즘(Comparisons Sorting Algorithm) 선택 정렬은 정렬하고자 하는 배열을 선형 탐색해서 최솟값을 찾아 가장 앞의 데이터와 교환해 나가는 방식이다. 따라서 시간 복잡도는 O(n^2)이다. 이는 간단하게 구현할 수 있지만, 비효율적이라는 단점이 있다. #include #include #include using namespace std; int main() { // ex vector arr = {9, 2, 7, 3, 1}; //선택 정렬 for (int i = 0; i < arr.size(); i++) { int minn = arr[i]; int index = i; for (int j = i + 1; j < arr.size(); j+..