백준 알고리즘 2750(수 정렬하기) (C++, Python) BOJ

[문제] 백준 알고리즘 2750(수 정렬하기)

삽입 정렬이나 거품 정렬을 구현하는 문제이다. (시간 복잡도 O(N^2))

삽입 정렬(insert sort)은 작은 것을 최대한 앞쪽으로 삽입하는 방식이다.

(Bold는 값 비교 후 왼쪽>오른쪽 경우 교체)
idx = 0,  5 2 3 4 1 -> 2 5 3 4 1
idx = 1,  2 5 3 4 1 -> 2 3 5 4 1 -> 2 3 5 4 1
idx = 2,  2 3 5 4 1 -> 2 3 4 5 1 -> 2 3 4 5 1 -> 2 3 4 5 1
idx = 3,  2 3 4 5 1 -> 2 3 4 1 5 -> 2 3 1 4 5 -> 2 1 3 4 5 -> [1 2 3 4 5]  

[위키백과 - 삽입 정렬의 예]

거품 정렬(bubble sort)는 큰 것을 맨 뒤로 빼면서 제외하는 방식이다.

(Bold는 값 비교 후 왼쪽>오른쪽 경우 교체)
idx = 0,  5 2 3 4 1 -> 2 5 3 4 1 -> 2 3 5 4 1 -> 2 3 4 5 1 -> 2 3 4 1 [5] 5 fix
idx = 1,  2 3 4 1 -> 2 3 4 1 -> 2 3 4 1 -> 2 3 1 [4] 4 fix
idx = 2,  2 3 1 -> 2 3 1 -> 2 1 [3] 3 fix
idx = 3,  2 1 -> [1 2]      

[위키백과 - 삽입 정렬의 예]

코드로는 ins_sort()와 bub_sort()의 함수로 구분지어서 둘 다 구현했다.


[C++]
#include <cstdio>
#include <cstring>
using namespace std;

const int MAX = 1000;
int arr[MAX], n;

void bub_sort() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i- 1; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return;
}

void ins_sort() {
for (int i = 1; i < n; i++) {
int j = i;
while (j > 0) {
if (arr[j - 1] > arr[j]) {
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
}
j--;
}
}
return;
}

int main() {
memset(arr, 0, sizeof(arr));
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
//bub_sort();
ins_sort();

for (int i = 0; i < n; i++) {
printf("%d\n", arr[i]);
}
return 0;
}

[Python]
import sys
input = sys.stdin.readline
n = int(input())
arr = [int(input()) for _ in range(n)]
def ins_sort():
for i in range(1, n):
j = i
while j > 0:
if arr[j] < arr[j-1]:
tmp = arr[j]
arr[j] = arr[j-1]
arr[j-1] = tmp
j -= 1
return

def bub_sort():
for i in range(n-1):
for j in range(n - i - 1):
if arr[j] > arr[j+1]:
tmp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = tmp
return

#bub_sort()
ins_sort()
for i in range(n):
print(arr[i])

공의의 하나님께서 Christianity


어떻게 죄악까지 

사랑하겠어, 

널 사랑하는거지. 

by Think_why (feat.악뮤)


백준 알고리즘 1956(운동) (C++, Python) BOJ

[문제] 백준 알고리즘 1956(운동)

가능한 사이클의 최소 이동 거리를 찾는 문제.

유의할 점은 도착이 끝나는 것이 아니라, 다시 제자리로 돌아오는 것.

1 -> 2 -> 1 이런 짧은 사이클도 가능하다. 경로가 없으면 -1 출력.

플로이드 와샬 알고리즘을 활용하면 된다. (11404번 문제)


[문제 해결]

1. 2차원 graph를 INF(1e9)로 초기화한 후, 노드에 거리들을 저장해준다.

2. 플로이드 와샬 알고리즘 (모든 경로를 거쳐가는 경우를 고려한 알고리즘)
  - 거쳐가는 중간 노드 i, 시작 노드 v, 도착 노드 nv의 시간 복잡도 O(V^3)
  - i와 v가 같은 경우(시작=중간) 또는 i와 nv가 같은 경우(중간=도착)은 continue로 생략
  - 중간 노드를 거쳐가는 경우가 더 거리가 짧다면 갱신

3. graph에서 시작 노드와 도착 노드가 같은 idx의 값의 min값을 출력해준다.
  - min 값이 INF라면 -1 출력


[C++]
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX = 401;
const int INF = 1e9;
int n, m;
int graph[MAX][MAX];

void print() {
int _min = INF;
for (int i = 1; i <= n; i++) {
if (_min > graph[i][i]) _min = graph[i][i];
}
if (_min != INF) printf("%d\n", _min);
else printf("-1\n");
}

void solve_fw() {
for (int i = 1; i <= n; i++) {
for (int v = 1; v <= n; v++) {
if (v == i) continue;
for (int nv = 1; nv <= n; nv++) {
if (nv == i) continue;
if (graph[v][nv] > graph[v][i] + graph[i][nv]) {
graph[v][nv] = graph[v][i] + graph[i][nv];
}
}
}
}
print();
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
graph[i][j] = INF;
}
}
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if (graph[a][b] > c) graph[a][b] = c;
}
solve_fw();
return 0;
}

[Python]
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
graph = [[1e9] * (n+1) for _ in range(n+1)]
for _ in range(m):
a, b, c = map(int, input().split())
if graph[a][b] > c:
graph[a][b] = c

def answer():
_min = 1e9
for i in range(1, n+1):
if _min > graph[i][i]:
_min = graph[i][i]
print(_min if _min != 1e9 else -1)
return

def solve_fw():
for i in range(1, n+1):
for v in range(1, n+1):
if i == v:
continue
for nv in range(1, n+1):
if i == nv:
continue
if graph[v][nv] > graph[v][i] + graph[i][nv]:
graph[v][nv] = graph[v][i] + graph[i][nv]
answer()
return

solve_fw()

이득 Christianity


영원하지 않은 

가치를 손해 보고 

영원한 가치를 

얻을 수 있다면, 

오히려 훨씬 

이득이 아닌가! 

by Think_why 


영혼 Christianity


당신에겐 영혼이 없습니다. 

당신이 영혼이에요. 

몸을 가지고 있을 뿐입니다. 

You Don't have a soul. 

You are a soul. 

You have a body. 

by C.S.Lewis 


1 2 3 4 5 6 7 8 9 10 다음