배극곰의 IT식량창고

문제링크

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

문제설명

7
1
5
2
10
-99
7
5

1
1
2
2
2
2
5​

문제풀이

시간초과난 풀이

시간초과가 날것으로 예상했는데 역시나였다.

해결방법

우선순위 큐를 이용하자!

두개의 힙을 만들어 하나는 최소힙, 다른 하나는 최대힙으로 구현하자.

핵심은

leftHeap의 첫번째 원소에 중간값이 위치하게 만들면 된다.

rightHeap의 첫번째 원소가 leftHeap의 첫번째원소보다 크다면 중간값을 구할 수 없게 되므로

매 루프시 조건문을 통해 exchage하자!

이렇게 하면 매 루프시 sort를 시행하는 것보다 연산횟수 측면에서 단연 효율적이다.

코드

import sys
import heapq

input = sys.stdin.readline
N = int(input())
leftHeap = []
rightHeap = []

for i in range(N):
    data = int(input())

    if len(leftHeap) == len(rightHeap):
        # 최대힙으로 구현
        heapq.heappush(leftHeap, -data)
    else:
        # 최소힙으로 구현
        heapq.heappush(rightHeap, data)

    # leftHeap의 첫번째 원소를 중간값으로 만들기 위해 교환.
    if rightHeap and rightHeap[0] < -leftHeap[0]:
        l = heapq.heappop(leftHeap)
        r = heapq.heappop(rightHeap)

        heapq.heappush(rightHeap, -l)
        heapq.heappush(leftHeap, -r)        

    print(-leftHeap[0])

문제링크

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

문제설명

3
10
20
40

100

문제풀이

기본구조가 최소힙인 우선순위 큐 자료구조 활용하면 쉽게 풀리는 문제다.

힙에서 heappop() 시켜 작은수 먼저 더하여 answer배열에 저장하고,

힙의 마지막 두 수가 아니라면 더한값을 다시 heappush()하여 계속 이어나간다.

코드

import sys
import heapq

input = sys.stdin.readline
N = int(input())
heap = []
answer = []

for i in range(N):
    data = int(input())
    heapq.heappush(heap, data)

if N == 1:
    answer.append(0)
else:
    while True:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        answer.append(a+b)
        if not heap:
            break
        heapq.heappush(heap, a+b)

print(sum(answer))

문제링크

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

문제설명

문제풀이

우선순위 큐

우선순위 큐는 큐의 형태를 띄고 있으나, 항상 정렬이 되어있다.

파이썬에서는 heapq라는 모듈을 사용해 이 우선순위 큐 자료구조를 구현할 수 있다.

PriorityQueue로도 구현할 수 있지만 thread-safe한 특성 때문에 heapq에 비해 상대적으로 느리다고 한다.

시간초과에 걸리지 않기 위해 코테에 사용하기에는 heapq가 좋겠다.

heapq의 기본구조는 최소힙

첫번째 요소는 항상 가장 작은 요소이기 때문에

heapq.heappop(리스트)시 최솟값이 나오게 되는 것이다.

절댓값 힙

튜플의 첫번째 요소에 절댓값을 넣고, 두번째 원소에 원래 수 를 넣는다.

절댓값이 같은경우, 두번째 요소 기준으로 다시 우선순위 매김. (오름차순)

코드

import heapq
import sys

input = sys.stdin.readline
heap = []
N = int(input())

for i in range(N):
    x = int(input())

    if x == 0:
        if heap:
            print(heapq.heappop(heap)[1])
        else:
            print(0)
    else:
        heapq.heappush(heap, (abs(x), x))

문제링크

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

문제설명

문제

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

• 정사각형은 서로 겹치면 안 된다.
• 도형은 모두 연결되어 있어야 한다.
• 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.

정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

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

19

문제풀이

DFS + 백트래킹으로 푸는 방법이 있다.

핵심

1. DFS를 시행하면서 백트래킹.

2. depth ==2 일때 예외처리  ==> ㅗ모양

주의점

이때 재귀함수를 활용하여 DFS를 하는데,

재귀함수에서는 인자로 전달할 변수의 값을 수정후 전달하지않도록 하자!

이렇게 되면 해당 값이 재귀의 각 레벨에 영향을 미치게 된다.

total 값을 전달할시

total += arr[nx][ny]

DFS(nx, ny, depth + 1, total) 

=> 이렇게 미리 변수값을 업데이트하고 인자로 넘기면 total값은 해당 재귀레벨에서 지속적으로 누적되게 된다.

따라서, 재귀 호출시에 인자에 누적과정을 같이 전달하는 방식을 사용하자!

코드

import sys

input = sys.stdin.readline
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0] 
dy = [0, 0, -1, 1]
answer = 0

