YB 공부 블로그

from collections import deque
 
def solution(board, moves):
    answer = 0
 
    # moves-1 위치에 있는 것 뽑기
 
    temp = deque()
 
    for i in range(0,len(moves)):
        index = moves[i]-1
 
        for j in range(0,len(board)):
            if board[j][index]!=0:    
 
 
 
                if len(temp)!=0:
                    if temp[-1]==board[j][index]:
 
                        answer+=2
                        temp.pop()
                        board[j][index]=0
                        break
                    else:
                        temp.append(board[j][index])
                        board[j][index]=0
                        break
                else:
                    temp.append(board[j][index])
                    board[j][index]=0
                    break
 
 
 
 
 
 
 
 
 
 
 
    return answer

from itertools import combinations
 
 
n = int(input())
 
k = [ ]
 
 
 
for i in range(n):
    k.append(input())
 
 
k = list(sorted(k))
 
count = len(k)
 
for i in range(0,len(k)-1):
    if k[i+1].startswith(k[i])==True:
        count-=1
 
 
 
print(count)
 

from collections import deque
 
M,N = list(map(int,input().split(" ")))
 
k = [ ]
 
 
 
def bfs(k,x1,y1,M,N):
 
    dx = [1,1,1,0,-1,-1,-1,0]
    dy = [1,0,-1,-1,-1,0,1,1]
 
    k[x1][y1] = 0
 
    queue = deque()
    queue.append([x1,y1])
 
    while queue:
 
        x,y = queue.popleft()
 
        for i in range(0,len(dx)):
 
            temp_x = x + dx[i]
            temp_y = y + dy[i]
 
            if 0<=temp_x<M and 0<=temp_y<N and k[temp_x][temp_y]==1:
                k[temp_x][temp_y] = 0
                queue.append([temp_x,temp_y])
 
 
for i in range(M):
 
 
    k.append(list(map(int,input().split(" "))))
 
answer = 0
 
for i in range(0,M):
    for j in range(0,N):
 
        if k[i][j] == 1:
 
            answer += 1
 
            bfs(k,i,j,M,N)
 
 
print(answer)
 

 
 
# 프로세스
 
# deque를 이용했고 2차원 리스트를 이용했다.
 
from collections import deque
 
def maxs(k):
 
    m = 0
 
    for i in range(0,len(k)):
        if k[i][1]>m:
            m = k[i][1]
 
    return m
 
 
def solution(priorities, location):
    answer = 1
 
    k = []
 
    for i in range(0,len(priorities)):
        k.append([i,priorities[i]])
 
    k = deque(k)
    # 번호/우선순위 순서    
 
 
    while True:
 
 
        temp = k[0]
 
        # 찾으면
 
        if temp[0] == location and temp[1] ==maxs(k):
            print(k)
            return answer        
 
 
        # 찾는 건 아닌데 최대면
        elif temp[0] != location and temp[1] ==maxs(k):
            k.popleft()
            answer+=1
 
        # 아무것도 아니면  
        else:
            k.append(k.popleft())
 
 
 
 
 
    return answer

 
 
# 정수 삼각형
 
# 누적으로 풀었다. 풀어본 유형이여서 쉽게 풀 수 있었다.
 
n = int(input())
 
k = [ ]
 
for i in range(n):
    k.append(list(map(int,input().split(" "))))
 
 
 
if n==1:
    print(k[0][0])
 
elif n==2:
    print(max(k[1][1]+k[0][0],k[1][0]+k[0][0]))
 
else:
 
    k[1][1] += k[0][0]
    k[1][0] += k[0][0]
 
 
    for i in range(2,n):
 
        for j in range(0,len(k[i])):
 
            if j==0:
                k[i][0] += k[i-1][0]
 
 
 
            elif j==len(k[i])-1:
                k[i][j] += k[i-1][j-1]
 
            else:
                k[i][j] += max(k[i-1][j],k[i-1][j-1])
 
 
    print(max(k[-1]))
 
 
 
 
 
 
 
 
 

# 가장 긴 감소하는 부분 수열 
 
# 가장 긴 증가하는 부분 수열을 반대로만 작성하면 풀리는 문제이다. 풀이는 암기가 되었는데
# 확실하게 과정을 이해를 해야겠다.
 
 
from collections import deque
 
 
n = int(input())
 
k = list(map(int,input().split(" ")))
 
dp = [1]*(n+1)
 
 
 
for i in range(1,len(dp)-1):
    for j in range(0,i):
 
        if k[i]<k[j]:
 
            dp[i] = max(dp[j]+1,dp[i])
 
 
print(max(dp))

디자인 패턴 : 프로그램을 설계할 때 발생했던 문제점들을 객체 간의 상호 관계 등을 이용하여 해결할 수 있도록 하나의 ‘규약’ 형태로 만들어 놓은 것

싱글톤 패턴 

