척척석사의 코딩기록

이번에 사용한 알고리즘들인

Manacher Algorithm, Dijkstra, Floyd-Warshall Algorithm에 대해 정리 해보았습니다.

1. Manacher Algorithm

문자열에서 가장 긴 회문 (Palindrome)을 찾기 위한 알고리즘입니다.

2. Dijkstra Algorithm (데이크스트라 알고리즘)

Non-negative weighted graph가 주어져있을 때, 각 Vertices들의 최소 weight 간선을 찾아내는 문제입니다.

3. Floyd - Warshall Algorithm (플로이드 워셜 알고리즘)

2에서의 데이크스트라가 Non-negative만 해당이 되었다면, Floyd Warshall의 경우에는 음의 가중치 또한 허용합니다.

학회 발표 신청을 낸 뒤, 이제 구체적인 결과를 정말 내기 위해 마지막 박차를 가하고 있다보니 ... 

문제를 많이 못 풀게 되었는데, 그래도 틈 나는대로 몇몇 문제들을 풀어보았다.

1. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/description/

class Solution:
    def longestPalindrome(self, s: str) -> str:
        t = '#'.join('^{}$'.format(s))
        print(t)
        n = len(t)
        P = [0] * n
        C = R = 0

        for i in range (1,n-1):
            P[i] = (R > i) and min(R-i, P[2*C - i])
            while t[i + 1 + P[i]] == t[i - 1 - P[i]]:
                P[i] += 1
            if i + P[i] > R:
                C,R = i , i + P[i]
        max_len, answer = max((n,i) for i,n in enumerate(P))
        return s[(answer - max_len)//2 : (answer + max_len) // 2]

2. 전화번호부

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

def solution(phone_book):
    phone_book.sort()
    N = len(phone_book)
    answer = True
    for i in range (0,N-1):
        if len(phone_book[i]) <= len(phone_book[i+1]) and phone_book[i+1][:len(phone_book[i])] == phone_book[i]:
            answer = False
    return answer

3. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = 1
        cnt_zero = 0
        for i in range (0,len(nums)):
            if nums[i] == 0:
                cnt_zero += 1
            else:
                ans *= nums[i]
            
        answer = []
        if cnt_zero == 0:
            for i in range (0,len(nums)): 
                t = ans // nums[i]
                answer.append(t)
        elif cnt_zero == 1:
            for i in range (0,len(nums)):
                if nums[i] == 0:
                    answer.append(ans)
                else:
                    answer.append(0)
        else:
            for i in range (0,len(nums)):
                answer.append(0)
        return answer

4. 의상

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

def solution(clothes):
    dict = {}
    for i in range (0,len(clothes)):
        if clothes[i][1] not in dict:
            dict[clothes[i][1]] = [clothes[i][0]]
        else:
            dict[clothes[i][1]].append(clothes[i][0])
    a = list(dict.values())
    answer = 1
    for i in range (0,len(a)):
        answer *= (len(a[i]) + 1)
    return answer - 1

5. 행렬의 곱셈

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

def solution(arr1, arr2):
    answer = []
    n = len(arr1[0])
    for i in range (0,len(arr1)):
        ans = []
        for j in range (0,len(arr2[0])):
            cnt = 0
            for k in range (0,len(arr1[0])):
                cnt += arr1[i][k] * arr2[k][j]
            ans.append(cnt)
        answer.append(ans)
        
                
    return answer

6. 주식가격

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

from collections import deque
def solution(prices):
    answer = []
    prices = deque(prices)
    while prices:
        x = prices.popleft()
        count = 0
        for i in prices:
            if x > i:
                count += 1
                break
            count += 1
        answer.append(count)
    return answer

7. A → B

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

from collections import deque
A,B = map(int,input().split())
deq = deque([A])
jud = False
dict = {A:1}
while deq:
    c = deq.popleft()
    if c == B:
        jud = True
        print(dict[c])
        break
    else:
        if 2*c > 10**9:
            continue
        else:
            deq.append(2*c)
            dict[2*c] = dict[c] + 1
        if 10*c + 1 > 10** 9:
            continue
        else:
            deq.append(10*c + 1)
            dict[10*c+1] = dict[c] + 1
if deq == deque([]) and jud == False:
    print(-1)

10. 숨바꼭질

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

from collections import deque
N,K = map(int,input().split())
num = [0 for _ in range (0,100001)]
deq = deque()
deq.appendleft(N)
while deq:
    X = deq.popleft()
    if X == K:
        print(num[K])
    else:
        for a in (X-1,X+1,2*X):
            if 0 <= a <= 100000 and num[a] == 0:
                num[a] = num[X] + 1
                deq.append(a)

11. 숨바꼭질 3

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

from collections import deque
MAX = 100001
check = [False] * (MAX+1)
dist = [-1] * (MAX+1)

n,k = map(int, input().split())
deq = deque()
deq.append(n)
check[n] = True
dist[n] = 0

while deq:
    now = deq.popleft()
    if 0 <= now*2 <= MAX and check[now*2] == False:
        deq.appendleft(now*2)
        check[now*2] = True
        dist[now*2] = dist[now]
    if 0 <= now*2 <= MAX and check[now*2] == True:
        dist[now*2] = min(dist[now],dist[now*2])
    if 0 <= now + 1 <= MAX and check[now+1] == False:
        deq.append(now+1)
        check[now+1] = True
        dist[now+1] = dist[now] + 1
    if 0 <= now + 1 <= MAX and check[now+1] == True:
        dist[now+1] = min(dist[now+1],dist[now] + 1)
    if 0 <= now - 1 <= MAX and check[now-1] == False:
        deq.append(now-1)
        check[now-1] = True
        dist[now-1] = dist[now] + 1
    if 0 <= now - 1 <= MAX and check[now-1] == True:
        dist[now-1] = min(dist[now] + 1,dist[now-1])
print(dist[k])

12. 나는 포켓몬마스터 이다솜

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

import sys
N,M = map(int, input().split())
num = {}
name = {}
for i in range(1,N+1):
    pokemon = input()
    num[i] = pokemon
    name[pokemon] = i

for _ in range (0,M):
    x = input()
    if x.isdigit():
        print(num[int(x)])
    else:
        print(name[x])

13. 토마토

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

import copy
from collections import deque
def orangesRotting(m,n,grid):
    checked = [[False for _ in range (0,n)] for _ in range (0,m)]
    deq = deque()
    a = []
    fresh = 0
    for i in range (0,m):
        for j in range (0,n):
            if grid[i][j] == 0:
                fresh += 1
            if grid[i][j] == 1:
                a.append([i,j])
    deq.append(a)
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    day = 0
    #이미 다 상해있는 경우
    if fresh == 0:
        return day
    #그렇지 않은 경우
    while deq:
        k = fresh
        x = deq.popleft()
        rotten_orange = []
        for i in range (0,len(x)):
            for j in range (0,4):
                a = x[i][0] + dx[j]
                b = x[i][1] + dy[j]
                if 0 <= a < m and 0 <= b < n and grid[a][b] == 0 :
                    grid[a][b] = 1
                    fresh -= 1
                    rotten_orange.append([a,b])
        if k == 0:
            break
        if k == fresh:
            return -1
        else:
            day += 1
            deq.appendleft(rotten_orange)
    return day
M,N = map(int,input().split())
A = []
for i in range (0,N):
    a = list(map(int,input().split()))
    A.append(a)
print(orangesRotting(N,M,A))

14. 연결요소의 개수

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

from collections import deque
import sys
input = sys.stdin.readline

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

N, M = map(int, input().split()) 
graph = [[] for _ in range(0,N+1)]
for i in range(0,M):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

count = 0 
visited = [False] * (N+1)
for i in range(1, N+1):
    if not visited[i]:
        bfs(graph, i, visited)
        count += 1
print(count)

15. 회의실 배정

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

import sys
input = sys.stdin.readline
N = int(input())
time = [[0,0] for _ in range (0,N)]
for i in range (0,N):
    a,b = map(int,input().split())
    time[i][0],time[i][1] = a,b

time.sort(key = lambda x:(x[1],x[0]))
cnt = 1
end_time = time[0][1]
for i in range (1,N):
    if end_time <= time[i][0]:
        cnt += 1
        end_time = time[i][1]
print(cnt)

16. 쉬운 최단거리

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

from collections import deque
N,M = map(int,input().split())
graph = []
visited = [[False for _ in range (0,M)] for _ in range (0,N)]
dist = [[0 for _ in range (0,M)] for _ in range (0,N)]
for i in range (0,N):
    a = list(map(int,input().split()))
    graph.append(a)
dx,dy = [0,0,1,-1],[1,-1,0,0]
deq = deque()
for i in range (0,N):
    for j in range (0,M):
        if graph[i][j] == 2:
            deq.append([i,j])
            dist[i][j] = 0

while deq:
    x,y = deq.popleft()
    visited[x][y] = True
    for i in range (0,4):
        a,b = x+dx[i],y+dy[i]
        if 0 <= a < N and 0 <= b < M and visited[a][b] == False:
            if visited[a][b] == False and graph[a][b] == 1:
                dist[a][b] = dist[x][y] + 1
                visited[a][b] = True
                deq.append([a,b])
for i in range (0,N):
    for j in range (0,M):
        if graph[i][j] == 1 and visited[i][j] == False:
            dist[i][j] = -1
        if graph[i][j] == 0:
            dist[i][j] = 0
for i in range (0,len(dist)):
    a = " ".join(str(s) for s in dist[i])
    print(a)

17. 색종이

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

import sys
input = sys.stdin.readline
N = int(input())
cut_paper = []
n = N
while n > 0:
    A,B = [[0 for _ in range (0,n)] for _ in range (0,n)], [[1 for _ in range (0,n)] for _ in range (0,n)]
    n = n//2
    a = []
    a.append(A)
    a.append(B)
    cut_paper.append(a)
paper = []
for i in range (0,N):
    a = list(map(int,input().split()))
    paper.append(a)
cutted = [[False for _ in range (0,N)] for _ in range (0,N)]
M = len(cut_paper)
cnt_blue = 0
cnt_white = 0
for i in range (0,M): #큰 사각형부터 크기를 쪼개보기
    for x in range (0,N,len(cut_paper[i][0])): 
        for y in range (0,N,len(cut_paper[i][0])):#사각형의 꼭짓점 정하기 (x,y로 셋팅)
            jud1 = True
            jud2 = True
            for j in range (0,len(cut_paper[i][0])):
                for k in range (0,len(cut_paper[i][0])):
                    if cut_paper[i][0][j][k] == paper[x+j][y+k] and cutted[x+j][y+k] == False: #흰색인지 확인
                        continue
                    else:
                        jud1 = False
                        break
            for j in range (0,len(cut_paper[i][0])):
                for k in range (0,len(cut_paper[i][0])):
                    if cut_paper[i][1][j][k] == paper[x+j][y+k] and cutted[x+j][y+k] == False: #파란색인지 확인
                        continue
                    else:
                        jud2 = False
                        break
            if jud1 == True:
                for j in range (0,len(cut_paper[i][0])):
                    for k in range (0,len(cut_paper[i][0])):
                        cutted[x+j][y+k] = True #흰색인지 확인
                cnt_white += 1

            if jud2 == True:
                for j in range (0,len(cut_paper[i][0])):
                    for k in range (0,len(cut_paper[i][0])):
                        cutted[x+j][y+k] = True #파란색인지 확인
                cnt_blue += 1
print(cnt_white)
print(cnt_blue)

18. N과 M(5)

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

answer = []
def backtracking(depth,n,m):
    if depth == m:
        answer.append(" ".join(map(str,result)))
    for i in range (0,n):
        if visited[i] == False:
            visited[i] = True
            result.append(A[i])
            backtracking(depth + 1,n,m)
            visited[i] = False
            result.pop()
result = []            
N,M = map(int,input().split())          
A = list(map(int,input().split()))  
A.sort()
visited = [False for _ in range (0,N+1)]
backtracking(0,N,M)
for i in range (0,len(answer)):
    print(answer[i])

19. 플로이드

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

import sys
import math
input = sys.stdin.readline
N = int(input())
M = int(input())
A = [[math.inf for _ in range (0,N)] for _ in range (0,N)]
for i in range (0,M):
    a,b,c = map(int,input().split())
    if A[a-1][b-1] == math.inf:
        A[a-1][b-1] = c
    else:
        A[a-1][b-1] = min(c,A[a-1][b-1])
for k in range (0,N):
    for i in range (0,N):
        for j in range (0,N):
            if i == j:
                A[i][j] = 0
            else:
                A[i][j] = min(A[i][j], A[i][k] + A[k][j])
for i in range (0,N):
    for j in range (0,N):
        if A[i][j] == math.inf:
            A[i][j] = 0
for i in range (0,len(A)):
    print(" ".join(str(s) for s in A[i]))

슬슬 논문 작성과 학회 발표 준비에 바빠지다보니 포스팅이 조금 빈약해진 느낌.

3주차 스터디는 다음과 같은 문제들을 구현해보았다.

1. 연속부분 수열 합의 갯수

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

def solution(elements):
    ans = []
    for i in range (0,len(elements)):
        ans.append(elements[i])
    for i in range (0,len(elements)):
        ans.append(elements[i])
    summary = []
    for i in range (0,len(elements)): #길이를 indicate
        for j in range (1,len(elements)+1): #시작index 저장
            a = sum(ans[i:i+j])
            summary.append(a)
    summary = list(set(summary))
    answer = len(summary)
    
    return answer

2. 이진 변환 반복하기

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

def solution(s):
    removal,ope = 0,0
    while s != "1":
        comp = []
        cnt = 0
        for i in range (0,len(s)):
            if s[i] != "0":
                cnt += 1 #counting을 통해 마지막에 cnt를 2진으로 변환
            else:
                removal += 1 #제거하는 0의 갯수를 counting
        cnt = format(int(cnt), 'b')
        s = cnt
        ope += 1
    return ope,removal

3. Frequency of the Most Frequency Element

https://leetcode.com/problems/frequency-of-the-most-frequent-element/

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        N = len(nums)
        if N == 1:
            return 1
        else:
            nums.sort()
            start,end = 0,0
            result = 0
            summary = 0
            while end < N:
                summary += nums[end]
                while nums[end] * (end - start + 1) > summary + k:
                    summary-= nums[start]
                    start += 1
                result = max(result,end - start + 1)
                end += 1
            return result

4. 3Sum closest

https://leetcode.com/problems/3sum-closest/

class Solution:
    import math
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        N = len(nums)
        nums.sort()
        max_diff = 20001
        ans = 0
        for i in range (0,N):
            start = i + 1
            end = N - 1
            while start < end:
                summary = nums[i] + nums[start] + nums[end]
                c = int(math.fabs(summary - target))
                if summary == target:
                    return target
                else:
                    if c < max_diff:
                        max_diff = c
                        ans = summary
                    if summary < target:
                        start += 1
                    else:
                        end -= 1
        return ans

5. Reduction Operations to Make the Array elements equal

https://leetcode.com/problems/reduction-operations-to-make-the-array-elements-equal/

class Solution:
    def reductionOperations(self, nums: List[int]) -> int:
        nums.sort()
        a = nums[0]
        dict = {}
        for i in range (0,len(nums)):
            if nums[i] in dict:
                dict[nums[i]] += 1
            else:
                dict[nums[i]] = 1
        new_nums = list(dict.values())
        if len(new_nums) == 1:
            return 0
        else:
            cnt = 0
            for i in range (1,len(new_nums)):
                cnt += i * new_nums[i]
            return cnt

6. 2 x n 타일링

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

def solution(n):
    def f(m):
        if m == 1:
            return 1
        elif m == 2:
            return 2
        else:
            dp = [0 for _ in range (m+1)]
            dp[1],dp[2] = 1,2
            for i in range (3,m+1):
                dp[i] = (dp[i-1] + dp[i-2]) % 1_000_000_007
            return dp[-1]
    answer = f(n) % 1_000_000_007
    return answer

7. H-index

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

def solution(citations):
    answer = 0
    M = max(citations)
    for i in range (M,-1,-1):
        cnt = 0
        for j in range (0,len(citations)):
            if citations[j] >= i:
                cnt += 1
        if cnt >= i:
            return i
    return answer

8. n^2 배열 자르기

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

def solution(n, left, right):
    answer = []
    cnt = -1
    a,b = left // n, left % n
    c,d = right// n , right % n
    cnt = -1 + a * n
    for i in range (a,c+1):
        for j in range (0,n):
            cnt += 1
            if left <= cnt <= right:
                answer.append(max(j+1,i+1))       
            if cnt == right:
                break
    return answer

9. Kth Largest element in an array

https://leetcode.com/problems/kth-largest-element-in-an-array/

class Solution:
    import heapq
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for i in range (0,len(nums)):
            heapq.heappush(heap,-nums[i])
        for i in range (0,k-1):
            heapq.heappop(heap)
        a = -heapq.heappop(heap)
        return a

10. Ugly Number

https://leetcode.com/problems/ugly-number/

class Solution:
    import heapq
    def nthUglyNumber(self, n: int) -> int:
        answer = [1]
        heap = [2,3,5]
        dict = {}
        while len(answer) < n:
            b = heapq.heappop(heap)
            answer.append(b)
            if 2 * b not in dict:
                heapq.heappush(heap,2 * b)
                dict[2*b] = 1
            if 3 * b not in dict:
                heapq.heappush(heap,3 * b)
                dict[3*b] = 1
            if 5 * b not in dict:
                heapq.heappush(heap,5 * b)
                dict[5*b] = 1
        return answer[-1]

11. Kth Smallest Element in a Sorted matrix

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

class Solution:
    import heapq
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        heap = []
        for i in range (0,len(matrix)):
            for j in range (0,len(matrix[0])):
                heapq.heappush(heap,matrix[i][j])
        for i in range (0,k-1):
            heapq.heappop(heap)
        a = heapq.heappop(heap)
        return a

12. 이중우선순위큐

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

import heapq
def solution(operations):
    answer = []
    heap1 = [] #최소힙
    heap2 = [] #최대힙으로 사용할 예정
    cnt = 0
    for i in range (0,len(operations)):
        if cnt == 0:
            heap1 = []
            heap2 = []
        a = operations[i][0]
        b = operations[i][2:]
        if a == "I":
            cnt += 1
            heapq.heappush(heap1,int(b))
            heapq.heappush(heap2,-int(b))
        if a == "D":
            #카운트가 하나 이상일 때 진행하겠다
            cnt -= 1
            if cnt < 0:
                cnt = 0
            else:
                #최댓값 저장되어있는 힙에서 제거하기
                if b == "1":
                    heapq.heappop(heap2)
                #최솟값 저장되어있는 힙에서 제거하기
                else:
                    heapq.heappop(heap1)
    list2 = []
    answer = []
    set1 = set(heap1)
    for i in range (0,len(heap2)):
        list2.append(-heap2[i])
    for i in range (0,len(list2)):
        if list2[i] in set1:
            answer.append(list2[i])
    if answer == []:
        return [0,0]
    else:
        return [max(answer),min(answer)]

13. 문자열 폭발

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

import sys
input = sys.stdin.readline
S = input().rstrip()
M = input().rstrip()
n = len(S)
m = len(M)
com = []
for i in range (0,m):
    com.append(M[i])
result = []
if n >= m:
    for s in S:
        result.append(s)
        if result[-m:] == com:
            for i in range (0,m):
                result.pop(-1)
    u = "".join(t for t in result)
else:
    for s in S:
        result.append(s)
    u = "".join(t for t in result)

if u == "":
    print("FRULA")
else:
    print(u)

2주차 스터디 내용은 DFS, BFS를 집중적으로 학습했습니다.

LG전자 코딩테스트도 겹쳐있었던지라 집중적으로 이문제 저문제 풀어봤던 것 같습니다.

내용 및 설명 추가 예정

1. 백준 - 영역 구하기

from collections import deque
M,N,K = map(int,input().split())
A = [[0 for _ in range (0,N)] for _ in range (0,M)]
visited = [[False for _ in range (0,N)] for _ in range (0,M)]
for i in range (0,K): #벽(색칠된 부분) 체크하기
    a =  list(map(int,input().split()))
    for j in range (a[1],a[3]):
        for k in range (a[0],a[2]):
            A[j][k] = 1      
            
dx = [0,0,1,-1]
dy = [1,-1,0,0]
ans = []
for i in range (0,M):
    for j in range (0,N):
        if A[i][j] == 0 and visited[i][j] == False:
            cnt = 1
            deq = deque()
            deq.appendleft((i,j))
            while deq:
                x,y = deq.popleft()
                visited[x][y] = True
                for k in range (0,4):
                    a = x + dx[k]
                    b = y + dy[k]
                    if 0 <= a < M and 0 <= b < N:
                        if A[a][b] == 1:
                            continue
                        if visited[a][b] == False and A[a][b] == 0:
                            deq.appendleft((a,b))
                            visited[a][b] = True
                            cnt += 1
            ans.append(cnt)
ans.sort()
print(len(ans))
print(" ".join(str(s) for s in ans))

어떤 점의 좌표가 주어져있을 때,  그 점의 상하좌우를 전부 훑어보면서 방문한 곳인지 방문하지 않은 곳인지 체크하면서

deque에 추가해주면 됩니다. 방법은 dfs던 bfs던 상관 없을 것 같습니다.

처음으로 방문한 곳은 방문처리를 해서 이후에 올 수 없도록 하는 조치가 필요하겠습니다.

몇개가 붙어있는지 세면 되기 때문에, cnt를 통해 인접한 영역의 갯수를 구하면서 리스트 (ans)에 추가하면 되겠습니다.

ans를 오름차순으로 정렬해준 뒤, 출력해주면 되겠습니다.

2. 프로그래머스 - 미로 탐색

from collections import deque
def solution(maps):
    answer = 0
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    deq = deque()
    deq.append((0, 0))
    n = len(maps) #세로 길이 first component
    m = len(maps[0]) #가로 길이 second component
    check = [[False for _ in range (0,m)] for _ in range (0,n)]
    while deq:
        x,y = deq.popleft()
        check[x][y] = True
        for i in range(0,4):
            a = x + dx[i]
            b = y + dy[i]
            if 0 <= a < n and 0 <= b < m:
                if maps[a][b] == 0:
                    continue
                else:
                    if check[a][b] == False:
                        maps[a][b] += maps[x][y]
                        check[a][b] = True
                        deq.append((a,b))
                    else:
                        maps[a][b] = min(maps[a][b], maps[x][y] + 1)
                    
            else:
                continue
    if maps[-1][-1] == 1:
        return -1
    else:
        return maps[-1][-1]
N,M = map(int,input().split())
A = []
for i in range (0,N):
    a = input()
    b = []
    for j in range (0,len(a)):
        b.append(int(a[j]))  
    A.append(b)
print(solution(A))

동일하게 상하좌우로 막히지 않은 곳을 찾아가면서 도착점까지 가면 되겠습니다.

주의해야할 점은, 이미 방문한 포인트에 있어서는 어떻게 해야하는가? 가 되겠습니다.

그때는 기존값과 새롭게 취한 루트에 대해서의 값을 비교해주면 되겠습니다.

그리고 deque가 비워졌음에도 불구하고 도달하지 못한 경우에는 출구에 도달하지 못했다는 뜻이 되겠습니다.

3. 프로그래머스 - 무인도 여행

from collections import deque
def solution(maps):
    answer = []
    N = len(maps)
    
    A = [[0 for _ in range (0,len(maps[0]))] for _ in range (0,N)]
    for i in range (0,N):
        for j in range (0,len(maps[0])):
            if maps[i][j] == "X":
                A[i][j] = "X"
            else:
                A[i][j] = int(maps[i][j])
    M = len(maps[0])
    visited = [[False for _ in range (0,M)] for _ in range (0,N)]
    #first ex: n = 4, m = 5
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    for i in range (0,N):
        for j in range (0,M):
            if A[i][j] == "X" or visited[i][j] == True:
                continue
            else:
                cnt = A[i][j]
                deq = deque()
                deq.appendleft((i,j))
                while deq:
                    x,y = deq.popleft()
                    visited[x][y] = True
                    for k in range (0,4):
                        a = x + dx[k]
                        b = y + dy[k]
                        if 0 <= a < N and 0 <= b < M:
                            if visited[a][b] == False and A[a][b] != "X":
                                deq.appendleft((a,b))
                                visited[a][b] = True
                                cnt += A[a][b]
                answer.append(cnt)
    answer.sort()
    if answer == []:
        return [-1]
    else:
        return answer

1번과 동일한 유형입니다.

단순히 이 경우에는 각 좌표 (i,j)에 방문할때마다 cnt에 A_ij에 해당하는 값을 더해주면 됩니다.

이후, cnt 값을 리스트에 추가하면서 오름차순으로 정렬하면 정답이 나옵니다.

4. 프로그래머스 - 네트워크

from collections import deque
def solution(n, computers):
    answer = 0
    connection = []
    for i in range (0,n):
        a = []
        deq = deque()
        deq.append((i,i))
        checked = [[False for _ in range (0,n)] for _ in range (0,n)]
        checked[i][i] = True
        a.append(i)
        while deq:
            x,y = deq.popleft()
            a.append(y)
            for z in range (0,n) :
                if computers[y][z] == 1 and checked[y][z] == False:
                    deq.append((y,z))
                    checked[y][z] = True
                    a.append(z)
                else:
                    continue
        a = list(set(a))
        connection.append(a)
    ans = []
    for i in range (0,len(connection)):
        if connection[i] in ans:
            continue
        else:
            ans.append(connection[i])
    answer = len(ans)
    return answer

이 경우에는 Directed graph가 아닌 Undirected Graph입니다.

예를 들어, i와 j가 연결되어있다 한다면 행렬을 만들 때 A_ij = A_ji = 1로서 설정하는 방식으로 행렬 A를 구성해줍니다.

이런 행렬 A를 Adjacency Matrix (인접행렬) 이라고 부릅니다.

결국 각 노드에 방문했을 때 이어져있는 모든 노드를 찾아보는 방식이 되겠습니다.

그렇게 노드의 끝이 어디인지 찾아가는 방식이 되겠네요.

(이 과정에서 연산이 조금 많아질 수 있는데, 이런 경우에는 처음에 A를 받아올 때,

A = [[] for _ in range (0,N)] 이렇게 빈 매트릭스를 만들어준 뒤에, A[i]에 대해서만 사이클을 돌려주면 될 것 같습니다.)

5. 백준 - 케빈 베이컨의 6단계 법칙

import sys
import math
input = sys.stdin.readline
N,M = map(int,input().split())
A = [[math.inf for _ in range (0,N)] for _ in range (0,N)]
for i in range (0,M):
    a,b = map(int,input().split())
    A[a-1][b-1],A[b-1][a-1] = 1,1
for k in range (0,N):
    for i in range (0,N):
        for j in range (0,N):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])
