곽의 개발 blog

코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

cnt = 0

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

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

print(cnt)

처음에는 최대로 연결되는 개수라고 이해를 했는데

이 문제에서 말하는 연결 요소는 연결되어 있는 그래프의 개수 나 영역의 개수였다.

DFS/BFS를 한 번 수행했을 때 방문되는 모든 노드를 묶어서 하나의 연결 요소라고 할 수 있다.

따라서 DFS/BFS가 수행되는 횟수가 연결 요소의 개수가 된다.

모든 노드를 순차적으로 방문하면서 아직 방문되지 않은 노드에 대해서

DFS/BFS를 실행하는 과정이 for문이다.

DFS/BFS가 한 번 끝날 때마다 cnt+1을 하게 되면 연결 요소의 개수를 구할 수 있다.

처음에 런타임 에러 (RecuresionError)가 떴다.

RecursionError는 재귀와 관련된 에러이다. 가장 많이 발생하는 이유는 파이썬이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때이다.

파이썬이 정한 최대 깊이는 sys.getrecursionlimit()을 통해 확인할 수 있다.

백준의 채점 서버에서 이 값은 1000으로 되어 있다.

파이썬이 정한 최대 재귀 깊이를 변경하여 에러를 해결하였다.

sys.setrecursionlimit(10**6)

이 함수를 사용하면 소스의 최대 재귀 깊이를 1,000,000 정도로 크게 설정할 수 있다.

import sys
input = sys.stdin.readline

n = int(input())
endPoint = 0
answer = 0
lectures = []

for i in range(n):
    a, b = map(int, input().split())
    lectures.append([a,b])

lectures.sort(key = lambda x: (x[1], x[0]))

for start, end in lectures:
    if endPoint <= start:
        answer += 1
        endPoint = end
print(answer)

끝나는 시간을 기준으로 배열을 정렬하고

현재 채택된 강의가 끝나는 시간 <= 그 다음 회의 시작 시간 인지를 검사한 후

조건을 만족하면 강의를 추가하고 끝나는 시간을 갱신하도록 구현하였다.

2차원 배열 정렬

* 첫 번째 값으로 정렬하기

array.sort(key=lambda x:x[0])

x:x[0] 으로 0번째 즉 배열에서 첫번째 인덱스에 대해서 정렬시켰다.

여기까지만 하면 0번째 인덱스에 대해서 오름차순 정렬이 되지만

동일한 0번째 인덱스를 가진 1번째 인덱스에 대해서는 정렬이 되지 않는다.

둘 다 오름차순 정렬이 되길 원한다면,

array.sort(key=lambda x: (x[0], x[1]))

요렇게 해줘야 함

*두 번째 값으로 정렬하기

x: () 괄호 안에 튜플 형식으로 집어넣는다.

- 를 앞에 붙이면 역으로 즉 내림차순으로 정렬시킬 수 있다.

array.sort(key=lambda x: (-x[1], x[0]))

요렇게 하면 첫번째 인덱스 요소들에 대해 내림차순으로 정렬하고,

동일한 첫번째 인덱스를 가진 요소들에 대해서는

0번째 요소들을 기준으로 오름차순으로 정렬한다.

마침 동아리 과제에서 C#으로 실버1 이상 문제 푸는 게 있어서 C#으로도 풀어봤다.

using System;

class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int endPoint = 0;
        int answer = 0;
        int[][] lectures = new int[n][];

        for (int i = 0; i < n; i++)
        {
            string[] input = Console.ReadLine().Split();
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            lectures[i] = new int[] { a, b };
        }

        Array.Sort(lectures, (x, y) => {
            if (x[1] == y[1]) return x[0].CompareTo(y[0]);
            return x[1].CompareTo(y[1]);
        });

        foreach (int[] lecture in lectures)
        {
            int start = lecture[0];
            int end = lecture[1];
            if (endPoint <= start)
            {
                answer++;
                endPoint = end;
            }
        }
        Console.WriteLine(answer);
    }
}

문제

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

 

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

코드

import sys
input = sys.stdin.readline

n = int(input())
solution = [0]*(n+1)

if n == 1:
    print(1)
elif n == 2:
    print(2)
else:
    solution[1] = 1
    solution[2] = 2
    for i in range(3, n+1):
        solution[i] = (solution[i-1] + solution[i-2]) % 10007
    print(solution[n])

2 x N 크기의 직사각형을 채울 수 있는 방법의 수는

2 x ( N-2 ) 크기의 직사각형을 채우는 경우의 수에 1 x 2 크기의 직사각형 2개를 붙이는 경우

+

2 x ( N-1 ) 크기의 직사각형을 채우는 경우의 수에 2 x 1 크기의 직사각형 1개를 붙이는 경우

이다.

코드

import sys
from collections import Counter
input = sys.stdin.readline

n = int(input())
for _ in range(n):
    k = int(input())
    arr = []
    result = 1
    for _ in range(k):
        item, type = input().split()
        arr.append(type)
    cnt = Counter(arr)
    for item in cnt:
        result *= (cnt[item]+1)
    print(result-1)

의상의 이름과 종류를 입력 받는다.

사실 의상의 이름은 중요하지 않고 종류에 따라 개수를 세는 것이 더 중요하다.

따라서 입력을 받은 후 의상의 종류만 배열에 따로 저장하였고,

개수를 세기 위해 입력을 저장해놓은 배열을 다시 Counter함수에 입력하였다.

경우의 수는

의상마다

(의상의 종류의 개수 + 1(안 입는 것)) 의 경우의 수를 곱하고

최종적으로 아무것도 입지 않는 경우의 수 1을 뺀 값을 출력한다.

예를 들어

주어진 예제 첫번째 케이스에서

headgear 2가지, eyewear 1가지를 입력 받았기 때문에

최종 result 값은

( 2 + 1 ) * ( 1 + 1 ) = 6

에서 아무것도 입지 않는 경우 1을 뺀 5가 출력값이 된다.

코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
value = []
for _ in range(n):
    value.append(int(input()))
value.sort(reverse=True)

cnt = 0
for i in value:
    if k == 0:
        break
    cnt += k//i
    k %= i

print(cnt)

가장 큰 단위부터 나누기 위해 동전의 값을 저장해둔 리스트를 내림차순으로 다시 정렬하였다.

몫은 cnt변수에 더하고, 나눠진 나머지를 다시 k에 저장한다.

k가 0이 될 때까지 반복한다.

예를 들어 4200원일 때

1000원으로 나누면 몫은 4가 되고 나머지는 200이 된다.

따라서 4는 cnt 변수에 추가하면 되고

나머지 200은 다음으로 나눠지는 단위 100으로 나눈다.