#include <iostream>
using namespace std;
int main(void){
int i, j, tmp;
int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9};
for(i=0;i<10;i++){
for(j=0;j<9-i;j++){ // i for문이 1번 반복될 때마다 가장 마지막 위치의 원소는 채워지기 때문에 idx 9-i까지만 확인
if(arr[j] > arr[j+1]){
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
for(i=0;i<10;i++){
cout << arr[i] << " ";
}
return 0;
}
출력
1 2 3 4 5 6 7 8 9 10
시간 복잡도
10 + 9 + 8 + ... + 1
= 10 * (10 - 1) / 2
= N * (N - 1) / 2
= O(N^2)
실제로 실행시켜보면 Bubble Sort가 Selection Sort보다 더 느리게 작동한다. : Bubble Sort는 당장 옆에 있는 것과 비교해 자리를 바꾸는 연산을 수행하며, 자리를 바꾸는 연산은 총 3번의 연산을 필요로 하기 때문에 컴퓨터가 실질적으로 수행해야하는 명령어가 더 많기 때문이다. 반면에 선택 정렬은 가장 작은 수를 찾아 마지막에 한 번만 자리를 바꾸는 연산을 수행한다.
티어 : Silver 3 시간 제한 : 1 초 메모리 제한 : 128 MB 알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론
문제
2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.
출력
1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.
예제 입출력
우선 알고리즘은 각 자릿수가 1로 이루어진 숫자로 n이 나누어 떨어질 때까지 확인하는 방식을 이용했다.
처음에는 각 자릿수가 1로 이루어진 숫자를 만들기 위해 문자열을 이용했다.
num이라는 string형 변수를 하나 만들어 n으로 나누어떨어지지 않으면 '1'을 추가해주는 방식으로 아래와 같이 구현했다.
#include <iostream>
#include <string>
using namespace std;
int cal_len(long long n){
string num = to_string(n);
return num.length();
}
long long ispossible(int n){
// n의 길이 계산
int len = cal_len(n);
string num;
// n의 길이만큼 1로만 구성된 문자열 만들기
for(int i=0;i<len;i++){
num += '1'; // O(n)으로 동작
}
while(true){
// num이 n의 배수인지 확인
if(num%n==0) return num.length();
// num 한 자리 추가
num += '1';
}
return -1;
}
int main(void){
int n;
while(true){
cin >> n;
if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
cout << ispossible(n) << "\n";
}
return 0;
}
하지만 런타임 에러(out_of_range)로 실패 ㅠ
num += '1';의 연산이 O(n)으로 동작하기 때문에 연산량이 너무 많기 때문이다.
그래서 num 변수를 long long형으로 선언해 동일한 알고리즘을 사용했다.
#include <iostream>
using namespace std;
long long ispossible(int n){
int cnt=1;
long long num=1;
while(true){
// num이 n의 배수인지 확인
if(!(num%n)) return cnt;
// num 한 자리 추가
num = num*10+1;
cnt++;
}
return -1;
}
int main(void){
int n;
while(true){
cin >> n;
if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
cout << ispossible(n) << "\n";
}
return 0;
}
하지만 이 방법도 동일하게 런타임 에러(out_of_range)가 났다.
결과적으로 런타임 에러의 원인은 num이 너무 커지는 것이었는데, num을 줄이기 위해 Moduler(%) 연산을 이용했다.
Algorithm
Brute Force 1. num(long long형)에 1로 이루어진 숫자를 하나씩 담음 2. num이 n으로 나누어 떨어지는지 확인 2-1. 나누어떨어지면 num의 길이 return 2-2. 나누어떨어지지 않으면 num의 길이 증가 (num = num*10 + 1 연산) → 이 때 moduler 연산(num%=n)을 이용해 num의 크기 줄여주는 것이 이 문제의 핵심 !
Code
#include <iostream>
using namespace std;
long long ispossible(int n){
int cnt=1;
long long num=1;
while(true){
// num이 n의 배수인지 확인
if(!(num%n)) return cnt;
// num의 크기 줄여주기
num%=n;
// num 한 자리 추가
num = num*10+1;
cnt++;
}
return -1;
}
int main(void){
int n;
while(true){
cin >> n;
if(cin.eof()) break; // cin.eof(): EOF이면 입력이 취소되고 true 반환
cout << ispossible(n) << "\n";
}
return 0;
}
티어 : Silver 1 시간 제한 : 1 초 메모리 제한 : 256 MB 알고리즘 분류 : 그래프 이론, 그래프 탐색, 플로이드-워셜
문제
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.
출력
총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.
예제 입출력
Algorithm
DFS 1. 그래프 구현 2. DFS 돌면서 갈 수 있는 곳 리스트에 저장 3. 리스트에 들어있는 곳에 맞게 1로 변경
Code
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
def dfs(x):
global idx
# 현재 노드에 방문한 적 있는지 확인
if visited[x]:
return False
# 방문 기록
# dfs를 첫 번째 수행하는 경우가 아닐 때만 수행
if x != idx or (nodes and x == idx):
visited[x] = True
nodes.append(x)
# 인접 노드 방문
for next_node in graph[x]:
dfs(next_node)
return True
def set_answer(i):
for j in nodes:
answer[i][j] = 1
N = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]
answer = [[0 for _ in range(N)] for __ in range(N)]
# 그래프 구현
graph = [[] for _ in range(N+1)]
for i in range(N):
for j in range(N):
if matrix[i][j] == 1:
graph[i].append(j)
# 모든 정점 DFS 돌기
for idx in range(N):
nodes = []
visited = [False for _ in range(N+1)]
if dfs(idx):
# set answer
set_answer(idx)
for i in range(N):
print(' '.join(map(str, answer[i])))
티어 : Silver 1 시간 제한 : 2 초 메모리 제한 : 128 MB 알고리즘 분류 : 그리디 알고리즘
문제
0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.
행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)
입력
첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.
예제 입출력
Algorithm
구현 - Simulation 1. 다른 숫자인 곳을 왼쪽 위 지점으로 잡고 연산 2. 모두 변환 후 A와 B가 동일한지 비교
Code
# [x][y]의 위치의 값이 같은지 다른지 확인
def is_same(x, y):
if A[x][y] != B[x][y]:
return False
else:
return True
# [x][y]의 위치의 값을 변경
def change(x, y):
# [x][y]부터 3x3이 범위를 벗어나면 for문 들어가지 않음
if x+3 > N or y+3 > M:
return False
for xx in range(x, x+3):
for yy in range(y, y+3):
# 0이면 1로 변경
if A[xx][yy] == 0:
A[xx][yy] = 1
else:
A[xx][yy] = 0
return True
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = [list(map(int, input().rstrip())) for _ in range(N)]
B = [list(map(int, input().rstrip())) for _ in range(N)]
answer = 0
for x in range(N):
for y in range(M):
# 다른 숫자인 곳이 있으면
if not is_same(x, y):
# 해당 위치부터 3x3 만큼 연산
if change(x, y):
answer += 1
# A와 B가 같으면 answer 출력
if A==B:
print(answer)
# 같지 않으면 -1 출력
else:
print(-1)
티어 : Silver 1 시간 제한 : 1 초 (추가 시간 없음) 메모리 제한 : 512 MB 알고리즘 분류 : 자료 구조, 그리디 알고리즘, 우선순위 큐
문제
석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!
아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.
x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.
이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.
아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.
입력
첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.
두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai≤ 1,000,000)
출력
첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.
예제 입출력
Algorithm
구현 1. 숫자 오름차순 2. 가장 맨 앞 두 숫자 더한 값으로 대체 3. 1과 2를 m번 반복
Code
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
cards = list(map(int, input().split()))
for count in range(m):
# 숫자 오름차순
cards.sort()
cards[0], cards[1] = cards[0]+cards[1], cards[0]+cards[1]
print(sum(cards))
