꾸준히 개발하기

https://www.acmicpc.net/problem/2609

이번 기회에 파이썬에서 사용 가능한 최대공약수(gcd), 최소공배수(lcm) 구하는 방법을 다 정리해보았다.

가장 베이직한 방법

최대공약수 : 숫자 x,y 중 더 작은 숫자부터 1까지 -1 해가며 x%i == 0 and y%i == 0인 숫자 찾기

최소공배수 : 숫자 x,y 중 더 큰 숫자부터 (x*y)까지 +1 해가며 i%x == 0 and i%y == 0인 숫자 찾기

유클리드 호제법

x,y의 gcd는 y와 r의 gcd와 같다. ( x%y = r)

즉 계속해서 x의 자리에 y값을 대입하고, y에는 x%y 값인 r을 대입하면 x%y == 0 인 순간의 y값이 바로 gcd이다.

최소공배수는 x*y를 위에서 구한 gcd로 나눠주면 된다.

라이브러리 활용

이게 사실 제일 편하다..^^ 파이썬의 math 라이브러리는 인자를 심지어 여러개 받을 수 있는 최대공약수, 최소공배수를 구해주는 함수를 제공한다.

math 라이브러리를 import 해주고 math.gcd( 인자, 인자, ... ) math.lcm( 인자, 인자 ,... ) 해주면 된다.

코드는 다음과 같다.

n, m = map(int, input().split())

# 가장 베이직한 방법
def getGCD_basic(x, y):
    for i in range(min(x, y), 0, -1):
        if x % i == 0 and y % i == 0:
            return i


def getLCM_basic(x, y):
    for i in range(max(x, y), (x * y) + 1):
        if i % x == 0 and i % y == 0:
            return i


# 유클리드 호제법
def getGCD_euclid(x, y):
    while y:
        x, y = y, x % y
    return x


def getLCM_euclid(x, y):
    return (x * y) // getGCD_euclid(x, y)


# 파이썬 라이브러리 활용
import math

print(math.gcd(n, m))
print(math.lcm(n, m))

유클리드 호제법은 정말... 정말 오랜만에 다시 들여다봤다...^^ 수학을 열심히 했던 학생이었는데 이렇게까지 싸그리 까먹을 수 있다니 슬프다. 안 좋은 일이나 빨리 까먹지 이런 수학적 지식만 홀라당 다 까먹어 버렸다.

10.7부터 week1을 달리고 있다.

https://www.acmicpc.net/workbook/view/8997

백준 15649 N과 M (1)

N과 M문제는 자다가도 풀 수 있어야 한다고 해서 순열로 풀었다가 눈물 좍좍 흘리면서 백트래킹을 뿌셨다.

백트래킹은 불필요한 경우를 탐색하지 않는다. 즉 특정 조건에서는 탐색을 그만하고 뒤로 되돌아가는(back) 성질을 가지고 있다. 따라서 DFS로 무작정 들이박으면 시간초과가 나는 상황에 유용하게 쓰이겠다.

숫자 1~N까지 중복 없는 M개의 요소를 가진 수열을 구하는 문제이다.

따라서 1) 수열의 길이가 M을 넘으면 안됨 2) 배열 내에 중복 X 두 가지 조건을 만족하는 숫자 뽑기를 진행하면 된다.

ex. N = 4, M = 3

1. 첫번째 숫자로 1,2,3,4 중 가장 작은 숫자인 1을 선택한다. -> for 문으로 순차 증가
2. 두번째 숫자로 2,3,4 중 가장 작은 숫자인 2를 선택한다. -> 선택 과정에서 배열 안에 존재하는지 체크하여 중복 제거
3. 세번째 숫자로 3,4 중 가장 작은 숫자인 3을 선택한다.
4. 수열의 길이가 M(3)이 되었으므로 다시 단계 3로 돌아간다. -> 재귀 탈출
5. 세번째 숫자로 4를 고른다. 
6. 수열의 길이가 M(3)이 되었으므로 단계 2로 돌아간다.
7. 두번째 숫자로 다음 작은 숫자인 3를 선택한다.
8. 세번째 숫자로 2,3,4 중 2를 선택한다. -> 추후 여기에서 다시 숫자를 고를 때 3은 이미 배열안에 존재하므로 X
9. ... 반복

즉 위의 과정을 코드로 구현하면 다음과 같다. 

n, m = map(int, input().split())
result = []

def backTracking():
    # 수열의 길이가 m이면 출력해주고 전단계로 돌아가기 (재귀 탈출)
    if len(result) == m:
        print(" ".join(map(str, result)))  # "구분자".join(리스트)
        return
    # 1 ~ n 까지 체크
    for i in range(1, n + 1):
        # 중복 체크
        if i not in result:
            result.append(i)
            backTracking()
            # return 문으로 돌아온 경우 실행되는 부분
            result.pop()  # n=4, m=3일때 1,2,3이 들어온 경우 3을 없앰으로써 전단계로 돌아감


backTracking()

백트래킹 어렵다. 재귀라서 더 어렵게 느끼는 것 같기도 하고...! 익숙해질때까지 킵고잉이다 정말

출력 관련해서 문자열 다룰 때 자주 쓰이는 함수 join도 짚고 가보자.

"구분자".join(리스트) 형태로 사용하며 join 함수는 매개변수로 들어온 리스트에 있는 요소 하나 하나를 합쳐서 하나의 문자열로 바꿔 반환하는 함수이다. "구분자"를 값과 값 사이에 넣어서 하나의 문자열로 합쳐준다!