answer = []
for i in range (0,N):
    a = sum(A[i]) - A[i][i]
    answer.append(a)
min_val = min(answer)
for i in range (0,N):
    if answer[i] == min_val:
        print(i+1)
        break

위에서 언급한 Adjacency Matrix의 예 입니다.

친구라는 것이 단방향이 아니라 양방향으로 알고 있는 것을 전제로 하고 있기 때문에, 이렇게 생각해볼 수 있겠습니다.

한편, 행렬 2개를 곱해주면서 그 값이 어떻게 되는지 체크하는 것이겠습니다.

아이디어로서는 i와 j가 알고있고, j가 k가 알고 있다고 하는 상황에서, i와 k의 관계가 어떨까요?

(설명 조금 더 작성)

6. 백준 - 내리막 길 (골드 3)

def f(x,y):
    if x ==  M-1 and y == N-1:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    route = 0
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    for i in range (0,4):
        a = x + dx[i]
        b = y + dy[i]
        if 0 <= a < M and 0 <= b < N and graph[x][y] > graph[a][b]:
            route += f(a,b)
    dp[x][y] = route
    return route
M,N = map(int,input().split())
graph = []
dp = [[-1 for _ in range (0,N)] for _ in range (0,M)]
for i in range (0,M):
    a = list(map(int,input().split()))
    graph.append(a)