def isValid(r, c):
    if 0 <= r < N and 0 <= c < M:
        return True
    return False

def DFS(x, y, depth, total):
    global answer

    if depth == 4:
        answer = max(answer, total)
        return
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if not isValid(nx, ny):
                continue
            if visited[nx][ny]:
                continue
            
            if depth == 2:
                visited[nx][ny] = 1
                DFS(x, y, depth+1, total+arr[nx][ny])
                visited[nx][ny] = 0

            visited[nx][ny] = 1
            DFS(nx, ny, depth+1, total+arr[nx][ny])
            visited[nx][ny] = 0


# for 문 돌려서 DFS 시행.
for i in range(N):
    for j in range(M):
        visited[i][j] = 1
        DFS(i, j, 1, arr[i][j])
        visited[i][j] = 0

print(answer)

문제링크

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

문제설명

2 7
2 3 2 3 1 2 7

2

문제풀이

실수한점

1. "for item in 배열" 구문을 사용하여

 그 안에서 인덱스를 구하기 위해 배열.index(아이템) 을 사용해버렸다는 거.

이렇게 되면 아이템과 같은 원소를 가진 인덱스중 처음 인덱스가 반환되므로 이런 접근방법은 위험하다.

==> 

for idx, item in enumerate(배열) 구문을 사용하거나

for i in range(N) 을 사용하자... 평범하게

cf. arr[i:].index(p) 를 하게 되면 슬라이싱 처리된 부분인덱스를 반환하지만, 우리는 멀티탭에 꽂혀있는 용품 중
가장 늦게 사용하는 용품을 알기만 하면 되므로 비교용으로는 충분하다.

핵심

- 조건 분기문 처리

 아이템이

 1. 이미 멀티탭에 꽂혀있을 경우

 2. 멀티탭에 꽂혀있지 않을경우

     (1) 빈자리 있을경우

     (2) 없을경우

          # 멀티탭에 꽂혀있는 용품중 하나를 뽑아야 한다!

          ① 이제 사용할 일 없는 용품이면 (즉, arr에  없으면)

             =>  해당 용품을 멀티탭에서 뽑기

          ② 꽂혀있는 용품 모두 나중에 사용해야 한다면,

             =>  그 중 가장 마지막에 사용할 용품을 제거  => 이것이 핵심이다.

 코드

# 구멍개수, 전기용품 총 사용횟수
N, K = map(int, input().split())
# 전기용품 이름 
arr = list(map(int, input().split()))
answer = 0
tap = []

for i, item in enumerate(arr):
    # 이미 멀티탭에 꽂혀있을 경우
    if item in tap:
        continue
    
    # 빈자리 있을경우
    if len(tap) < N:
        tap.append(item)
    # 멀티탭 꽉 차있으면
    else:
        # 우선순위를 매겨야함
        # 해당 전기용품이 다음 순번에 또 사용해야 하는지 기준으로 
        far = 0
        tmp = 0
        for p in tap:
            # 이제 사용할 일 없는 용품이면
            if p not in arr[i:]:
                tmp = p
                break
            # 사용할 일이 모두 있으면 해당 원소의 가장 끝 인덱스 추출하여 비교
            # 가장 마지막에 사용할 용품 제거위해
            elif arr[i:].index(p) > far:
                far = arr[i:].index(p)
                tmp = p
        tap.remove(tmp)
        answer += 1
        tap.append(item)

print(answer)

문제링크

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

문제설명

3
1 3
2 4
3 5

2

문제풀이

전에 풀었던 '회의실 배정' 문제와 비슷하다고 생각했다.

우선순위 큐(큐의 형태를 하고 있지만, 항상 정렬이 된 자료구조)를 사용했다.

우선순위 큐를 구현하기 위해 파이썬의 heapq 라이브러리를 활용하였는데

heapq는 기본구조가 최소힙이므로 첫번째 노드로 항상 가장 작은 요소가 된다.

핵심

우선 순위 큐로 수행시간을 줄이는 방법을 생각할 수 있느냐가 핵심인 듯하다.

코드

import sys
import heapq

input = sys.stdin.readline
N = int(input())
arr = [[0, 0] for _ in range(N)]
answer = 0 # 강의실 수
heap = []

for i in range(N):
    arr[i][0], arr[i][1] = map(int, input().split())

arr.sort(key=lambda x: x[0])
heapq.heappush(heap, arr[0][1]) # 첫 강의 끝나는 시간
for i in range(1, N):
    # heap[0] 가장 빨리끝나는 강의실임.
    # 다음 강의 시작시간이 더 작으면, 강의실 늘려야하므로
    if heap[0] > arr[i][0]:
        heapq.heappush(heap, arr[i][1])
    # 아니라면, 같은 강의실에서 가능
    else:
        heapq.heappop(heap)
        heapq.heappush(heap, arr[i][1])