파이썬이 문자열 다룰 때 깡패인 언어인 만큼 join함수에도 익숙해지자. 자주 써야된다~!

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1

6 5 
1 2 
2 5 
5 1 
3 4 
4 6

예제 출력 1

2

DFS를 이용한 풀이 (python)

#백준 11724 DFS
import sys
sys.setrecursionlimit(10000)

def dfs(start):
    if(visited[start]):
        return
    visited[start] = True
    for node in adj[start]:
        if not visited[node]:
            dfs(node)


N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
cnt = 0

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)


for node in range(1, N+1):
    if not visited[node]:
        dfs(node)
        cnt +=1


print(cnt)

BFS를 이용한 풀이 (python)

#백준 11724 BFS
from collections import deque

def bfs(start):
    visited[start] = True
    queue.append(start)
    while queue:
        x=queue.popleft()
        for i in range(len(adj[x])):
            y=adj[x][i]
            if not visited[y]:
                visited[y] = True
                queue.append(y)


N,M=map(int,input().split(' '))
adj = [ [] for _ in range(N+1)]
visited = [False] * (N+1)
queue = deque()
cnt = 0

for _ in range(M):
    x, y = map(int, input().split(' '))
    adj[x].append(y)
    adj[y].append(x)


for node in range(1,N+1):
    if not visited[node]:
        bfs(node)
        cnt+=1

print(cnt)

대부분 DFS를 통해 구현하던데, 그 이유는 알겠다. BFS로 구현하는게 더 귀찮더라...ㅎㅎ

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 test case의 수가 주어진다. 각 test case에 대해서 문서의 수 N(100이하)와 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue의 어떤 위치에 있는지를 알려주는 M(0이상 N미만)이 주어진다. 다음줄에 N개 문서의 중요도가 주어지는데, 중요도는 1 이상 9 이하이다. 중요도가 같은 문서가 여러 개 있을 수도 있다. 위의 예는 N=4, M=0(A문서가 궁금하다면), 중요도는 2 1 4 3이 된다.

출력

각 test case에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

예제 입력 1

3
1 0
5
4 2
1 2 3 4
6 0
1 1 9 1 1 1

예제 출력 1

1
2
5

무작정 우선순위 큐를 쓰려고 해서 살짝 헤맸던 문제였다. 우선순위 큐는 값을 넣자마자 알아서 정렬이 되어버려서 문제 내의 '중요도가 맞지 않는 문서의 경우 큐의 맨 뒤로 이동한다'는 조건에 부합하지 않았다. 그렇다고 큐만 써서 문제를 풀자니 가장 우선순위가 높은 문서를 매번 체크해주기 귀찮아서 우선순위 큐, 일반적인 큐 두 가지를 모두 사용하여 문제를 풀었다. 

queue는 입력받은 문서가 원래 몇번째 자리에 있었는지 위치값을 함께 저장해주기 위해 pair<int,int>를 사용하였다. first 값이 value(중요도), second값이 pos(위치)이다.

함수로는 전체 입력을 받는 input()함수, 우선순위를 고려하여 큐에서 pop하고 최종 인쇄 순서를 반환하는 solve() 함수, queue와 prioirty queue를 초기화해주는 clear() 함수 세 개를 정의하였다. 자세한 설명은 코드에 주석으로 달아놓았다. 

* 큐를 초기화해줄때 일반적으로 전체를 순회하며 pop()을 해줘 초기화를 하는 경우가 많은데, 스택 오버플로우에 좀 더 나은 초기화 방법이 있어 clear() 함수는 해당 방법을 사용하였다. 메모리 해제도 해주고 초기화도 해주는 좋은 방법인 것 같다. 

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int TC, N, M, cnt;
queue <pair <int, int>> q;
priority_queue <int> pq;
queue <int> ans;

void input() {
	int val = 0;
	for (int i = 0; i < N; i++) {
		cin >> val;
		q.push(make_pair(val, i));
		pq.push(val);
	}
}

int solve() {
	cnt = 0;
	int val, pos = 0;
	while(!pq.empty()) {
		// 맨 앞 원소가 우선순위인 경우
		if (pq.top() == q.front().first) {
			// 뽑을 원소가 M번째 원소인 경우
			if (q.front().second == M) {
				cnt++;
				return cnt;
			}
			// 뽑아줌
			pq.pop(); q.pop();
			cnt++;
		}
		// 맨 앞 원소가 우선순위가 아닌경우
		else {
			val = q.front().first;
			pos = q.front().second;
			q.pop(); q.push(make_pair(val, pos));
		}
	}
	return cnt;
}

// q, pq 초기화
void clearQ(queue<pair<int, int>>& q) {
	queue<pair<int, int>> empty;
	swap(q, empty);
}
void clearPQ(priority_queue<int>& pq) {
	priority_queue<int> empty;
	swap(pq, empty);
}
void clear() {
	clearQ(q);
	clearPQ(pq);
}

int main() {
	cin >> TC;

	for (int i = 0; i < TC; i++) {
		cin >> N >> M;
		input();
		ans.push( solve() );
		clear();
	}

	while (!ans.empty()) {
		cout << ans.front() << endl;
		ans.pop();
	}

	return 0;
}

사실 내 코드가 좋은 코드라고는 말하기 어렵다. 애초에 너무 알고리즘 공부를 안했다ㅠㅠ 기록용으로 남기는 코드이니 참고만 하길 바란다.