print(f(0,0))

7. Leet code - Rotting Oranges (medium)

class Solution:
    import copy
    from collections import deque
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        checked = [[False for _ in range (0,n)] for _ in range (0,m)]
        deq = deque()
        a = []
        fresh = 0
        for i in range (0,m):
            for j in range (0,n):
                if grid[i][j] == 1:
                    fresh += 1
                if grid[i][j] == 2:
                    a.append([i,j])
        deq.append(a)
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]
        day = 0
        #이미 다 상해있는 경우
        if fresh == 0:
            return day
        #그렇지 않은 경우
        while deq:
            k = fresh
            x = deq.popleft()
            rotten_orange = []
            for i in range (0,len(x)):
                for j in range (0,4):
                    a = x[i][0] + dx[j]
                    b = x[i][1] + dy[j]
                    if 0 <= a < m and 0 <= b < n and grid[a][b] == 1 :
                        grid[a][b] = 2
                        fresh -= 1
                        rotten_orange.append([a,b])
            if k == 0:
                break
            if k == fresh:
                return -1
            else:
                day += 1
                deq.appendleft(rotten_orange)
        return day

상한 오렌지는 상하좌우에 있는 오렌지를 전부 상하게 한다는 점에 착목하면 좋을 것 같습니다.

8. 프로그래머스 - 게임 맵 최단거리

