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

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

풀이 과정

• 처음엔 그냥 무식하게 탐색으로 하려고 했으나 계속 시간초과가 나옴.

  • 생각해보니 최대 1000개 학급에 최대 1000명의 학생이 가능한데 조건을 걸더라도 1000의 1000제곱은 풀릴리가 없음,,

• 고민하다 찾아보니 투포인터 알고리즘을 사용한다고 해서 투포인터 알고리즘으로 풀이

  • 모든 각각의 학급 내 학생들을 오름차순으로 정렬한 후, 초기에는 각 학급에서 능력치가 가장 낮은 학생들만 뽑아서 그룹을 만든다.
  • 차이를 좁히기 위해서는 최솟값을 올리던지 최댓값을 내리던지 해야 하는데.. 능력치가 낮은 학생에서 높은 학생 순으로 진행하므로 최댓값을 내릴수 없으므로 최솟값을 올리는 방식만 고려하면 된다.
  • 최소 히프를 사용해서 능력치가 가장 낮은 학생을 뽑고, 그 학생이 속한 그룹의 다음 학생을 다시 히프에 넣어주는 방식으로 진행
  • 과정 중에 하나의 반의 마지막 학생이 최솟값인 경우 더이상 최솟값을 갱신할 수 없으므로 종료하면 된다.
  • 과정 중 최댓값과 최솟값의 차이는 계속해서 갱신해준다.

소스 코드

import sys
import heapq
from collections import deque

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

n, m = map(int, input().split())
students = [deque(sorted(list(map(int, input().split())))) for _ in range(n)]

heap = []

min_value = int(10e9)
max_value = 0

for i in range(len(students)):
    v = students[i].popleft()
    max_value = max(max_value, v)
    min_value = min(min_value, v)
    heapq.heappush(heap, [v, i])

sumation = max_value - min_value

while heap:
    prev_min_value, pos = heapq.heappop(heap)
    if not students[pos]:
        # 해당 deque가 비어있다면 더이상 갱신 불가능
        break

    new_value = students[pos].popleft()
    heapq.heappush(heap, [new_value, pos])

    if max_value < new_value:
        max_value = new_value
    min_value = heap[0][0]
    sumation = min(sumation, max_value - min_value)


print(sumation)

https://programmers.co.kr/learn/courses/30/lessons/12902

풀이 과정

1. DP 테이블을 구성한다.

2. 현재 위치 i 기준으로 가능한 경우의 수

   • i-2칸을 채우는 경우의 수에서 2칸 채우는 경우의 수인 3을 곱한다.
   • i-4칸을 채우는 경우의 수에서 4칸 채우는 경우의 수인 2를 곱한다.
     • 4칸 채우는 경우의 수에서.. 가운데에 블록 하나씩 넣으면 2칸씩 늘어난다.
     • 6칸 채우는 경우의 수도 2개, 8칸 채우는 경우의 수도 2개, ..
     • 각각을 처리해 주어야 한다.

3. 테이블을 채우기 전, 계산한 결과를 1,000,000,007으로 나눈 나머지를 저장해 둔다.

4. dp[n]을 리턴해주면 된다.

소스 코드

def solution(n):
    answer = 0
    dp = [1] + [0] * (n)

    for i in range(2, n+1):
        dp[i] += (dp[i-2] * 3)
        for j in range(4, i+1, 2):
            dp[i] += (dp[i - j] * 2)

        dp[i] = dp[i] % 1000000007
    answer = dp[n]
    return answer

https://programmers.co.kr/learn/courses/30/lessons/42897

풀이 과정

• 썩 좋은 문제인거같지는 않음.. DP 테이블을 구성하면 시간초과가 나와서 찾아보니 변수로 풀이하면 시간초과가 나지 않는다고 하여 변수로 DP 풀이 함.

