배극곰의 IT식량창고

문제링크

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

문제설명

9 8
CCTGGATTG
2 0 1 1

0

4 2
GATA
1 0 0 1

2

문제풀이

핵심

- 문자열에서 특정 조건을 만족하는 크기가 고정된 부분 문자열을 탐색하기 위해 슬라이딩 윈도우 활용

- 딕셔너리를 사용하여 각 필요한 알파벳 충족개수를 비교하는 로직에 활용하였다.

시간복잡도를 줄이기 위해 활용하는 슬라이딩 윈도우의 본질을 잊지말자!

(이중반복문 X)

반복문 작성시에는 항상 인덱스를 초과하지 않도록 유념해야하는 것 같다.

해당 문제 같은 경우는, 오른쪽 포인터가 인덱스를 벗어나지 않도록 j += 1 문 이전에 

맨 오른쪽 원소를 추가하는 로직을 작성하였다.

시간복잡도는 O(N) 이다.

코드

s, p = map(int, input().split())
data = input()
acnt, ccnt, gcnt, tcnt = map(int, input().split())
answer = 0
# 두개의 포인터 지정
i = 0
j = p - 1

# 딕셔너리
dict = { 'A': 0, 'C': 0, 'G': 0, 'T': 0 }
targetStr = data[i:j]

for item in targetStr:
    dict[item] += 1

# 슬라이딩 윈도우
while j <= s-1:
    # 인덱스 초과 나니까 j+=1 하기전에, 오른쪽 원소 추가하는 로직을 먼저.
    dict[data[j]] += 1

    # 비밀번호 유효성 검사
    if dict['A'] >= acnt and dict['C'] >= ccnt and dict['G'] >= gcnt and dict['T'] >= tcnt:
        answer += 1

    dict[data[i]] -= 1 # 인덱스 맨 왼쪽 문자열 제거
    i += 1
    j += 1

print(answer)

문제링크

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

문제설명

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

3

9
8 6
7
1 2
1 3
2 7
2 8

문제풀이

주어진 친족관계들을 기반으로, 입력 받은 두 값 a, b의 촌수를 계산하는 문제였다.

핵심 아이디어

1. 인접리스트 형태로 저장.

2. ★그래프에 저장할때 양방향임을 고려 (주어진 입력값은 한 방향관계만을 나타냄)

3. a, b의 촌수를 구한다는건 => 그래프를 그려놓고 생각해보면 a부터 b까지의 최단거리

   따라서 BFS를 활용

4. 촌수 카운트를 위해 queue에 (노드번호, depth) 튜플형태로 삽입

5. BFS를 시행하다가 구하고자 하는 노드에 도달하면 depth 반환

6. BFS 끝났는데도 도달 안하면 -1 반환

코드

from collections import deque

n = int(input())
a, b = map(int, input().split())
m = int(input())
graph = [[] for _ in range(n+1)]
visited = [0] * (n+1)
queue = deque([])

# 양방향 그래프
for _ in range(m):
    s, e = map(int, input().split())
    graph[s].append(e)
    graph[e].append(s)

def BFS(a, b):
    queue.append([a, 0])
    visited[a] = 1

    while queue:
        cur, depth = queue.popleft()

        if cur == b:
            return depth

        for next in graph[cur]:
            if not visited[next]:
                queue.append([next, depth+1])
                visited[next] = 1

    return -1

print(BFS(a, b))

문제링크

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

문제설명

2
5 6
0 0 1 0

30
30

3
3 4 5
1 0 1 0

35
17

문제풀이

코드

N = int(input())
arr = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
maxValue = - int(1e9)
minValue = int(1e9)

def DFS(add, sub, mul, div, total, i):
    global maxValue, minValue

    if i == N:
        maxValue = max(maxValue, total)
        minValue=  min(minValue, total)
        return
    # 연산자 삽입
    if add:
        DFS(add-1, sub, mul, div, total+arr[i], i+1)
    if sub:
        DFS(add, sub-1, mul, div, total-arr[i], i+1)
    if mul:
        DFS(add, sub, mul-1, div, total*arr[i], i+1)
    if div:
        DFS(add, sub, mul, div-1, int(total/arr[i]), i+1)
            

DFS(add, sub, mul, div, arr[0], 1)
print(maxValue)
print(minValue)
# 연산자 우선순위 무시
# 1 2 3 4 5 6
# + + - * /

# N개의 수와 N-1개의 연산자가 주어질때 만들수있는 결과가 최대인것과 최소인것 구하기
# 완전탐색

문제링크

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

문제설명

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

9

문제풀이

시뮬레이션 문제로,

주어진 조건을 빠르고 정확하게 파악하는 것이 제일 중요한 것 같다.

이 부분은 앞으로도 남들보다 더 꾸준히 문제를 풀어 익숙해지려고 노력해야겠다.

핵심

1. 지도에서 움직이는 형태 구현. (상하좌우)

2. 방향 변환하는 함수 만들어서 활용

3. 자료구조 큐 활용

주의점

1. 이동후 현재좌표 갱신하기

BFS 문제중에 지도에서 움직이는 형태를 구현한 적이 많았는데 갱신된 좌표를 큐에 넣어서 해당좌표를 다시 꺼내 이용하여 문제가 없었지만,

지금은 직접 현재좌표를 갱신하는 추가코드가 필요하다!!

조금 안일하게 문제풀이에 임했지 않았나 싶다...

풀이 간략히 설명

- arr을 N * N 으로 만들고 사과가 있는 좌표에 1을 삽입 

- 방향 정보 저장은 딕셔너리를 활용

   direction[시간] = 문자정보  형태

- 뱀이 방문한 좌표는 arr[nx][ny] = 2. 