from collections import deque
def solution(maps):
    answer = 0
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    deq = deque()
    deq.append((0, 0))
    n = len(maps) #세로 길이 first component
    m = len(maps[0]) #가로 길이 second component
    check = [[False for _ in range (0,m)] for _ in range (0,n)]
    while deq:
        x,y = deq.popleft()
        check[x][y] = True
        for i in range(0,4):
            a = x + dx[i]
            b = y + dy[i]
            if 0 <= a < n and 0 <= b < m:
                if maps[a][b] == 0:
                    continue
                else:
                    if check[a][b] == False:
                        maps[a][b] += maps[x][y]
                        check[a][b] = True
                        deq.append((a,b))
                    else:
                        maps[a][b] = min(maps[a][b], maps[x][y] + 1)
                    
            else:
                continue
    if maps[-1][-1] == 1:
        return -1
    else:
        return maps[-1][-1]

9. Leet code - Course Schedule (medium)

class Solution:
    from collections import deque
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        v = numCourses
        e = len(prerequisites)
        graph = [[] for _ in range (0,v)]
        indegree = [0 for _ in range (0,v)]
        for edge in prerequisites:
            a,b = edge[0],edge[1]
            graph[a].append(b)
            indegree[b] += 1
        deq = deque()
        for i in range (0,v):
            if indegree[i] == 0:
                deq.appendleft(i)
        result = []
        print(deq)
        if len(deq) == 0:
            return False
        A = []
        while deq:
            now = deq.popleft()
            result.append(now)
            for i in graph[now]:
                indegree[i] -= 1
                if indegree[i] == 0:
                    deq.appendleft(i)
        if len(result) != v:
            return False
        return True