- 하나의 클래스에 오직 하나의 인스턴스만 가지는 패턴

- 보통 데이터베이스 연결 모듈에 많이 사용한다.

- 스프링에서는 @Component 어노테이션을 통해 이를 구현함

- 인스턴스 생성 비용이 줄지만 의존성이 높아진다는 단점 존재

- TDD를 할 때 단점임

- 의존성 주입을 통해 모듈 간의 결합을 조금 더 느슨하게 만들 수 있다.

- 의존성 주입을 통해 간접적으로 주입할 수 있다.

팩토리 패턴

- 객체를 사용하는 코드에서 객체 생성 부분을 떼어내 추상화한 패턴

- 상위와 하위 클래스가 분리 -> 유연성을 가질 수 있다.

- 유지 보수성이 증가한다.

전략 패턴 

-  객체의 행위를 바꾸고 싶은 경우 ‘직접’ 수정하지 않고 전략이라고 부르는 ‘캡슐화한 알고리즘’을 컨텍스트 안에서 바꿔주면서 상호 교체가 가능하게 만드는 패턴

옵저버 패턴 

- 주체가 어떤 객체(subject)의 상태 변화를 관찰하다가 상태 변화가 있을 때마다 메서드 등을 통해 옵저버 목록에 있는 옵저버들에게 변화를 알려주는 디자인 패턴

- 주로 이벤트 기반 시스템에 사용 ex)트위터, MVC 패턴

프록시 패턴 

- 객체의 접근에 대한 흐름을 가로채 대상 객체 앞단의 인터페이스 역할을 하는 디자인 패턴

-

import sys
from collections import deque
 
input = sys.stdin.readline
 
# 10%에서 메모리 초과 -> check 함수 내의 리스트 길이 때문인 것 같음.
# 리스트에 넣는 것이 아닌 선언된 리스트를 이용해서 해결하는 방법을 알게 됌.
 
 
# 각 섬을 2~n+1 까지의 숫자로 채우기
 
def bfs(k,index,x,y):
 
    # 시작 위치 x,y
 
    queue = deque()
 
    queue.append([x,y])
 
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
 
    while queue:
 
 
        a,b = queue.popleft()
 
        k[a][b] = index
 
        for i in range(4):
 
            temp_x = a + dx[i]
            temp_y = b + dy[i]
 
            if 0<=temp_x<len(k) and 0<=temp_y<len(k) and k[temp_x][temp_y] == 1:
                queue.append([temp_x,temp_y])
 
 
 
# BFS 돌면서 최단 값 찾기
 
def check(k,i,j):
 
    count = 0
 
    queue = deque()
 
    queue.append([i,j])
 
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
 
    compare = k[i][j]
 
    temp = [ ]
 
    while queue:
 
        a,b = queue.popleft()
 
        for i in range(4):
 
            temp_x = a + dx[i]
            temp_y = b + dy[i]
 
            if 0<=temp_x<len(k) and 0<=temp_y<len(k):
 
                # 다른 섬을 만났을 때
 
                if k[temp_x][temp_y]!=0 and k[temp_x][temp_y]!=compare:
                    return count
 
                else:
 
                    # 이 부분이 문제
 
                    if k[temp_x][temp_y]==0:
                        temp.append([temp_x,temp_y])
 
 
        if len(queue) == 0:
            queue = deque(temp)
            count += 1
            temp = [ ]
 
 
 
    return 1000000
 
 
 
 
 
 
 
# 0은 바다, 1은 육지
 
 
n = int(input())
 
k = [ ]
 
for i in range(n):
    k.append(list(map(int,input().split(" "))))
 
 
 
index = 2
 
for i in range(0,len(k)):
    for j in range(0,len(k)):
        if k[i][j] == 1:
            bfs(k,index,i,j)
            index+=1
 
 
 
# 각 섬의 모든 구간에서 다른 섬의 최솟값 구하기
 
answer = 1000000
 
for i in range(0,len(k)):
    for j in range(0,len(k)):
 
 
        if k[i][j] != 0:
            answer= min((check(k,i,j),answer))
 
print(answer)
 
 
 
 
'''
 
check 함수 정답 코드
 
 
 
 
def bfs2(z):
    global answer
    dist = [[-1] * n for _ in range(n)] # 거리가 저장될 배열
    q = deque()
 
    for i in range(n):
        for j in range(n):
            if arr[i][j] == z:
                q.append([i, j])
                dist[i][j] = 0
 
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 갈 수 없는 곳이면 continue
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            # 다른 땅을 만나면 기존 답과 비교하여 짧은 거리 선택
            if arr[nx][ny] > 0 and arr[nx][ny] != z:
                answer = min(answer, dist[x][y])
                return
            # 바다를 만나면 dist를 1씩 늘린다.
            if arr[nx][ny] == 0 and dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                q.append([nx, ny])
 
 
 
'''