1. 동그랗게 배치되어 있으므로 1번에 집이 배치되던가 배치되지 않던가 두가지 경우로 나누어서 풀이해야 함.

   • 1번에 집이 배치되었다면 2번에는 반드시 배치가 되지 않은 상태로 3번부터 진행
   • 1번에 집이 배치되어있지 않다면 2번에는 배치가 될수도, 안될수도 있으니 각각에 맞춰 채운 후 진행

2. 최대 금액을 출력한다.

   • 1번에 집이 배치가 된 상태이면서 마지막 번호에 배치가 되지 않은 경우
   • 1번에 집이 배치가 되지 않은 상태이면서 마지막 번호에 배치가 되었거나 / 되지 않은 경우
   • 총 세가지 경우중 최댓값을 출력해주면 된다.

3. 아래 소스 참고

   • a -> 1번 뽑음 & 현재 번호의 집은 털지 않음
   • b -> 1번 뽑음 & 현재 번호의 집 털음
   • e -> 1번 뽑지 않음 & 현재 번호의 집 털지 않음
   • f -> 1번 뽑지 않음 & 현재 번호의 집 털음

소스 코드

def solution(money):

    # 1번을 뽑았을 때
    a, b, c, d = 0, 0, 0, 0
    a, b = money[0], money[0]

    # 1번을 뽑지 않았을 때
    e, f, g, h = 0, 0, 0, 0
    e, f = 0, money[1]

    for i in range(2, len(money)):
        c = max(a, b)
        d = max(a + money[i], b)
        g = max(e, f)
        h = max(e + money[i], f)

        a, b = c, d
        e, f = g, h


    answer = max(a, e, f)
    return answer

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

풀이 과정

1. 입력받은 친구 번호에 맞추어서 그래프를 구성한다.

   • graph[번호]에 해당 번호의 친구들을 저장해둔다.

2. 1번부터 DFS를 진행하여 결혼식에 오는 친구들을 방문처리 해준다.

   • DFS의 깊이가 2일때 종료시켜 준다. (친구의 친구까지만 진행하므로)

3. 전체 DFS 과정이 종료되면 VISITED가 TRUE인 개수를 구한 뒤 1을 빼준다.

   • 상근이를 빼주어야 함.

소스 코드

import sys

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

def dfs(graph, visited, person, depth):
    if depth == 2:
        return
    for nx in graph[person]:
        if not visited[nx]:
            visited[nx] = True
        dfs(graph, visited, nx, depth+1)

n = int(input())
m = int(input())
friends = [map(int, input().split()) for _ in range(m)]

graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
visited[1] = True

for p1, p2 in friends:
    graph[p1].append(p2)
    graph[p2].append(p1)

dfs(graph, visited, 1, 0)
print(len(list(filter(lambda x:x==True, visited))) - 1)

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

풀이 과정

1. 선분을 이용하여 그래프를 구성한다.

   • 두 선분이 친구 관계라면 1, 친구 관계까 아니라면 아주 큰 값(INT_MAX)으로 설정
   • 두 선분이 친구 관계인지 확인하려면 총 세가지 케이스를 확인해야 한다.
     1. 하나의 선분의 왼쪽 끝이 다른 선분 안에 있거나, (왼쪽은 겹치고 오른쪽은 선분 밖에)
     2. 오른쪽 끝이 다른 선분 안에 있거나. (오른쪽은 겹치고 왼쪽은 선분 밖에)
     3. 하나의 선분의 왼쪽 끝이 다른 선분보다 작고, 오른쪽 끝이 다른 선분보다 클 때(덮을 때)
     4. 아예 안에 들어있을 때는 (1), (2)에 걸리므로 따로 처리할 필요 없음

2. Floyd 알고리즘을 사용하여 각 선분에서 다른 선분으로 이동 가능한 최단 거리를 테이블로 미리 구성해 둔다.

   • 삼중 반복문을 통해 거쳐가는 모든 케이스 조사
   • 반복문 순서가 중요함!! 맨 바깥쪽 반복문이 거쳐가는 노드
     • distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
     • k가 거쳐가는 노드
   • T의 최대가 300이라서.. 300 * 300 * 300을 해야되는데 좀 크지 않나라고 생각했지만 잘 된다. 생각해보니 후에 Q개의 줄에 걸쳐 최단경로를 입력받고 출력해야되서 좀 오래걸리더라도 다 구해둬야 되는게 맞음.