위상정렬 (Topological sort)에 대한 개념을 알 수 있었습니다.

일반적인 DFS, BFS와 비슷한 느낌이지만 directed graph를 설정한 후, Route의 끝까지 뚫는 역할을 합니다.

10. 백준 - 전쟁전투 (실버 1)

from collections import deque

N,M = map(int,input().split())
check = [[False for _ in range (0,N)] for _ in range (0,M)]
war = []
for i in range (0,M):
    a = input()
    war_list = []
    for j in range (0,len(a)):
        war_list.append(a[j])
    war.append(war_list)
power1 = 0
power2 = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for i in range (0,M):
    for j in range (0,N):
        if war[i][j] == "W" and check[i][j] == False:
            check[i][j] = True
            deq = deque()
            deq.append((i,j))
            cnt = 0
            while deq:
                x,y = deq.popleft()
                cnt += 1
                for k in range (0,4):
                    a = x + dx[k]
                    b = y + dy[k]
                    if 0 <= a < M and 0 <= b < N and check[a][b] == False and war[a][b] == "W":
                        deq.append((a,b))
                        check[a][b] = True
            power1 += cnt ** 2
        if war[i][j] == "B" and check[i][j] == False:
            check[i][j] = True
            deq = deque()
            deq.append((i,j))
            cnt = 0
            while deq:
                x,y = deq.popleft()
                cnt += 1
                for k in range (0,4):
                    a = x + dx[k]
                    b = y + dy[k]
                    if 0 <= a < M and 0 <= b < N and check[a][b] == False and war[a][b] == "B":
                        deq.append((a,b))
                        check[a][b] = True
            power2 += cnt ** 2
