그냥 코딩하는 사람의 블로그

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

풀이 과정

1. 지원자 A의 성적이 어떤 지원자 B보다 서류 심사, 면접 성적이 모두 떨어지는 경우는 선발되지 않는다라는 조건이 있으므로, 따라서 서류 심사를 기준으로 오름차순 정렬을 해 준다.
2. 정렬된 리스트를 기준으로 순차적으로 지원자를 검사한다.
   1. 서류 심사를 기준으로 오름차순 정렬을 해주었으므로, 서류심사 성적은 무조건 이전 지원자보다 안좋다고 볼 수 있으므로, 면접 성적만을 보면 된다.
   2. 따라서, 이전 지원자들보다 면접 성적이 좋아야만 합격이다. 따라서, 합격한 지원자들의 면접 성적중 가장 좋은 면접 성적보다 좋은지 확인하고, 좋다면 가장 좋은 면접 성적을 갱신하고 합격 카운팅을 해준다.
3. 전체 합격자의 수를 출력한다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
T = int(input())

for _ in range(T):
    N = int(input())
    applicants = [list(map(int, input().split())) for _ in range(N)]
    applicants.sort()
    max_r2 = 999999
    answer = 0
    for _, r2 in applicants:
        if r2 < max_r2:
            max_r2 = r2
            answer += 1

    print(answer)

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

풀이 과정

1. 전체적으로 3가지 과정을 반복한다.
   
   1. 치즈가 더이상 남아있지 않은지 체크한다
   2. 외부 공기의 위치들을 따로 구해준다.
      • 이 과정에서 테두리는 무조건 외부 공기로 간주해도 되기 때문에, (0, 0)에서부터 1이 아닌 0을 만나는 경우에 대해서만 BFS를 진행해주면 된다.
   3. 각각의 치즈와 인접한 4개의 칸 중 몇개의 칸이 외부 공기인지 개수를 구하고, 2개 이상이라면 제거해 준다. 이 때, 한번에 제거해 주어야 제거로 인해 다른 치즈가 영향을 받지 않는다.
   4. 시간을 1초 증가시켜 준다.
2. 치즈가 남아있지 않는다면, 총 몇초가 지났는지 출력시켜 준다.

소스 코드

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

def get_air_pos():
    air = set()
    air.add((0, 0))
    queue = deque([[0, 0]])
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < N and 0 <= ny and ny < M:
                if (nx, ny) not in air and matrix[nx][ny] == 0:
                    air.add((nx, ny))
                    queue.append([nx, ny])

    return air

def is_empty():
    for i in range(N):
        for j in range(M):
            if matrix[i][j] != 0:
                return False
    return True

def destroy_cheese(air):
    destroy_cheese_pos = []
    for i in range(N):
        for j in range(M):
            if matrix[i][j] == 1:
                air_count = 0
                for k in range(4):
                    x, y = i + dx[k], j + dy[k]
                    if (x, y) in air:
                        air_count += 1
                if air_count >= 2:
                    destroy_cheese_pos.append([i, j])
                    
    for x, y in destroy_cheese_pos:
        matrix[x][y] = 0
                            

time = 0
while True:
    if is_empty():
        break
    air = get_air_pos()
    destroy_cheese(air)
    time += 1
    

print(time)

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

풀이 과정

1. 2-친구가 되기 위해서는 간단하게 보면 직접 친구이거나, 한명의 친구를 거쳐서 친구이면 된다. 따라서 플로이드 알고리즘을 사용하여 거리 배열을 구한다.
   1. 직접 친구인 경우의 거리는 1이다.
   2. 한명의 친구를 거쳐서 친구인 경우의 거리는 2이다.
2. 각 사람별로 거리가 2 이하인 친구의 명수를 구해준 다음 최댓값을 구해준다.
3. (2)에서 구한 최댓값을 출력해 준다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N = int(input())

matrix = [list(input()) for _ in range(N)]
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 'N':
            matrix[i][j] = int(10e9)
        else:
            matrix[i][j] = 1

for i in range(N):
    for j in range(N):
        for k in range(N):
            matrix[j][k] = min(matrix[j][k], matrix[j][i] + matrix[i][k])

answer = 0
for i in range(N):
    count = 0
    for j in range(N):
        if j != i and matrix[i][j] <= 2:
            count += 1
    answer = max(answer, count)


print(answer)

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

풀이 과정

문제에서 어떻게 구현하라고 다 나와있기 때문에 그대로 구현해주면 된다. 여기서는 개인적으로는 map과 filter을 잘 사용하면 소스코드가 많이 간결해질 수 있을 것이라고 생각된다.

1. 각 후보가 점수별로 몇점을 획득하였는지 저장해 둔다.
2. 전체 점수의 합계가 가장 큰 후보군을 먼저 골라준다.
3. 후보군이 2명 이상인 경우에는 다음 단계로 진행한다.
   1. 3점을 가장 많이 받은 사람의 집합으로 후보군을 줄여준다.
   2. 이후, 2점을 가장 많이 받은 사람의 집합으로 후보군을 줄여준다.