- 방문한 좌표마다 큐에 삽입하고, 방문한 좌표에 사과가 없다면

큐의 특성을 활용해 꼬리빼기(방문안함으로 처리)

- 이동할때마다 현재좌표 갱신!!

- 매초 마다 time을 증가시켜 direction의 키와 일치하는 시간이 되면 => 방향 변환 (함수로 구현)

코드

from collections import deque

N = int(input())
K = int(input())
arr = [[0 for _ in range(N)] for _ in range(N)]
dx = [0, -1, 0, 1]  # 각각 우 상 좌 하
dy = [1, 0, -1, 0]
directions = {}

# 입력값1) 사과 위치 정보 저장
for i in range(K):
    r, c = map(int, input().split())
    arr[r-1][c-1] = 1

L = int(input())
# 입력값2) 방향 변환 정보 저장
for i in range(L):
    x, d = input().split()
    directions[int(x)] = d

def rotateDir(index, str):  # 방향 나타내는 인덱스, 방향
    # 상3 하2 좌1 우0
    # L 왼쪽회전 => 우 -> 상(1) -> 좌(2) -> 하(3)
    # D 오른쪽회전 => 우(0) -> 하(3) -> 좌(2) -> 상(1)
    if str == 'L':
        result = (index + 1) % 4
    elif str == 'D':
        result = (index + 3) % 4
    return result

def start(x, y):
    dir = 0 # 처음은 오른쪽으로 향하니, 동을 나타내는 인덱스0 에 접근 위해 설정.
    queue = deque([(x, y)])
    arr[x][y] = 2
    time = 0
    
    while True:
        time += 1
        nx = x + dx[dir]
        ny = y + dy[dir]
        # 범위안에 있고 방문한 지역 아니라면
        if 0 <= nx < N and 0 <= ny < N and arr[nx][ny] != 2:
            queue.append((nx, ny))
            x, y = nx, ny
            # 사과가 있다면 꼬리 안뺌 그대로 늘림.
            if arr[nx][ny] == 1:
                arr[nx][ny] = 2   # 방문
            else:
                arr[nx][ny] = 2
                px, py = queue.popleft()
                arr[px][py] = 0
        else:
            break

        if time in directions.keys():
            dir = rotateDir(dir, directions[time])
    
    return time

print(start(0, 0))

문제링크

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

문제설명

4 6
a t c i s w

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

문제풀이

핵심

C개 문자 중  L개를 골라 암호를 만들어야하는데,

1. 최소 2개 자음과 1개 모음을 이용해야함.

2. 알파벳 순서로 나열된 암호여야함

풀이 과정

1. arr 오름차순 정렬

2. 정렬된 상태의 배열에서 반복문 시행. 각각 첫번째 원소부터 C-L 번째까지의 원소를 시작점으로 함수시행.

3. 후보리스트에 조건에 맞는 원소 삽입하고 재귀함수 호출

4. 후보리스트 길이가 원하는 길이라면, 암호조건에 부합하는지 체킹하고 리턴

5. 함수시행이 종료됐으므로, 백트래킹하여 다음 순번의 암호찾기.

코드

from itertools import combinations

L, C = map(int, input().split())
arr = list(input().split())
arr.sort()
# 입력예제1 => a, c, i, s, t, w

vowels = set(('a', 'e', 'i', 'o', 'u'))
# 최소 자음2개 모음1개 구성.
def check(arr):
    vcnt, ccnt = 0, 0
    for item in arr:
        if item in vowels:
            vcnt += 1
        else:
            ccnt += 1

    if vcnt >= 1 and ccnt >= 2:
        return True
    else:
        return False
    
def DFS(tmp):
    if len(tmp) == L:
        # 체킹
        if check(tmp):
            print(''.join(tmp))
            return
    
    # a c i s t w
    for i in range(len(tmp), C):
        if tmp[-1] < arr[i]:
            tmp.append(arr[i])
            DFS(tmp)
            tmp.pop()


for i in range(C-L+1):
    tmp = [arr[i]]
    DFS(tmp)

문제링크

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

문제설명

2 4
CAAB
ADCB

3

3 6
HFDFFB
AJHGDH
DGAGEH

6

문제풀이

백트래킹

DFS의 특성대로 탐색하다가, 더이상 솔루션이 될 수 없다고 판단되면 포기하고 다른 후보를 탐색하는 기법이다.

실수한 부분

1. 처음 DFS시행 전에 시작지점 좌표 방문, 알파벳체크 처리 잊지말자!

2. 불필요한 반복검사 줄이기. (아스키코드 활용하여 알파벳 => 숫자 변환하는 로직을 초반에 따로 빼자.)

    -> 이것도 시간초과에 한몫한듯.

코드

R, C = map(int, input().split())
arr = [list(input()) for i in range(R)]
visited = [[0 for _ in range(C)] for _ in range(R)] 
checked = [0] * 27
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0

# 아스키코드 활용하여 알파벳 => 숫자로 바꾸기
for i in range(R):
    for j in range(C):
        arr[i][j] = ord(arr[i][j]) - 64

def DFS(x, y, cnt):
    global answer
    answer = max(cnt, answer)

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

        # 범위 내에 있고, 방문안한 노드인지
        # arr[nx][ny]가 기존 알파벳들과 다른 알파벳인지
        if 0 <= nx < R and 0 <= ny < C and not visited[nx][ny]:
            if not checked[arr[nx][ny]]:
                visited[nx][ny] = 1
                checked[arr[nx][ny]] = 1
                DFS(nx, ny, cnt+1)
                visited[nx][ny] = 0
                checked[arr[nx][ny]] = 0
            

visited[0][0] = 1
checked[arr[0][0]] = 1
DFS(0, 0, 1)

print(answer)

문제링크

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)