print(power1,power2)

11. 백준 - 숨바꼭질 2 (골드 5)

from collections import deque
N,K = map(int,input().split())
if N >= K:
    print(N-K)
    print(1)
else:
    cnt = 0
    num = [0 for _ in range (0,100001)]
    deq = deque()
    deq.appendleft([N])
    while deq:
        X = deq.popleft() #리스트로 받아옴
        B = []
        for i in range (0,len(X)):
            for y in (X[i] - 1, X[i] + 1, 2 * X[i]):
                if y > 100000 or y < 0:
                    pass
                else:
                    if num[y] == 0 or num[y] == num[X[i]] + 1:
                        B.append(y)
                        if y == K:
                            cnt += 1
                        num[y] = num[X[i]] + 1
                    else:
                        if y == K:
                            cnt += 1
        deq.appendleft(B)
        if cnt != 0:
            break
        else:
            continue
    print(num[K])
    print(cnt)

12. 프로그래머스 - 타겟 넘버

from collections import deque
def solution(numbers, target):
    answer = 0
    deq = deque()
    deq.append([numbers[0],-numbers[0]])
    cnt = 1
    while cnt < len(numbers):
        A = deq.popleft()
        B = []
        for i in range (0,len(A)):
            B.append(A[i]-numbers[cnt])
            B.append(A[i]+numbers[cnt])
        deq.append(B)
        cnt += 1
    for i in range (0,len(deq[0])):
        if deq[0][i] == target:
            answer += 1
    return answer