print(len(heap))

문제링크

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

문제설명

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

4
3

문제풀이

처음 시도한 방법 (시간초과난 풀이)

for i in range(N-1, 0, -1):
        # 비교할 사원 찾기 위한 또다른 포인터
        for j in range(i):
            # 순위가 더 낮다면(== 숫자가 더 크다면)
            if sortedArr[i][1] > sortedArr[j][1]:
                answer -=1
                break

N이 100000까지 범위이므로 시간초과에 더 유의했어야 했다

투포인터 이중포문을 써서, 최악의 경우 O(N^2)이므로 시간초과가 났다.

핵심

1. 서류기준으로 오름차순 정렬을 한번 한 후 

2. 그렇다면 왼쪽부터 탐색해도 된다. 

  왜냐하면, 서류성적이 가장 높은 왼쪽사원의 면접성적과 그다음 사원의 면접성적을 비교하며 합격 여부를 판단할 수 있기 때문.

sortedArr[0][1] 값을 최솟값으로 정하고 조건에 통과하면 합격수를 늘리고,

최솟값을 갱신하며 비교해 나간다.

코드

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    grade = [[0, 0] for _ in range(N)]
    answer = 0
    for i in range(N):
        grade[i][0], grade[i][1] = map(int, input().split())
    
    sortedArr = sorted(grade, key=lambda x: x[0])

    answer = 1
    minValue = sortedArr[0][1]
    for i in range(1, N):
        # 서류기준으로 오름차순 정렬된 상태이므로
        # 면접성적이 더 높아야 즉, 값이 더 낮으면 합격
        if sortedArr[i][1] < minValue:
            minValue = sortedArr[i][1]
            answer += 1
    
    print(answer)

문제링크

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

문제설명

100 50

48

문제풀이

코드

N, M = map(int, input().split())
answer = 0 # 이동횟수의 최솟값 저장

if N == 1:
    answer = 1
elif N == 2:
    answer = min(4, (M-1)//2 + 1)
# 가로길이가 6이하라면, 1번,4번 방법으로만 이동가능
elif M <= 6:
    answer = min(4, M)
# 그 외에, 모든 방법 사용가능.
else:
    answer = M-2

print(answer)

문제링크

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

문제설명

2
10
15

20

문제풀이

무게들을 배열에 입력받은 후 정렬시킨다.

배열의 오른쪽부터 탐색하면서 총개수를 늘려가며 버틸수있는 최대 무게를 계산.

그리고 그 최대무게들을 비교하며 최댓값을 산출하였다.

예를 들어, 로프들이 각 버틸 수 있는 무게가 

10 20 18 이라고 하면,

1. 오름차순 정렬 => 10 18 20

2. 1개 사용시 최대무게  => arr[-1] 값인 20

3. 2개 사용시 최대무게  => 18 * 2 = 36

4. 3개 사용시 최대무게  => 10 * 3 = 30

이므로 답은 36이다.

코드

# 모든 로프 사용할 필요 X,
# 임의로 몇개만 골라도 됨.
N = int(input())
arr = []
answer = 0 # 버틸수있는 최대무게
k = 0

for i in range(N):
    arr.append(int(input()))

arr.sort()

answer = arr[-1] # 1개 사용시 최대무게
k = 1
for i in range(N-2, -1, -1):
    k += 1
    tmp = arr[i] * k    
    answer = max(tmp, answer)

print(answer)

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/43162

문제설명

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

문제풀이

네트워크의 개수를 return 해야한다. 나는 BFS로 풀었다. 

쉽게 말하면 총 그래프의 구역 수를 세는 문제이다.

Edge로 이어진 네트워크 그룹을 세야하므로,

방문리스트를 만들고 방문하지 않은 모든 노드를 시작으로 BFS를 시행한 다음,

한번의 BFS가 끝날때마다 answer를 1 늘리면 된다.

주의할 점은,

백준의 "적록색약"이나 "유기농배추"처럼 이차원 배열에서 구역수를 세는 것이 아닌,

실제 그래프 상에서 구역수를 세는 것이 핵심이다.

굳이 말하면 백준의 "바이러스" 문제와 비슷할 것 같다.

코드

from collections import deque

def solution(n, computers):
    answer = 0
    visited = [0] * n
    queue = deque()
    
    def BFS(node):
        queue.append(node)
        visited[node] = 1
        while queue:
            v = queue.popleft()
                
            for nv in range(n):
                if computers[v][nv] == 1 and not visited[nv]:
                    queue.append(nv)
                    visited[nv] = 1
    
    for i in range(n):
        if not visited[i]:
            BFS(i)
            answer += 1
            
    return answer