본문 바로가기
반응형

전체 글1306

버블 정렬(Bubble Sort) 특징 - O(N2) - 서로 인접한 두 원소를 비교하여 정렬 - 한 번의 탐색으로 가장 큰 원소가 맨 뒤에 위치하게 됩니다. (오름차순 기준) 시뮬레이션 구현 코드 (오름차순 기준) #include int swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void bubbleSort(int arr[], int n) { for (int i = n-1; i > 0; i--) { for (int j = 0; j < i; j++) { if (arr[j] < arr[j + 1]) { swap(&arr[j], &arr[j + 1]); } } } } void main() { int n = 10; int arr[10] = { 1, 10, 5, 8, 7, 6, 4.. 2021. 2. 24.
DFS와 BFS 비교 출처: 나무위키 경로 비교 BFS - Queue 이용 - 최소신장트리(Minimum Spanning Trees), 최단경로(Shortest Paths) 장점: 무한히 깊거나 무한에 가까운 트리인 경우에 효과적 단점: 목표 노드로 가는 경로들 모두가 같은 거리일 때 비효율적 ※ BFS (Breadth-First Search, 너비 우선 탐색) BFS (Breadth-First Search, 너비 우선 탐색) BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서 zoosso.tistory.com DFS - Stack 이용 - 백트래킹 - 사이클 탐지.. 2021. 2. 24.
[BOJ] 백준 1260 DFS와 BFS 출처: https://www.acmicpc.net/problem/1260 Input 4 5 1 1 2 1 3 1 4 2 4 3 4 Output 1 2 4 3 1 2 3 4 4개의 정점과 5개의 간선은 아래와 같은 상태입니다. DFS, BFS 방문 순서는 다음과 같습니다. [구현] ① 그래프 정보를 바탕으로 인접행렬 구현 ② 인접행렬에서 DFS, BFS 구현 Input 7 6 1 1 4 1 3 1 2 4 6 4 5 2 7 Output 1 2 7 3 4 5 6 1 2 3 4 7 5 6 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Stack; public class Main { pub.. 2021. 2. 24.
[BOJ] 백준 1427 소트인사이드 출처: https://www.acmicpc.net/problem/1427 Input 2143 Output 4321 자릿수를 정렬하는 것이므로 『0』 ~ 『9』에 해당하는 숫자를 정렬합니다. 버블정렬 이용 내림차순이므로 배열의 끝자리부터 정렬의 낮은 숫자가 배치되는 형태입니다. 버블 정렬(Bubble Sort) 특징 - O(N2) - 서로 인접한 두 원소를 비교하여 정렬 - 한 번의 탐색으로 가장 큰 원소가 맨 뒤에 위치하게 됩니다. (오름차순 기준) 시뮬레이션 구현 코드 (오름차순 기준) #include int swap(int* a, int* b zoosso.tistory.com import java.util.Arrays; import java.util.Scanner; public class Main {.. 2021. 2. 24.
[SWEA] 8825 홀수 중간값 피라미드2 출처: SWEA Input 2 4 1 6 3 7 4 5 2 2 3 1 2 Output #1 4 #2 2 #include #include using namespace std; int n, arr[200000]; bool cmp(int x, int mid) { return x >= mid; } bool judgeUpDown(int mid) { for (register int i = 1; i > testCase; for (int tc = 1; tc > n; for (int i = 1; i > arr[i]; int left = 1, right = 2 * n - 1, answer = 1; while (left > 1; if (judgeUpDown(mid)) { answer = mid; left = mid + 1;.. 2021. 2. 24.
[SWEA] 5642 합 출처: SWEA Input 1 5 1 3 -8 18 -8 Output #1 18 모든 원소가 음수인 경우 주의해야 한다. Input 1 5 -5 -4 -3 -2 -1 Output #1 -1 ※ 유사문제 풀이: [BOJ] 1912 연속합 [BOJ] 백준 1912 연속합 출처: https://www.acmicpc.net/problem/1912 Input 10 10 -4 3 1 5 6 -35 12 21 -1 Output 3 배열의 연속된 부분합을 구하는 문제입니다. ① 중첩 for문을 이용하면 시간초과. ② 모든 원소가 음수일 때,.. zoosso.tistory.com #include using namespace std; int arr[100000]; #define MIN -1001 int main() { i.. 2021. 2. 24.
[SWEA] 8016 홀수 피라미드 출처: SWEA Input 3 1 2 3 Output #1 1 1 #2 3 7 #3 9 17 1..N층에서 좌/우측에 놓여지는 수식은 아래와 같다. left = (N - 1) * (N - 1) * 2 + 1; right = N * N * 2 - 1; #include using namespace std; typedef unsigned long long ull; int main() { ios_base::sync_with_stdio(0); cin.tie(0); ull N, left, right; int testCase; cin >> testCase; for (int tc = 1; tc > N; left = (N - 1) * (N - 1) * 2 + 1; right = N * N * 2 - 1; // 정답 출력.. 2021. 2. 24.
[SWEA] 8822 홀수 중간값 피라미드 1 출처: SWEA Input 2 4 4 2 1 Output #1 1 #2 0 N층에 적혀질 수 있는 숫자는 1층에서 1~2N-1 사이에 있는 중간값들 중 하나입니다. 따라서 적혀질 수 없는 숫자는 1과 2N-1 숫자입니다. #include using namespace std; int N, X, answer; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int testCase; cin >> testCase; for (int tc = 1; tc > N >> X; if (X == 1 || X == 2 * N - 1) answer = 0; else answer = 1; // 정답 출력 printf("#%d %d\n", .. 2021. 2. 24.
[SWEA] 9317 석찬이의 받아쓰기 출처: SWEA Input 2 16 MyNameIsSeokChan mynameisseokchan 15 SamsungSoftware MembershipZzang Output #1 11 #2 2 두 문자열을 받아서 대소문자를 구분하여 다른 문자인지 확인 #include using namespace std; int main() { int testCase; cin >> testCase; int len, answer; char A[100001], B[100001]; for (int tc = 1; tc > len; scanf("%s", A); scanf("%s", B); answer = 0; // 일치하는 문자 수 확인 for (int i = 0; i < len; i++) { if (A[i] == B[i]) ans.. 2021. 2. 24.
[BOJ] 백준 2667 단지 번호 붙이기 출처: https://www.acmicpc.net/problem/2667 Input 7 0110100 0110101 1110101 0000111 0100000 0111110 0111000 Output 3 7 8 9 총 3개의 단지가 존재하며, 각 단지의 집의 수는 7, 8, 9개 입니다. BFS 알고리즘을 이용해 배열을 순회하며 연결된 집을 처리. import java.util.Collections; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Stack; class House{ int x,y; int number; public House(int x, int y, int numb.. 2021. 2. 24.
반응형

티스토리툴바