코딩테스트 대비 스터디를 시작하면서, 첫 주차 알고리즘은 완전 탐색(Brute Force).

대표문제로서 선택된 것이 프로그래머스 - 카펫 (Level 2)

1. 카펫

해당 문제 풀이 코드는 이하와 같습니다.

#풀이 1 (Yellow 활용)
import math
def solution1(brown, yellow):
    a = brown + yellow #전체 타일 갯수 a
    for i in range (1,int(math.sqrt(a))+1): #a = i * (a//i) = i * b (i <= b)
        if a % i == 0:
            b = a // i 
            if (i - 2) * (b - 2) == yellow: #yellow = (i-2) * (b-2)
                answer = [b,i]
                return answer

#풀이 2 (전체 활용)
def solution2(brown,yellow):
    for i in range (1,int(math.sqrt(yellow))+1): #yellow = i * (yellow//i) = i * b (i <= b)
        if yellow % i == 0:
            b = yellow // i 
            if (i + 2) * (b + 2) == brown + yellow: #brown + yellow = (i+2) * (b+2)
                answer = [b+2,i+2]
                return answer
brown,yellow = map(int,input().split())
print(solution1(brown,yellow))
print(solution2(brown,yellow))

첫 번째는, Yellow 타일과 Brown 타일의 개수를 합친다면 전체 타일 개수가 나온다는 점을 활용하는 풀이