4. 모든 단계를 거치고 난 다음에도 후보군이 2명 이상이라면 0과 최대 점수를 출력해 주고, 후보군이 1명이라면 해당 인원의 번호와 점수를 출력해 준다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N = int(input())

score = [[0] * 3 for _ in range(3)]

for _ in range(N):
    a, b, c = map(int, input().split())
    score[0][a-1] += a
    score[1][b-1] += b
    score[2][c-1] += c

total_score = [[idx, sum(sc)] for idx, sc in enumerate(score)]
max_score = max(map(lambda x: x[1], total_score))
candidate = list(filter(lambda x: x[1] == max_score, total_score))

if len(candidate) >= 2:
    max_three_count = max(map(lambda x: score[x[0]][2], candidate))
    candidate = list(filter(lambda x: score[x[0]][2] == max_three_count, candidate))
    max_two_count = max(map(lambda x: score[x[0]][1], candidate))
    candidate = list(filter(lambda x: score[x[0]][1] == max_two_count, candidate))

if len(candidate) >= 2:
    print(0, max_score)
else:
    print(candidate[0][0] + 1, candidate[0][1])

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

풀이 과정

1. Kruskal 알고리즘을 사용하여 최소 비용 신장 트리를 구성한다.
   1. 최소 비용인 간선을 하나 선택하고 Cycle을 형성하는지 체크한다
   2. Cycle을 형성하는지 체크하는 방법은 간선에 연결된 두 점이 하나의 집합에 속해있는지 확인하면 된다.
      1. Union-find 알고리즘 사용
   3. Cycle을 형성하지 않는다면 두 점을 연결해 주고 비용을 더해준다.
   4. 위 과정을 총 N-1개의 간선을 선택할 때까지 반복해 준다.
2. 최소 비용 신장 트리의 비용의 합계를 출력시켜 준다.

풀이 과정

import sys
import heapq

input = lambda: sys.stdin.readline().rstrip()

N = int(input())
heap = []
cost = [list(map(int,input().split())) for _ in range(N)]

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 != p2:
        parent[p1] = p2

for i in range(N):
    for j in range(i+1, N):
        heapq.heappush(heap, [cost[i][j], i, j])

answer = 0
parent = [i for i in range(N+1)]
edge_count = 0
while heap and edge_count < N-1:
    cost, fr, to = heapq.heappop(heap)
    if find(parent, fr) != find(parent, to):
        union(parent, fr, to)
        answer += cost
        edge_count += 1


print(answer)

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

풀이 과정

1. 맨 앞자리에 K가 들어오려면 이전 자리에는 K~9가 들어올 수 있다.
   1. 따라서 점화식을 구성하면 DP[i][K] = DP[i-1][K] + DP[i-1][K+1] + ... + DP[i-1][9]
   2. 해당 점화식을 이용하여 DP 테이블을 채워주면 된다. 단, 한자리일때는 자기 자신을 고를때밖에 없으므로 1로 설정하여 준다.
2. 이후 각각의 테스트 케이스에 입력받은 자리수에 맞추어서 DP 테이블에서의 합계를 구해서 출력시켜 준다.
   • 예를 들어, 자릿수 4를 입력받으면 DP[4]의 합계를 출력시켜 주면 된다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
dp = [[0] * 10 for _ in range(65)]

for i in range(10):
    dp[1][i] = 1

for i in range(2, 65):
    for j in range(10):
        for k in range(j, 10):
            dp[i][j] += dp[i-1][k]

T = int(input())
for _ in range(T):
    C = int(input())
    print(sum(dp[C]))

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

풀이 과정

1. 현재 가진 연료로 어떤 주유소를 들릴 수 있는지를 업데이트 해주는게 핵심
2. 현재 가진 연료로 마을까지 갈 수 없다면 주유소를 무조건 하나 이상 들려야 함. 
   1. 따라서, 방문할 수 있는 주유소를 따로 기름의 양을 기준으로 최대 히프에 넣어 관리한다. 
   2. 이 때, 방문할 수 있는 주유소들 중 기름을 가장 많이 넣을 수 있는 주유소를 하나 방문해서 들려준다. 즉, 최대 히프에서 하나의 요소를 꺼내서 기름을 채워준다. 이 때 해당 주유소를 들리게 되므로 따로 카운트를 하나 늘려준다.
   3. 주유소를 방문해서 기름을 넣었으므로 넣은 기름으로 더 이동해서 방문할 수 있는 주유소를 다시 최대 히프에 넣어준다.
3. 방문할 수 있는 주유소가 더이상 없는데 마을에 도착하지 않았다면 -1을 리턴해 주고, 마을에 도착하였다면 방문한 주유소의 수를 출력시켜 준다.