3. 입력받은 두 선분 사이의 거리를 출력해 준다.

소스 코드

import sys

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

T = int(input())
lines = [list(map(int, input().split())) for _ in range(T)]
INT_MAX = int(10e9)
graph = [[INT_MAX] * T for _ in range(T)]

for i in range(len(lines)):
    for j in range(i+1, len(lines)):
        if (lines[i][0] <= lines[j][0] and lines[j][0] <= lines[i][1]) or \
        (lines[i][0] <= lines[j][1] and lines[j][1] <= lines[i][1]) or \
        (lines[j][0] <= lines[i][0] and lines[j][1] >= lines[i][1]):
            graph[i][j] = 1
            graph[j][i] = 1

for i in range(T):
    for j in range(T):
        for k in range(T):
            graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

Q = int(input())
for _ in range(Q):
    src, dest = map(int, input().split())
    src, dest = src - 1, dest - 1

    if graph[src][dest] == INT_MAX:
        print(-1)
    else:
        print(graph[src][dest])

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

풀이과정

1. 맨 왼쪽부터 X개의 합계를 먼저 구해두고 시작.

2. [i ~ i+X]의 합계중 최댓값을 구하면 되는 문제

   • 매번 합계를 구해주면 시간이 너무 오래 걸린다.
   • 따라서, [i ~ i+X]의 합계를 구한 다음, 다음 구간의 합계에서는 [i]를 빼주고, [i+X+1]을 더해주면 그게 [i+1 ~ i+X+1]의 합계이다.
   • 이러한 방식으로 진행하면서 합계중 최댓값을 저장해두고, 최댓값이 같은 경우 최댓값의 개수도 같이 증가

3. 최댓값과 최댓값의 갯수를 출력해 준다.

소스 코드

import sys

input = lambda : sys.stdin.readline().rstrip()
N, X = map(int, input().split())
log = list(map(int, input().split()))

max_visitor = 0
max_visitor_cnt = 0

visitor = sum(log[:X])
left = 0
right = X-1

while right < N:
    if max_visitor < visitor:
        max_visitor = visitor
        max_visitor_cnt = 1
    elif max_visitor == visitor:
        max_visitor_cnt += 1

    if right == N-1:
        break

    visitor -= log[left]
    left += 1
    right += 1
    visitor += log[right]

if max_visitor == 0:
    print("SAD")
else:
    print(max_visitor)
    print(max_visitor_cnt)

https://programmers.co.kr/learn/courses/30/lessons/86052

풀이 과정

• 이게 난이도 2는 아닌거 같음. 전혀 감을 못잡고있다가 힌트를 보고 풀었음..

1. 전체 경우의 수를 탐색함.

   • 각각의 격자에서 왼쪽, 아래, 오른쪽, 위 네개의 방향으로 시작해서 이미 방문한 격자를 만날때까지 탐색
   • 미리 방향 배열을 만들어 두어서 좌회전일땐 +1, 우회전일땐 -1 하도록 함.
   • 탐색할 때 격자를 몇개 이동했는지 저장해 둠.

2. 격자의 끝을 넘어갈 때, 반대쪽 방향으로 들어오는건 그냥 나머지 연산자로 구현함.

   • (-1) % n = n-1, (n+1) % n = 1 인걸 이용

3. 저장해 둔 탐색 결과를 오름차순으로 정렬하여 리턴

소스 코드

def goto(grid, visited, start):
    x, y, way = start
    direction = [[0, -1], [1, 0], [0, 1], [-1, 0]]
    length = 0
    while True:
        if visited[x][y][way]:
            break

        visited[x][y][way] = True
        length += 1

        if grid[x][y] == 'S':
            pass
        elif grid[x][y] == 'L':
            way = (way + 1) % 4
        elif grid[x][y] == 'R':
            way = (way - 1) % 4

        x = (x + direction[way][0]) % len(grid)
        y = (y + direction[way][1]) % len(grid[0])

    return length