주목할 점은 Yellow 타일의 개수 = (타일의 가로길이 - 2) * (타일의 세로길이 - 2)라는 점입니다.

그래서, 전체 타일 갯수 a  = i * (a // i) (가로 x 세로)로 나눈 뒤, 

yellow = (i - 2) * (a // i - 2)가 되는지 확인하는 방법입니다.

두 번째는, 첫 번째의 반대 순서로 생각해내가는 방법입니다.

브루트포스 방법으로 한다면, 아마 다음과 같이 되지 않을까 싶습니다.

이후, 따로 준비한 문제 두 개는 백준 1051번 숫자 정사각형  (실버 3), 백준 2468 안전 영역 (실버 1)이다.

숫자 정사각형은 정직하게 풀면 쉽게 풀리고, 안전 영역은 DFS, BFS와 연관 지을 수 있기 때문에 추가적으로 학습했다.

2. 숫자 정사각형

#BOJ 1051 숫자정사각형 실버3
N,M = map(int,input().split())
A = []
for i in range (0,N):
    a = list(str(input()))
    A.append(a)
ans = []
for i in range (1,N+1):
    for x in range (0,N-i+1):
        for y in range (0,M-i+1):
            B = list(set([A[x][y],A[x][y+i-1],A[x+i-1][y],A[x+i-1][y+i-1]]))
            if len(B) == 1:
                ans.append(i*i)
            else:
                continue
print(max(ans))

아이디어는 n  * n 정사각형을 생각 한 뒤, 각 정사각형의 꼭짓점이 (시작점 A[i][j]을 포함하여) A[i][j+n-1],A[i+n-1][j] , A[i+n-1][j+n-1] 으로 나타내어진다는 것에 주목하면 좋다.

만약, 위 네점에 해당하는 값이 전부 같다면, set 함수를 사용하여 중복되는 값들을 전부 삭제할 수 있기 때문에 set( - )의 길이는 1이 되겠다.

하지만 한 점이라도 해당하는 값이 다르다면, set에 의해 만들어지는 튜플의 길이가 2 이상이 되기 때문에 간단하게 판단할 수 있다.

ex) 1,1,1,2 -> 1,2  / 2,2,2,2 -> 2 / 3,2,3,4 -> 2,3,4 .....

이후, 만약 set에 의해 생성되는 튜플의 길이가 1이라면 정사각형의 넓이는 n * n 으로 주어지므로 이를 ans에 추가.

(혹은 max 함수를 사용하는 것도 좋아보인다.)

그 뒤 ans의 최댓값을 반환하면 끝.

3. 안전 지대

from collections import deque
N = int(input())
A = []
max_height = 0
for i in range (0,N):
    a = list(map(int,input().split()))
    max_height = max(max(a),max_height)
    A.append(a)

def move(x,y,h):
    dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
    z = []
    for i in range (0,4):
        a = x + dxdy[i][0]
        b = y + dxdy[i][1]
        if 0 <= a < N and 0 <= b < N and A[a][b] > h:
            z.append([a,b])
    return z
ans = []

for height in range (0,max_height):
    cnt = 0
    visited = [[False for _ in range (0,N)] for _ in range (0,N)]
    for i in range (0,N):
        for j in range (0,N): 
            if A[i][j] > height and visited[i][j] == False:
                visited[i][j] = True
                a = deque([])
                a.appendleft([i,j])
                while a:
                    c = a.popleft()
                    visited[c[0]][c[1]] = True
                    b = move(c[0],c[1],height)
                    for area in b:
                        if visited[area[0]][area[1]] == False:
                            visited[area[0]][area[1]] = True
                            a.appendleft([area[0],area[1]])
                cnt += 1
    ans.append(cnt)      
print(max(ans))

아이디어는 다음과 같다.

1. 최고 높이 max_height 구하기 (for문을 통해 0~max_height까지 전부 체크하기 위함)

2. DFS, BFS를 통하여 연결 요소의 갯수를 구하기

(이 과정에서 높이가 1에서 구한 변수보다 높은지 판정이 필요함)

3. 연결요소의 갯수를 저장하는 리스트를 만든 뒤, 그 뒤 최댓값 반환

느낀 점

브루트포스 알고리즘에서 백트래킹 (끝까지 탐색을 완료하면 뒤로 돌아가는)에 관련된 문제가 많았다는 것을 알 수 있었다.

또한 DFS,BFS와 연계되어있는 문제가 많아 보이므로 그 부분에 대해 추가 공부를 하는 것도 좋아 보인다.