졍's 기술 블로그

단지번호붙이기

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 너무 우선 탐색, 깊이 우선 탐색

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입출력

Algorithm

BFS
1. 그래프 구현
2. 단지에 포함되어있고(graph[x][y] == 1), 방문한 적이 없다면(not visited[x][y]) bfs 수행
-> 이 때 home_cnt 라는 리스트에(각 단지의 아파트 개수) 마지막 원소(0) append
3. bfs 수행하면서 아파트 하나씩 만날 때 마다 home_cnt의 마지막 원소 증가
4. bfs 수행 완료 후 home_cnt의 마지막 원소가 0인 경우(시작 위치 제외하고 만난 아파트가 없는 경우) manually 1 증가
5. home_cnt 리스트 sort 후 length, 원소 하나씩 출력

Code

from collections import deque
queue = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(graph, sx, sy, visited):
    queue.append((sx, sy))

    while queue:
        x, y = queue.popleft()

        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]

            # graph 벗어나면 continue
            if nx < 0 or nx > N-1 or ny < 0 or ny > N-1:
                continue

            # 0이면 continue
            if not graph[nx][ny]:
                continue

            # 방문한 적 있으면 continue
            if visited[nx][ny]:
                continue

            # 방문 기록
            cnt_home[-1] += 1
            visited[nx][ny] = True
            queue.append((nx,ny))
    
N = int(input())
graph = []
for i in range(N):
    graph.append(list(map(int, input())))

cnt_home = []
visited = [[False for _ in range(N)] for _ in range(N)]
for x in range(N):
    for y in range(N):
        queue.clear()
        if graph[x][y] and not visited[x][y]:
            cnt_home.append(0)
            bfs(graph, x, y, visited)
            if not cnt_home[-1]:
                cnt_home[-1] += 1

cnt_home.sort()
print(len(cnt_home))
for i in cnt_home:
    print(i)

메모리: 34184 KB
시간: 64 ms

미로 탐색

티어 : Silver 1
시간 제한 : 1 초
메모리 제한 : 192 MB
알고리즘 분류 : 그래프 이론, 그래프 탐색, 너비 우선 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입출력

Algorithm

BFS
1. 그래프 구현
2. BFS 돌면서 문제 조건에 따라 갈 수 없는 곳이 아니라면 큐에 모두 추가
3. 도착지점에 도착하면 이동 횟수 return

Code

from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(graph, sx, sy, ex, ey, visited):
    queue = deque()
    queue.append((sx, sy))

    while queue:
        x, y = queue.popleft()

        for dir in range(4):
            nx = x + dx[dir]
            ny = y + dy[dir]

            # 도착지에 도착하면 return
            if nx == ex and ny == ey:
                return visited[x][y] + 1
            
            # graph 밖으로 나가면 continue
            if nx < 0 or nx > N-1 or ny < 0 or ny > M-1:
                continue

            # 방문한 적 있으면 continue
            if visited[nx][ny]:
                continue

            # 0이면 continue
            if not graph[nx][ny]:
                continue

            # 방문 기록
            visited[nx][ny] = visited[x][y] + 1
            queue.append((nx, ny))

N, M = map(int, input().split())

graph = []
visited = [[0 for _ in range(M)] for _ in range(N)]
for _ in range(N):
    graph.append(list(map(int, input())))

print(bfs(graph, 0, 0, N-1, M-1, visited)+1)

메모리: 34168 KB
시간: 76 ms

약수

티어 : Bronze 1
알고리즘 분류 : 수학, 정수론

약수 짝끼리의 곱은 N이 된다는 성질을 이용했다.

e.g., 8의 약수 = {1, 2, 4, 8}

         → 1 * 8 = 8

         → 2 * 4 = 8

따라서 진짜 약수를 모두 벡터에 담은 후 벡터를 오름차순 정렬하면 벡터의 첫 번째 요소와 마지막 요소는 약수 짝이 될 것이므로 두 값을 곱한 값이 N이 된다.

Algorithm

1. 입력받은 진짜 약수를 모두 vector에 담음
2. 벡터를 오름차순 정렬해 약수끼리 짝이 맞을 수 있도록 함
3. 벡터의 첫 번째 요소와 마지막 요소를 곱함

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int cnt; // N의 진짜 약수의 개수
vector <int> v; // N의 진짜 약수
int N;

void input(){
    cin >> cnt;
    for(int i=0;i<cnt;i++){
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
}

void solution(){
    // 벡터 오름차순 정렬
    sort(v.begin(), v.end());
    // 벡터의 처음 값과 마지막 값 곱함
    N = v[0] * v[v.size()-1];
}

void output(){
    cout << N;
}

int main(void){
    input();
    solution();
    output();
    return 0;
}

메모리: 2020 KB
시간: 0 ms

1

티어 : 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;
}

메모리: 2020 KB
시간: 0 ms

나머지

티어 : Bronze 5
시간 제한 : 1 초
메모리 제한 : 256 MB
알고리즘 분류 : 수학, 구현, 사칙연산

문제

(A+B)%C는 ((A%C) + (B%C))%C 와 같을까?

(A×B)%C는 ((A%C) × (B%C))%C 와 같을까?

세 수 A, B, C가 주어졌을 때, 위의 네 가지 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000)

출력

첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다.

예제 입출력

Code

#include <iostream>
using namespace std;

int main(void){
    int A, B, C;
    cin >> A >> B >> C;
    cout << (A+B)%C << "\n";
    cout << ((A%C)+(B%C))%C << "\n";
    cout << (A*B)%C << "\n";
    cout << ((A%C)*(B%C)%C) << "\n";
    return 0;
}

메모리: 2020 KB
시간: 0 ms

경로 찾기

티어 : 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])))

메모리: 30840 KB
시간: 92 ms

행렬

티어 : 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)

메모리: 30840 KB
시간: 76 ms

카드 합체 놀이

티어 : Silver 1
시간 제한 : 1 초 (추가 시간 없음)
메모리 제한 : 512 MB
알고리즘 분류 : 자료 구조, 그리디 알고리즘, 우선순위 큐

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 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))

메모리: 30840 KB
시간: 240 ms