소스 코드

import sys
import heapq
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

N = int(input())
stations = [list(map(int, input().split())) for _ in range(N)]
dist, current_gas = map(int, input().split())
heap = []

stations.sort(key=lambda x:x[0])
queue = deque(stations)

answer = 0
while True:
    while queue and queue[0][0] <= current_gas:
        _, gas  = queue.popleft()
        heapq.heappush(heap, -gas)

    if dist <= current_gas:
        break
    else:
        if not heap:
            answer = -1
            break
        append_gas = -heapq.heappop(heap)
        current_gas += append_gas
        answer += 1

print(answer)

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

풀이 과정

1. 각각의 알파벳이 있는 자리가 1이라고 할 때 모두 더했을때 값이 얼마나 나오는지 구한다.
   • 예를 들어, Axxxx + xxAxx라 하면 10100이 나온다.
2. (1)에서 구한 값들중 가장 큰 값에 9를 부여하고, 다음 큰 값에 8을 부여하고 , .. 이러한 방식으로 값을 부여해준 다음 합계를 구해 준다.
   1. 값을 부여할 때는, (1)에서 구한 값에 부여한 값을 곱해주면 된다.
   2. 값을 부여한 후, 그대로 더한다.
3. (2)에서 구한 합계를 출력해 준다.

소스 코드

import sys
from collections import defaultdict

input = lambda: sys.stdin.readline().rstrip()


alpha = defaultdict(lambda: 0)
N = int(input())
for _ in range(N):
    word = input()
    size = len(word)
    for idx, ch in enumerate(word):
        alpha[ch] += (10 ** (size-1-idx))

temp = sorted(alpha.values(), reverse=True)
pos = 0
answer = 0
for i in range(9, 0, -1):
    answer += temp[pos] * i
    pos += 1
    if pos == len(temp):
        break

print(answer)

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

풀이 과정

1. 초기에 설치해둔 폭탄의 위치를 저장해 둔다.
2. 폭탄이 없는곳에 모두 폭탄을 설치시켜 준다.
   • 이 때, 초기에 설치해둔 폭탄과 터지는 시간이 다르기 때문에 폭탄이 없는곳에 폭탄을 설치하면서 위치를 따로 저장해 두어야 한다.
3. 직전에 설치한 폭탄이 아닌, 더 이전에 설치해둔 폭탄을 터트린다.
   • 이 때, 직전에 설치한 폭탄도 터질 수 있으므로 만약 직전에 설치한 폭탄도 터진다면 직전에 설치한 폭탄 집합에서 해당 폭탄을 제거해 준다.
4. 입력받은 시간에 맞추어서 2-3 과정을 반복해 주면 된다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
R, C, N = map(int, input().split())

matrix = [list(input()) for _ in range(R)]
boompos = []
for i in range(R):
    for j in range(C):
        if matrix[i][j] == 'O':
            boompos.append([i, j])

def set_boom(matrix):
    next_boom = set()
    for i in range(R):
        for j in range(C):
            if matrix[i][j] == '.':
                next_boom.add((i, j))
                matrix[i][j] = 'O'
    return next_boom

def boom(matrix, boompos, next_boom):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, 1, -1]
    destroypos = set()
    for x, y in boompos:
        destroypos.add((x, y))
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C:
                destroypos.add((nx, ny))

    for x, y in destroypos:
        if (x, y) in next_boom:
            next_boom.remove((x, y))
        matrix[x][y] = '.'
        

time = 1
while time < N:
    next_boom = set_boom(matrix)
    time += 1
    if time == N:
        break
    boom(matrix, boompos, next_boom)
    boompos = next_boom
    time += 1

for m in matrix:
    print("".join(m))

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

풀이 과정

1. 문제에서 다리를 하나 무너뜨려 서로 왕복할 수 없는 섬이 생겼다고 주어졌으므로 두개의 섬으로 분리되었다는걸 알 수 있음.
2. Union-Find 알고리즘을 사용하여 두개의 섬의 집합을 구해준다.
   1. 이어진 섬의 parent는 같으며, 이어지지 않은 섬의 parent는 다르다는 점을 이용하여 1번째 섬에서부터 N번째 섬까지 방문하면서 인접한 섬과의 parent를 비교한다.
   2. parent 값이 다른 경우 떨어진 섬이므로 두 섬을 연결해주면 된다.

소스 코드

import sys

sys.setrecursionlimit(10**5)
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
parent = [i for i in range(N+1)]


def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
    return parent[a]

def union(parent, a, b):
    par1 = find(parent, a)
    par2 = find(parent, b)

    if par1 != par2:
        parent[par1] = par2

for _ in range(N-2):
    a, b = map(int, input().split())
    if find(parent, a) != find(parent, b):
        union(parent, a, b)

for i in range(2, N+1):
    if find(parent, i) != find(parent, i-1):
        union(parent, i, i-1)
        print(i, i-1)