def solution(grid):
    answer = []
    visited = [[[False] * 4 for _ in range(len(grid[0]))] for __ in range(len(grid))]

    for i in range(len(grid)):
        for j in range(len(grid[0])):
            for k in range(4):
                if visited[i][j][k] == False:
                    answer.append(goto(grid, visited, [i, j, k]))

    answer.sort()
    return answer

https://programmers.co.kr/learn/courses/30/lessons/62050

풀이 과정

• 4단계 문제라 그런지 소스가 되게 길고 응용이 많다..

1. BFS로 이동 가능한 각각의 영역에 번호를 붙여준다.

   • 영역번호가 1번이라면 1번끼리는 이동 가능한 것이다.

2. 번호를 붙인 영역간에 이동 가능한 최소 거리를 저장해 둔다.

   • 노드가 영역의 수만큼 있다고 생각
   • dict[(1, 2)] = 3 이라면.. 1번 노드(영역)에서 2번 노드(영역)으로 이동하기 위해서(간선) 비용이 3이라고 보면 된다.

3. Kruskal 알고리즘으로 최소비용 신장트리를 구한 다음, 최소비용을 리턴해주면 된다.

   • 간선의 비용이 최소인것부터 순차적으로 사용한다.
   • union-find 알고리즘을 사용하여 사이클 검사

소스 코드

from collections import deque, defaultdict
import heapq

def area_bfs(area, land, start, value, height):
    queue = deque([start])
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    area[start[0]][start[1]] = value
    while queue:
        cx, cy = queue.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx and nx < len(land) and 0 <= ny and ny < len(land[0]):
                if area[nx][ny] == int(10e9) and abs(land[cx][cy] - land[nx][ny]) <= height:
                    area[nx][ny] = value
                    queue.append([nx, ny])

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


def solution(land, height):
    answer = 0

    # 구간별로 번호 매김
    INT_MAX = int(10e9)
    area = [[INT_MAX] * len(land[0]) for _ in range(len(land))] 
    number = 1
    for i in range(len(area)):
        for j in range(len(area[0])):
            if area[i][j] == INT_MAX:
                area_bfs(area, land, [i, j], number, height)
                number += 1

    # 구간 그래프화
    dx = [1, 0]
    dy = [0, 1]

    distance = defaultdict(lambda: int(10e9))
    for i in range(len(area)):
        for j in range(len(area[0])):
            for k in range(2):
                nx, ny = i + dx[k], j + dy[k]
                if 0 <= nx < len(area) and 0 <= ny < len(area[0]) and area[i][j] != area[nx][ny]:
                    # 작은 지역번호가 앞으로 가도록 간선정보 구성
                    # key : (작은 지역 번호, 큰 지역 번호) = 최소 이동 거리
                    src = min(area[i][j], area[nx][ny])
                    dest = max(area[i][j], area[nx][ny])
                    distance[(src, dest)] = min(distance[(src, dest)], abs(land[nx][ny] - land[i][j]))


    parent = [i for i in range(number)]
    heap = []

    # 간선 오름차순으로 힙에 넣어줌.
    for areas, dist in distance.items():
        heapq.heappush(heap, [dist, areas])

    # 간선의 크기가 작은 순서대로 그래프에 추가
    # 사이클 형성시 패스
    while heap:
        dist, areas = heapq.heappop(heap)
        if find(parent, areas[0]) != find(parent, areas[1]):
            union(parent, areas[0], areas[1])
            answer += dist

    return answer

https://programmers.co.kr/learn/courses/30/lessons/43236?language=python3

풀이 과정

1. 이분 탐색으로 풀이를 한다. 이분 탐색의 대상은 각 지점 사이의 거리의 최솟값으로 진행한다.

   • 이 값을 mid라고 두자.

2. 만약 이전 돌과 현재 돌 사이의 거리가 mid보다 작다면 제거해야되는 돌이므로 제거 카운팅을 늘려준다.

   • 맨 마지막에 도착지점과 마지막 돌 사이의 거리도 체크해줘야 함.
   • 제거한 돌은 거리 계산에 들어가면 안되므로, 이전 돌은 prev라는 변수에 따로 저장해두고 현재 돌을 제거해야되는 경우 prev 변수를 갱신하지 않도록 함.

3. 제거한 돌의 개수가 n개 이하인 경우에는 정답을 저장해 두고 오른쪽 구간 진행(최댓값을 찾아야 하므로)

4. 제거한 돌의 개수가 n개보다 많은 경우는 왼쪽 구간 진행

• 원래 문제 읽어보면 딱 n개 제거해야되는거 같은데, n개 제거하도록 하면 틀림. n개 이하로 해야 맞음..

소스 코드

def solution(distance, rocks, n):
    answer = 0
    left = 0
    rocks.sort()
    right = int(10e8)+1

    # mid를 최솟값이라고 할 때
    while left <= right:
        mid = (left + right) // 2
        prev = 0
        eliminated_count = 0
        for i in range(len(rocks)):
            if rocks[i] - prev < mid:
                eliminated_count += 1
            else:
                prev = rocks[i]

        if distance - prev < mid: # 도착 거리
            eliminated_count += 1

        if eliminated_count <= n:
            answer = mid
            left = mid + 1
        else:
            right = mid - 1

    return answer

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

풀이 과정

1. 가장 큰 수를 만들려면 1, 7만으로 최대한 자리수를 늘리기만 하면 된다. (각각 2개, 3개이며 나머지는 4개 이상이므로 1 두개 넣는것보다 작음)

   • 성냥개비 개수가 홀수라면 맨앞에 7을 넣어주고 나머지는 1, 짝수라면 전체 1만으로 구성

2. BFS를 사용하여 DP 테이블을 채워준다.

   • 최대 100개의 성냥개비를 사용 가능하므로 100개까지 진행
   • DP[i]는 i개의 성냥개비로 만들 수 있는 수의 최솟값
   • 큐에 들어가는 형식은 [성냥개비 수, 만들어진 수]
   • 맨 앞자리는 0이 들어갈 수 없으므로, 초기 큐에는 1~9까지만 넣어준다.
   • 매 단계 큐에 넣을때마다 뒤에 09를 붙여주고, 09를 만드는데 필요한 성냥 수를 더해서 넘겨준다.
     • 성냥 수가 100개를 넘어가면 안됨.
   • 큐에서 빼낼 때, 만들어진 수가 기존 수보다 작을때만 뒤에 붙여주는 과정 진행

3. 최솟값, 최댓값 형식으로 출력시켜주면 된다.

• 최솟값이 굉장히 큰 수가 나올 수 있으므로 초기 값 설정을 잘 해주어야 함. 초깃값을 10e9로 했다가 처음엔 틀렸는데, sys.maxsize로 바꾸어주니 정답이 나옴.

import sys
from collections import deque

T = int(sys.stdin.readline().rstrip())

INT_MAX = int(sys.maxsize)

dp_max = [0] * 101
dp_min = [INT_MAX] * 101

count = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]
initial = [[value, idx] for idx, value in enumerate(count)][1:]

queue = deque(initial)

while queue:
    cnt, make = queue.popleft()
    dp_min[cnt] = min(dp_min[cnt], make)
    if dp_min[cnt] != make:
        continue
    for i in range(10):
        if cnt + count[i] <= 100:
            queue.append([cnt + count[i], int(str(make)+str(i))])

for _ in range(T):
    p = int(sys.stdin.readline().rstrip())
    max_string = ''
    if p % 2 == 1:
        max_string = '7' + '1' * ((p-3) // 2)
    else:
        max_string = '1' * (p // 2)
    print(dp_min[p], max_string)