참조 https://velog.io/@gkdis6/알고리즘-강한-연결-요소-추출-알고리즘-Strongly-Connected-Component https://mobuk.tistory.com/120 https://velog.io/@namsh1125/%ED%83%80%EC%9E%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

• DFS 1번을 기반으로 SCC를 찾는 알고리즘
• O(V+E)의 시간복잡도를 가짐
• 코사라주 알고리즘보다 구현이 어렵지만 DFS 1번으로 SCC를 구할 수 있음.

Strongly Connected Components(SCC)

• 위 그림에서 (1,2,5)는 연결되어 있는 동시에 1은 2,5를 방문가능하고 2는 1,5를 방문가능하며 5는 1,2를 방문가능하다. 즉, 모든 정점이 다른 정점에 대해 방문가능하여 SCC이다.
  • 한 정점에서 다른 모든정점으로 직접적인 연결이 되어있다는 의미는 아니다.
  • 다른 정점을 지나서 도달할 수 있다는 의미이다.
• 하지만 3이 추가될 경우, (1,2,3,5)는 SCC가 아니다.

• 즉, SCC는 위처럼 한 노드에서 출발해 다른 노드들을 거쳐 다시 자기자신으로 돌아올 수 있는 cycle을 뜻한다.

과정

• 위의 그래프를 예시로, 정점 A부터 탐색
• Finished(parents)배열은 SCC판별이 끝났는지 저장
• visited 배열은 해당 정점을 방문하였는지 저장

• 먼저, A를 첫번째로 방문했기 때문에 A에 id=1을 부여하고 스택에 삽입
• A의 visited 갱신
• A에서 B로 이동가능함
  • B는 탐색이 되어있지 않으므로, A가 부모노드인지 판별불가
• 이후, A에서 이동 가능한 B를 탐색

• B에 id=2를 부여하고 스택에 삽입
• B의 visited 갱신
• B에서 C,E,F로 탐색가능
  • 각 노드들이 탐색되어 있지 않으므로 B가 부모노드인지 판별불가
• 노드중 가장 작은 C를 먼저 탐색(알파벳순이라고 가정)

• C에 id=3을 부여하고 스택에 삽입
• C의 visited 갱신
• C에서 D,G로 탐색가능
  • 각 노드들이 탐색되어 있지 않으므로 C가 부모노드인지 판별불가
• 노드중 가장 작은 D를 먼저탐색

• D에 id=4를 부여하고 스택에 삽입
• D의 visited 갱신
• D에서 H로 탐색가능
  • H는 탐색되어 있지 않으므로 D가 부모노드인지 판별불가
• H를 탐색

• H에 id=5를 부여하고 스택에 삽입
• H의 visited 갱신
• H에서 H로 이동가능
  • H는 탐색되어있음(자기자신)
  • 스택에서 부모노드인 H가 나올 때 까지빼내고 Finished 배열을 갱신
  • SCC배열에 저장
• 이전으로 되돌아감(D)

• D와 연결되어 있는 C,H의 부모정점이 본인이 아니기 때문에 본인의 부모인 C를 반환해주고 C로 이동(4≠min(3,5), 3으로 이동)
• C에서 이동가능한 D,G중 D는 방문정보가 있지만 G는 없으므로 G를 방문

• G에 id=6을 부여하고 스택에 삽입
• G의 visited 갱신
• G에서 F로 이동가능
  • F는 탐색되어 있지 않으므로 G가 부모노드인지 판별 불가
• F를 탐색

• F에 id=7을 부여하고 스택에삽입
• F의 visited 갱신
• F에서 G를 방문가능한데, G는 이미 방문한 배열이므로, 작은 G를 반환하고 이전으로 이동
• 다시 G로 되돌아왔고, 이제 G에서 F,H의 정보가 있으니 부모정점인지 판별
  • F의 부모는 본인(G)이고, H는 이미 SCC이다(Finished되어있음)
  • 스택에서 본인이 나올때까지 빼서 SCC에 추가하고 finish배열을 갱신
• 이전으로 돌아감

• C에 되돌아와서, 이제 C에서 연결된 G,D의 정보가 있으니 부모정점인지 판별
  • D의 부모는 본인(C)이고, G는 이미 SCC이다.
  • 스택에서 본인이 나올때까지 빼서 SCC에 추가하고 finish배열을 갱신
  • 이전으로 되돌아감

• B로 되돌아와서, 이제 C는 탐색되었지만 E와 F가 탐색되어있지 않음
• E를 탐색

• E에 id=8을 부여하고 스택에 삽입
• E의 visited를 갱신
• E에서 A,F로 이동가능
  • A는 방문되어있고, F는 이미 SCC이다.
  • 그러므로, 본인의 부모정점인 A 반환(min(1,8))
• 이전으로 되돌아감
• 이제 B에서 본인이 부모정점인지 판별
  • C와 F는 이미 SCC이고, E에서 반환받은 부모정점은 본인이 아님.
  • 그러므로, 부모정점을 판별(min(2,1)하면 A가 본인의 부모정점이 된다.
  • 스택에서 본인이 나올 때 까지 SCC에 추가하고 finished배열을 갱신

• SCC가 완성되었다.

백준 2150

import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline

V,E=map(int,input().split())

graph=[[] for _ in range(V+1)]
parents=[-1]*(V+1)
for _ in range(E):
    a,b=map(int,input().split())
    graph[a].append(b)

stk=[]
visit=[0]*(V+1)
id=0
res=[]
def func(now):
    global id
    id+=1
    parents[now]=id
    stk.append(now)
    visit[now]=1
    parent=parents[now]

    for next in graph[now]:
        if parents[next]==-1:
            parent=min(parent,func(next))
        elif visit[next]:
            parent=min(parent,parents[next])

    if parent==parents[now]:
        scc=[]
        while True:
            node=stk.pop()
            visit[node]=0
            scc.append(node)
            if now==node:
                break
        res.append(sorted(scc)+[-1])
    return parent

for i in range(1,V+1):
    if parents[i]==-1:
        func(i)
res.sort()
print(len(res))
for i in res:
    print(*i)

암기하기 쉽게 변형(백준 11278)

N,M=map(int,input().split())
graph=[[] for _ in range(2*N+1)]
for i in range(M):
    x,y=map(int,input().split())
    graph[-x].append(y)
    graph[-y].append(x)

stk=[]
visit=[0]*(2*N+1)
finish=[0]*(2*N+1)
scc_idx=[0]*(2*N+1)

id=1
scc_id=1
def func(now):
    global id,scc_id
    parent=id
    visit[now]=id
    id+=1
    stk.append(now)

    for next in graph[now]:
        if not visit[next]:
            parent=min(parent,func(next))
        if not finish[next]:
            parent=min(parent,visit[next])

    if parent==visit[now]:
        while stk:
            top=stk.pop()
            finish[top]=1
            scc_idx[top]=scc_id
            if top==now:
                break
        scc_id+=1
    return parent

for i in range(1,2*N+1):
    if not visit[i]:
        func(i)

res=[0]*(N)
for i in range(1,N+1):
    if scc_idx[i]==scc_idx[-i]:
        print(0)
        break
    if scc_idx[i]<scc_idx[-i]:
        res[i-1]=1
else:
    print(1)
    print(*res)

참고사이트 [Network 04] Persistent Connection을 위한 기술 01 - Keep Alive (TCP, HTTP) Nginx 의 keep-alive 를 조정하여 성능을 개선해보자! (https://velog.io/@realsnoopso/Stateless-와-Connectionless-의-차이)

1. Stateless와 Connectionless에 대해 설명해 주세요.

Stateless

• 서버가 클라이언트의 상태정보를 저장하지 않는 구조
• 클라이언트의 요청마다 독립적으로 처리되며, 각각의 요청때마다 필요한 모든 정보가 포함되어 전달되어야 함

Connectionless

• 서버와 클라이언트가 통신할 때 연결을 유지하지 않는 구조
• 한번 요청 및 응답이 끝나면 연결을 종료시켜버림(매번 연결을 새로 맺어야 함)

2. 왜 HTTP는 Stateless 구조를 채택하고 있을까요?

• 확장성, 단순성, 데이터일관성 때문
• 각 요청은 서로 독립적이어야 함. 서버에 요청에 대한 정보를 기억할 필요가 없으므로 개발과 유지 보수가 더 단순해짐.
• 서버가 각 클라이언트의 상태를 추적할 필요가 없으므로 수천 또는 수백만 사용자를 처리하는 대규모 서비스에 적합함. 상태 정보를 저장하고 관리하지 않아도 되므로, 서버 자원을 효율적으로 사용할 수 있고, 로드 밸런싱이 쉽게 구현됨.
• 각 요청과 응답이 독립적이므로, 여러 서버가 동일한 요청을 처리할 수 있음. 이는 분산 시스템에서 매우 중요
• 클라이언트 상태를 유지할 필요가 없으므로 서버는 빠르게 응답을 보낼 수 있음, 또 여러 서버 사이에서 데이터 일관성 문제가 발생할 가능성이 줄어듦.

왜 HTTP는 connectionless를 채택했을까?

• 서버의 자원 효율적 관리
• 수 많은 클라이언트의 요청에도 대응할 수 있게 하기 위해서
• 수 천명이 서비스를 사용해도 실제 서버에서 동시에 처리하는 요청은 수 십개 이하로 작음

3. Connectionless의 논리대로면 성능이 되게 좋지 않을 것으로 보이는데, 해결 방법이 있을까요?

HTTP 성능의 한계

• 매번 TCP/IP 연결을 새로 맺어야 하므로 3-way handshake에 따른 시간이 추가됨
• HTML을 받기 위해 연결/끊기, JS파일 받기 위해 연결/끊기..

해결

• HTTP1.1에는 keep-alive옵션, HTTP/2 부터는 서버푸시로 최적화 함
  • keep-alive: 여러개의 파일을 송수신할 수 있음

      ![](https://velog.velcdn.com/images/www-jong/post/05986d21-1a21-4896-9d56-bcf122d271f0/image.png)

  • 서버푸시: HTML보내고, 서버가 바로 CSS, JS파일 보낼 수 있음

전체적으로 필요한 부분에는 커넥션 유지를 하는 듯

• HTTP 지속 연결(Persistent Connections)으로 문제 해결

📌keep-alive

4. TCP의 keep-alive와 HTTP의 keep-alive의 차이는 무엇인가요?

TCP keep-alive

• TCP 수준에서 연결이 활성상태인지 확인하기 위해 사용되는 기능
• 일정시간동안 데이터 교환이 없을 경우 Keep-alive 패킷을 송수신해 연결 유효성 검사
• 연결을 유지하기 위해 사용(like healthcheck)

HTTP Keep-alive

• HTTP 프로토콜 수준에서 동작
• 얼마동안 연결을 유지할 것인지가 목적
• Http Header를 통해 전달
• 클라이언트-서버간 여러 HTTP 요청/응답을 하나의 TCP 연결로 처리할 수 있도록 함
• HTTP/1.0+ 에서는 persistent connection을 위해서 헤더에 명시를 했어야함
• HTTP/1.1 부턴 기본값으로 지원

풀이

우선순위 제거

각각의 일은 우선순위 작업이 없거나 1개가 존재한다. 우선순위를 계산하면서 kanpsack을 하기엔 복잡하므로 우선순위를 제거한다. 먼저, 예제 1번을 예로들어

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

로 입력이 제공될 경우,

• 1,4,6,7번은 우선순위 작업이 필요없음
• 2번은 1번을 먼저 작업해야함
• 3번은 2번을 먼저 작업해야함
• -> 1,2번을 해야 3번을 할 수 있다.
• 5번은 4번을 먼저 작업해야함

위를 응용하면 3번작업을 수행했다고 가정할때, 1번과 2번작업또한 수행했다는 결과가 나온다. 이를 이용해 우선순위 작업이 있는 작업들은 해당 작업을 수행하는데 필요한 우선순위 작업들의 w와 t를 합쳐주어 w와 t리스트를 갱신시켜준다.

아래처럼 w와 t를 갱신(ex. 3번작업을 수행한다는 것은 1,2번 작업을 했다는 뜻이므로, 해당 작업들의 w와 t를 3번 작업에 합쳐준다)

7 7
w : 2 3 1 4 5 1 3
t : 3 4 2 8 6 1 2
p : 0 1 2 0 4 0 0
-->
w : 2 5 6 4 9 1 3
t : 3 7 9 8 14 1 2

그룹 묶기

위처럼 w와 t가 갱신되었다면, 이제 그룹을 묶을 차례이다. 우선순위가 제거된 현재 작업에서는 1번,2번,3번 작업을 2개이상 처리할 수 없다.(2번작업에는 1번작업이 포함되어 있고, 3번작업에는 1,2번 작업이 포함되어 있으므로) 그러므로, 기존의 부모노드격인 1,4,6,7(우선순위가 없는 작업들)에 파생되는 작업들을 하나로 묶어준다.

자기자신도 포함시켜준다.

1번작업의 파생작업 : 1,2,3
4번작업의 파생작업 : 4,5
6번작업의 파생작업 : 6
7번작업의 파생작업 : 7

knapsack 알고리즘

기존의 knapsack 알고리즘(1차원 dp이용)의 시간복잡도는 아래와 같다.

O(N*M), N: 배낭용량, N: 넣을 물건들

하지만 주어진 중요도(배낭용량)의 최대값이 100,000이고 작업의 수(넣을 물건들)이 1,000이므로 시간복잡도를 고려해, dp를 dictionary로 선언하여 갱신시켜준다.

초기 dp를 선언해주고, n번 작업의 파생작업에 대해 for문 작업시마다 임시 dictionary를 선언하여 사용한다. dp for문을 돌면서 item이 추가되기 때문이다.

반복문을 돌면서 갱신되는 업무중요도가 S이상이 될 경우, 결과값을 갱신시켜주고 dp배열에는 추가하지 않는다(의미가 없다. 중요도가 S 이상만 넘을때의 최소 시간을 계산해야 하므로)

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
N,S=map(int,input().split())
res=10**9
w=[0]+list(map(int,input().split()))
t=[0]+list(map(int,input().split()))
p=[0]+list(map(int,input().split()))
graph=[[] for _ in range(N+1)]
dic={}
for i in range(1,N+1):
    graph[p[i]].append(i)

def func(now,time,work,parent):
    if parent!=0:
        if parent in dic:
            dic[parent].append(now)
        else:
            dic[parent]=[now]
    w[now]+=work
    t[now]+=time
    for i in graph[now]:
        func(i,t[now],w[now],i if parent==0 else parent)

func(0,0,0,0)

dp={}
for _,jobs in dic.items():
    tmp={}
    for job in jobs:
        for work,time in dp.items():
            total_work=work+w[job]
            total_time=time+t[job]
            if total_work<S:
                if total_work in tmp:
                    tmp[total_work]=min(total_time,tmp[total_work])
                else:
                    tmp[total_work]=total_time
            else:
                res=min(res,total_time)
        if w[job]<S:
            if w[job] in tmp:
                tmp[w[job]]=min(tmp[w[job]],t[job])
            else:
                tmp[w[job]]=t[job]
        else:
            res=min(res,t[job])

    for work,time in tmp.items():
        if work in dp:
            dp[work]=min(dp[work],tmp[work])
        else:
            dp[work]=tmp[work]
print(res if res!=10**9 else -1)

풀이

LCA문제인데 depth를 사용하면 안된다.

또한, paint와 count 연산 시 a번 노드와 b번 노드 사이의 최단경로의 길이는 항상 1,000 이하이다.

위 문구를 통해 문제를 해결해야 한다. 즉, LCA를 반복문으로 진행해서 구해내야 한다. 부모노드와 간선의 색상(부모노드a에서 자식노드b로 이어지는 간선을 color[b]로 둔다)만 구해서 사용한다.

시간초과된 풀이(36%)

import sys
input=sys.stdin.readline

N,K=map(int,input().split())
son=[set() for _ in range(N)]
son[0]={i for i in range(1,N)}
depth=[1]*N
parent=[0]*N
color=[0]*N

depth[0]=0

def count_color(a,b):
    colors=set()
    while depth[a]!=depth[b]:
        if depth[a]>depth[b]:
            colors.add(color[a])
            a=parent[a]
        else:
            colors.add(color[b])
            b=parent[b]
    while a!=b:
        colors.add(color[a])
        colors.add(color[b])
        a=parent[a]
        b=parent[b]
    return len(colors)
def fix_depth(x,val):
    depth[x]=val
    if not son[x]:
        return
    for i in son[x]:
        fix_depth(i,val+1)

def fix_color(a,b,val):
    while depth[a]!=depth[b]:
        if depth[a]>depth[b]:
            color[a]=val
            a=parent[a]
        else:
            color[b]=val
            b=parent[b]
    while a!=b:
        color[a]=val
        color[b]=val
        a=parent[a]
        b=parent[b]

def lca(a,b):
    while depth[a]!=depth[b]:
        if depth[a]>depth[b]:
            a=parent[a]
        else:
            b=parent[b]
    while a!=b:
        a=parent[a]
        b=parent[b]
    return a

for _ in range(K):
    tmp=list(map(int,input().split()))
    r=tmp[0]
    if r==1: #칠하기
        a,b,c=tmp[1:]
        fix_color(a,b,c)
    elif r==2: # 노드변경
        a,b=tmp[1:]
        son[parent[a]].discard(a)
        parent[a]=b
        son[b].add(a)
        fix_depth(b,depth[b])
    else: # 사이의 다른 색상 구하기
        a,b=tmp[1:]
        print(count_color(a,b))

정답코드

import sys
input=sys.stdin.readline

N,K=map(int,input().split())

parent=[0]*N
color=[0]*N

def find_lca(a,b):
    tmp=set()
    for i in range(1000):
        tmp.add(a)
        a=parent[a]
    for i in range(1000):
        if b in tmp:
            return b
        b=parent[b]

def count_color(a,b):
    colors=set()
    top=find_lca(a,b)
    while top!=a:
        colors.add(color[a])
        a=parent[a]
    while top!=b:
        colors.add(color[b])
        b=parent[b]
    return len(colors)

def fix_color(a,b,val):
    top=find_lca(a,b)
    while top!=a:
        color[a]=val
        a=parent[a]
    while top!=b:
        color[b]=val
        b=parent[b]

for _ in range(K):
    tmp=list(map(int,input().split()))
    r=tmp[0]
    if r==1: #칠하기
        a,b,c=tmp[1:]
        fix_color(a,b,c)
    elif r==2: # 노드변경
        a,b=tmp[1:]
        parent[a]=b
    else: # 사이의 다른 색상 구하기
        a,b=tmp[1:]
        print(count_color(a,b))

쿠키와 세션은 HTTP 통신의 특징인 Connectionless, 그리고 Stateless 문제를 해결하기 위한 장치임.

쿠키

• 저장위치 : 클라이언트
• 수명 : 보통 유효기간을 정해둠. 브라우저가 닫혀도 유효기간내에 유지됨
• 용량제한 : 각 도메인 당 4KB, 최대 20개
• 보안 : 클라이언트에 저장되므로 취약

세션

• 저장위치 : 서버
• 수명 : 브라우저가 닫히거나, 서버에서 설정한 시간까지
• 용량제한 : 없음
• 보안 : 서버에 저장되므로 보안이 좋다.

2. 세션 방식의 로그인 과정에 대해 설명해 주세요

1. 로그인 요청
2. 인증 ( id, password를 DB에서 검증)
3. 인증 성공시, 서버는 새로운세션 생성(DB에 정보기록)
4. 서버에서 클라이언트로 세션ID를 쿠키에 담아서 전달
5. 클라이언트는 이후 요청마다 세션 ID를 포함해서 요청

3. HTTP의 특성인 Stateless에 대해 설명해 주세요

• 각 요청이 독립적이며, 서버가 이전 요청의 상태를 기억하지 않음
• 작동원리
  • 클라이언트 요청 : 클라이언트가 서버에 요청(이 요청엔 필요한 정보가 다 있음. URL, 메소드, 헤더, 데이터 등)
  • 서버 응답 : 서버는 요청을 받아 응답함( 이 응답에 클라이언트가 요청한 데이터나 결과가 있음)
• 장점 : 각 요청을 독립적으로 처리하므로, 설계 및 구현이 쉬워짐. 확장성이 좋음
• 단점 : 매 요청마다 반복적으로 데이터를 요청받고 보내야함

4. Stateless의 의미를 살펴보면, 세션은 적절하지 않은 인증 방법 아닌가요?

• 불가피하게 유지해야 하는 경우가 많고 Stateless를 유지하는데 더 많은 부하와 cost가 커 사용하는 경우가 많음
• JWT 쓰면은 매 요청마다 JWT 토큰 보냄.
• 이 토큰안에 내가 누구고 이런거 담겨있고, + 요청(method, url) 나는 누구 고 나는 이런 요청 보냅니다. → 매번 보냄
• Stateful → 나는 누구입니다(서버에서 알아서 판단)

5. 규모가 커져 서버가 여러 개가 된다면, 세션을 어떻게 관리할 수 있을까요?

1. 세션 스티키니스(Session Stickiness)

   • 사용자가 세션동안 동일한 서버로 라우팅 되게 하는 방법
   • 각 서버가 독립적으로 세션을 관리할 수 있음
   • 장점 : 구현이 간단하고, 기존 서버 구조를 크게 변경하지 않아도 됨
   • 단점 : 특정 서버에 부하가 집중될 수 있음

2. 세션데이터 저장소를 별도로 관리

   • 세션 데이터를 특정 저장소에 저장해서 공유
   • Redis ,Memcached와 같은 메모리 캐시를 이용하기도 함
   • 장점 : 일관성 유지 가능
   • 세션은 요청때마다 I/O 가 발생하는데, RDB에서는 성능이슈가 발생할 수있으므로 적합할 수 있음
   • 단점 : 저장소의 성능과 가용성이 중요함. 과도한 트래픽시, 병목현상 발생가능

3. 세션 데이터를 DB에 저장하는 방식

   

• 세션을 별도로 Redis저장소를 따로 두어 사용
• 세션 정보를 각 서버마다 동일하게 가져감(전파)
• 장점 : 고가용성, 확장성, 성능
• 단점 : 설정이 복잡하고 비용이 많이 들 수 있음(여러 노드를 운영)

SpringWebFlux + Spring Security6.1 에서 jwt 사용중 blockhound에의해 blocking이 발생했다. 원인 코드는 아래와 같다

    public boolean validateAccessToken(String token) {
        try {
            Claims claims = Jwts.parserBuilder().setSigningKey(key).build().parseClaimsJws(token).getBody();
            return claims.getExpiration().after(new Date());
        } catch (Exception e) {
            return false;
        }
    }

Jwts.parserBuilder().setSigningKey(key).build().parseClaimsJws(token).getBody(); 이 부분에서 blocking이 발생했는데, 도통 해결방안을 찾지못하다가 드디어 찾았다.

https://stackoverflow.com/questions/76199457/jwts-parserbuilder-is-blocking

@Service
public class JwtService {


    final private JwtParser parser;

    public JwtService(){
        this.parser = Jwts.parserBuilder().setSigningKey(this.key).build();
    }
...

    public boolean validateAccessToken(String token) {
        try {
            Claims claims = parser.parseClaimsJws(token).getBody();
            return claims.getExpiration().after(new Date());
        } catch (Exception e) {
            return false;
        }
    }

}

JwtParser 인스턴스를 미리 생성 후, 재사용하는 방식을 이용한다.

풀이

스택을 이용하여 풀었다. 기본적인 원리는 idx:0부터 순회하며 stack에 집어넣는다 만약, stack의 top의 height보다 클경우 push height보다 작거나 같을경우 아래의 과정을 거쳐 pop되고 push 진행

입력으로 "7 2 1 4 5 1 3 3"이 들어온다고 가정할 때, 들어오는대로 (idx,height)형태로 스택에 집어넣는다.

• idx :0일때, height=2는 스택이 비어있으므로 push

• idx :1일때, height=1이므로, 스택의 top의 height가 더 크므로, pop
• (2,0)을 pop할경우, 스택이 비어있게 되는데 이는 곧, idx=1번째까지 최소높이라는 뜻
• 최고높이를 갱신해준다. (heightidx = 21=2)

• idx :2, 3일때, 각각 4와 5의 높이로 이전보다 높으므로 둘다 push
• idx :4일때, height=1이므로, 스택의 top보다 낮다.
• (3,5)를 pop할경우, 스택이 비어있지않는데 idx:1때 설명한것처럼 pop한상태의 스택의 top 즉, (2,4)와 idx:4 사이만큼의 직사각형의 넓이를 구해주어야 한다. 식으로 정리하면

  - 스택에서 top을 pop했을때 스택이 비어있지 않은경우 넓이는height*(idx-stk[-1][1]-1) == 5*(4-2-1)=5

• (2,4)또한 idx :1의 height 4보다 크므로 pop해준다. 위의 idx :1의 경우와 같으므로 생략

• idx :5, 6 일때도 push만 작동
• 이후, 모두 스택에 push했을 경우 하나씩 차례대로 pop을 진행하며 최대값 갱신

import sys
input=sys.stdin.readline

while True:
    li=list(map(int,input().split()))
    res=0
    if li[0]==0:break
    else:li.pop(0) 
    stk=[]
    idx=0
    for i in li:
        if not stk:
            stk.append((i,idx))
            idx+=1
        else:
            if stk[-1][0]<i:
                stk.append((i,idx))
                idx+=1
            else:
                tmp_li=[]
                while stk[-1][0]>=i:
                    now_val,now_idx=stk.pop()
                    if not stk:
                        res=max(res,now_val*(idx))
                        break
                    else:
                        res=max(res,now_val*(idx-stk[-1][1]-1))
                stk.append((i,idx))
                idx+=1
    while stk:
        now_val,now_idx=stk.pop()
        if not stk:
            res=max(res,now_val*(idx))
        else:
            res=max(res,now_val*(idx-stk[-1][1]-1))
    print(res)

풀이

최소 스패닝 트리를 이용해 푸는 문제이다. 크루스칼 알고리즘을 이용했다.

• 노드가 어떤 노드와 연결되어 있는지 정보를 담을 nodes 배열과, 어떤 노드가 연결되어 있고 가중치가 몇인지 담을 배열 li를 준비한다.
• 두가지 함수를 준비한다.
  • find함수는 노드a가 연결되어 있는 루트노드를 찾아 리턴한다.
    • union함수는 a와 b의 루트노드가 다를 경우, 연결하여 준다.
• li배열을 가중치 오름차순으로 정렬해 준다.
• li배열을 순회하면서 a와 b의 루트노드가 다를경우, 결과값가중치에 v를 더해주고, a와 b를 union 해준다.
• 마지막으로, 결과값가중치를 출력

import sys
input=sys.stdin.readline

V,E=map(int,input().split())
li=[]
cnt=0
weight=0
nodes=[i for i in range(V+1)] # 노드의 수만큼 배열 생성

for i in range(E): #간선정보 입력
    A,B,C=map(int,input().split()) # A와 B가 가중치 C로 연결
    li.append([A,B,C])

def find(a): # a노드의 루트노드를 찾는 과정
    if nodes[a]==a:
        return a
    else:
        nodes[a]=find(nodes[a])
        return nodes[a]

def union(a,b): # a와 b노드를 합치는 과정
    a=find(a)
    b=find(b)
    if a!=b: # a와 b의 루트노드가 다른 노드일 경우
        if a<b: # a의 루트노드가 b보다 작을경우
            nodes[b]=a # a의 아래에 b를 단다
        else:
            nodes[a]=b
li.sort(key=lambda x:x[2]) # 가중치 오름차순으로 정렬
i=0
while cnt<V-1:
    a,b,v=li[i][0],li[i][1],li[i][2]
    if find(a)!=find(b):
        cnt+=1
        weight+=v
        union(a,b)
    i+=1
print(weight)

풀이

공기와 접촉된 치즈는 매 턴마다 녹아 공기가 되는 문제이다. 이때, 중요한 점은 치즈로 둘러쌓인 공기 주변의 치즈는 녹지 않는다. 즉, 치즈를 녹일 수 있는 공기와 녹일 수 없는 공기를 별도로 분리하는게 핵심!

• 처음, 치즈를 녹일 수 있는 공기를 분리한다(배열에서 0->2로 변경)
• 그리고 본격적인 턴에 들어간다.
  • bfs를 이용해 치즈를 녹일 수 있는 공기 주변 1칸에 있는 치즈들을 별도로 배열에 넣는다.
  • 만약, 치즈를 녹일 수 있는 공기 주변에 치즈를 녹일 수 없는 공기가 있다면, 해당 공기를 0->2로 바꿔준다
    • 이후, 녹을 예정인 치즈들을 공기(2)로 치환해준다.
    • 이번턴에 몇개의 치즈가 녹았는지 계산해준다.
• 마지막으로, 몇번의 턴이 걸렸는지, 마지막 턴에 몇개의 치즈가 녹았는지 출력

  from collections import deque
  dx=[0,0,1,-1]
  dy=[1,-1,0,0]
  

mx,my=map(int,input().split()) count=[0,0,0] cheeses=[] li=[[0]*(my+1)] for i in range(mx): tmp=[0]+list(map(int,input().split())) for j in range(1,my+1): if tmp[j]==1: cheeses.append([i,j]) li.append(tmp) count[1]+=sum(tmp)

q=deque() q.append((1,1)) while q: x,y=q.popleft() for i in range(4): nx=x+dx[i] ny=y+dy[i] if 1<=nx<=mx and 1<=ny<=my: if li[nx][ny]==0: q.append((nx,ny)) li[nx][ny]=2 tmp_c=0 while tmp_c<count[1]: q=deque() tmp_cc=0 q.append((1,1)) visit=[[0]*(my+1) for i in range(mx+1)] visit[1][1]=1 tmp_airs=[] while q: x,y=q.popleft() for i in range(4): nx=x+dx[i] ny=y+dy[i] if 1<=nx<=mx and 1<=ny<=my: if li[nx][ny]==0: q.append((nx,ny)) li[nx][ny]=2 visit[nx][ny]=1 elif li[nx][ny]==1 and visit[nx][ny]==0: tmp_cc+=1 visit[nx][ny]=1 tmp_airs.append([nx,ny]) elif li[nx][ny]==2 and visit[nx][ny]==0: q.append((nx,ny)) visit[nx][ny]=1 tmp_c+=tmp_cc count[2]=tmp_cc count[0]+=1 for x,y in tmp_airs: li[x][y]=2 print(count[0]) print(count[2]) ```

풀이

오등큰수:

• 수열 li가 주어질 때, li[i]의 오등큰수는 j(i<j)이면서 li[i]보다 등장횟수가 많으면서 가장 작은 j를 뜻한다.
• 즉, 수열li에서 li[i]보다 오른쪽에 있으면서 li[i]보다 등장횟수가 큰 수열값을 찾는것이 관건이다. ex) li=[1,1,2,3,4,2,1] 일때, 등장횟수는 F(1)=3, F(2)=2, F(3)=1, F(4)=1 오등큰수는 NGF(0)=li[0]인 1보다 많이 등장한 값은 없으므로 -1 NGF(1)= 동일 NGF(2)= li[2]인 2보다 많이 등장한 값은 1밖에 없으므로 1 NGF(3)= li[3]인 3보다 많이 등장한 값은 1, 2인데 2가 오른편에 있으면서 가장 가까우므로 2 NGF(4)= li[4]인 4는 위의 NGF(3)과 동일, 2 NGF(5)= li[5]인 2보다 많이 등장한 값은 오른쪽에서 1밖에 없으므로 1 NGF(6)= li[6]인 1보다 오른쪽에 있는 값은 없으므로 -1

스택을 이용해 구현한다. 먼저, 수열 li에서 등장횟수를 구해준다 ex) li[2]=3 이므로 li2[3]= li[2]의 등장횟수 3

이후, li 수열을 순회한다 이때, 결과배열 res는 -1로 초기화 해준다.

• stack이 비어있지 않고 stack의 마지막 값보다 현재 수열의 등장횟수가 더 많은경우,
  • 결과값에 stack의 마지막 값(인덱스)를 넣고 stack에서 pop!
• 현재 수열의 인덱스(i)를 stack에 append

import sys
input=sys.stdin.readline
N=int(input())
li=list(map(int,input().split()))
li2=[0]*(max(li)+1)
res=[-1]*(len(li))
stk=[]
for i in li:
    li2[i]+=1
for i in range(N):
    while stk:
        if li2[li[stk[-1]]]<li2[li[i]]:
            res[stk.pop()]=li[i]
        else:
            break
    stk.append(i)
print(*res)

풀이

해석이 좀 복잡해 보일 수 있는 문제이다.

3
2 3 1

위의 예제 1번을 참고하여 풀어보면 A수열 A[0]=2, A[1]=3, A[2]=1 이 주어질 때, B[P[i]]=A[i]를 만족하는 P수열을 찾아야 한다. 먼저 B수열을 구하여 보면 B[P[0]] = A[0] -> B[1] = 2 B[P[1]] = A[1] -> B[2] = 3 B[P[2]] = A[2] -> B[0] = 1 즉, 1 2 0 이라는 답이 나오게 된다. 위 풀이를 해석하여 보면, A수열의 i번째가 몇번째로 작은 숫자인지 구하는 문제이다. 즉, 예제 1번의 배열에서 2는 2번째로 작고, 3은 3번째로 작고 1은 1번째로 작으므로 1 2 0 이다.

N=int(input())
li=list(map(int,input().split()))
sort_li=sorted(li)
res=[]
for i in li:
    idx=sort_li.index(i)
    res.append(idx)
    sort_li[idx]=-1
print(*res)    

먼저 A수열(li)을 입력받고, 오름차순으로 정렬된 sort_li 수열을 따로 만들어 준다. 그리고, li 수열을 순회하면서 해당 숫자가 sort_li배열에서 몇번째 idx인지 구해 결과배열에 추가하여 주면 끝. 이때, 중복된 숫자가 존재할 수 있으므로 이미 idx를 구한 숫자는 sort_li에서 -1로 바꾸어 준다.

풀이

참고로 이문제는 1174번(줄어드는 수)와 99% 유사하다. 백트래킹 혹은 조합을 통해 0부터 1000000까지의 줄어드는 수 조합을 찾는다.

이때,최대 감소하는 수(9876543210)는 N이 1022번째일때의 경우이므로, 그 이상으로 N이 들어올 경우 -1출력 처리.

N=int(input())
li=[]

def func(x,idx):
    global li
    if x!='':
        li.append(int(x))

    for i in range(idx+1,10):
        func(str(i)+str(x),i)

if N>1022:
    print(-1)
else:
    func('',-1)
    li.sort()
    print(li[N])
print(li)

from itertools import combinations
N=int(input())
li=[]
if N>1022:
    print(-1)
else:
    for i in range(1,11):
        for comb in combinations(range(0,10),i):
            comb=sorted(list(comb),reverse=True)
            li.append(int(''.join(map(str,comb))))
    li.sort()
    print(li[N])

풀이

끊긴 기타줄 N개를 6개세트와 단품가격중 최소비용으로 채우는 문제이다. 주어지는 6개 세트가격과 단품가격을 각각 리스트에 담는다 이때, 6개 세트가격이 단품6개가격보다 크다면, 세트가격을 단품6개가격으로 변경 후 리스트에 담아준다. 그 후, 두 리스트를 정렬해주고 6개 세트중 가장 낮은가격으로 N을 최대한 채워 준 뒤, 남은 나머지x를 단품중 가장 낮은가격*x와 세트중 가장 낮은가격중 더 낮은값으로 처리해준다.

N,M=map(int,input().split())
pac=[]
one=[]
for i in range(M):
    p,s=map(int,input().split())
    p=p if s*6>p else s*6
    pac.append(p)
    one.append(s)
pac.sort()
one.sort()
res=0
res+=(N//6)*pac[0]
N-=(6)*(N//6)
res+=N*one[0] if N*one[0]<pac[0] else pac[0]
print(res)

풀이

일반적인 bfs가 아닌 0-1를 이용하는 문제이다. 0-1 bfs는 아래과정과 같이 진행된다

• deque의 front(left)에서 현재노드를 꺼냄
• 연결된 인접 노드 탐색
• 해당 인접노드를 탐색할 수 있을 경우(이동가능한 경우)
  • 해당 노드를 향하는 가중치가 0이면 덱의 front(left)에 삽입
  • 해당 노드를 향하는 가중치가 1이면 덱의 back에 삽입

가중치가 가장 낮은 정점으로의 이동을 우선순위로 해야하므로 덱의 front에 삽입하게 된다. 일반 bfs와 동일하게 간선의 갯수(E)만큼 탐색, 정점의 갯수(V)만큼 중복없이 방문하므로 시간복잡도는 O(V+E)로 동일하다.

from collections import deque
n,k=map(int,input().split())
dis=[0]*100001

q=deque()
q.append(n)
while q:
    x=q.popleft()
    if x==k:
        print(dis[x])
        break
    for i in (x-1,x+1,x*2):
        if 0<=i<=100000 and not dis[i]:
            if i!=0 and i==x*2:
                dis[i]=dis[x]
                q.appendleft(i)
            else:
                dis[i]=dis[x]+1
                q.append(i)

풀이

stack을 이용해 해결하는 문제이다..!

S=input()
bomb=input()
while True:
    tmp_S=S.replace(bomb,'')
    if S==tmp_S:
        S=tmp_S
        break
    S=tmp_S
print('FRULA' if len(S)==0 else S)

처음엔 단순하게 폭탄문자열을 replace함수를 이용해 지워주는 방향으로 진행했는데 당연하게도 시간초과가 뜬다 ex) aaaaaaaaaaaaa..... bbbbbbbbb ab 입력일 경우, 시간복잡도가 굉장해진다.. 그러므로 시간복잡도를 줄이기 위해 stack을 이용한다.

• 문자열 S의 idx=0부터 stack에 쌓는다
• 만약, stack의 마지막 문자가 폭탄문자열의 마지막 문자와 같을경우
  • stack을 폭탄문자열 길이만큼 끝부분을 슬라이싱 한 결과가 폭탄문자열과 같을경우 그 길이만큼 stack에서 pop!

import sys
input=sys.stdin.readline
S=list(input().rstrip())
bomb=list(input().rstrip())
len_bomb=len(bomb)
stack=[]
idx=0
while idx!=len(S):
    stack.append(S[idx])
    if stack[-1]==bomb[-1]:
        if stack[-len_bomb:]==bomb:
            for i in range(len_bomb):
                stack.pop()
    idx+=1

print(*stack if stack else "FRULA",sep="")

풀이

정수론을 이용해 해결하는 문제이다. 에라토스테네스의 체로 소수들을 미리 뽑아놓고 찾는방식으로 진행하려했지만 범위가 너무커서 시간초과가 떴다 ㅠㅠ 정수론에서 "임의의 양수 M이 합성수이면 √m 보다 작거나 같은 약수를 가진다." 라는 정리를 이용해 "임의의 양수 M이 √m 보다 작거나 같은 양수를 가지지 않으면 소수이다." 라는 결과를 이용한다

1. n이 0 또는 1일경우, 2 출력후 끝.
2. n이 √m 보다 작거나 같은 약수를 가지지 않으면 n 출력후 끝.
3. n이 √m 보다 작거나 같은 약수를 가지면 n+=1 후 2번으로 되돌아가기.

import sys
input=sys.stdin.readline
N=int(input())

def check(x):
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True

for i in range(N):
    n=int(input())
    while True:
        if n==0 or n==1:
            print(2)
            break
        if check(n):
            print(n)
            break
        else:
            n+=1

풀이

배낭문제(knapsack problem)를 응용한 문제이다.(12865번 문제 참고) 점화식을 아래처럼 설계한다. dp[i][j]=i번째 추를 넣을경우, 안넣을경우, 반대편에 넣을경우 만들 수 있는 구슬의무게 즉, i-1번째 무게가 weight이고 i번째 추의 무게가 j인 경우

• dp[i][weight+j]
• dp[i][weight-j]
• dp[i][weight]

위의 3가지는 구슬의 무게로 가능한 가짓 수 이다. 이때,

• weight-j는 0보다 커야하며(무게가 음수일 수는 없다)
• 중복되는경우는 없애는 것이 좋다(재귀함수 반복 줄이기) dp배열이 완성된 경우 해당 구슬의 무게에 해당하는 dp배열을 순회하면서 True가 있는지 조회.

  N=int(input())
  li=[0]+list(map(int,input().split()))+[0]
  ball_N=int(input())
  ball=list(map(int,input().split()))
  dp=[[0]*(15001) for i in range(N+1)]
  

def back(now,weight): if now>N or dp[now][weight]: return dp[now][weight]=1 back(now+1,weight+li[now+1]) back(now+1,abs(weight-li[now+1])) back(now+1,weight)

back(0,0) for i in ball: ch=0 if i>15000: print("N",end=" ") else: for j in range(1,N+1): if dp[j][i]==1: print("Y",end=" ") ch=1 break if ch==0: print("N",end=" ")

아래의 방법은 2차원 dp배열 대신 set을 이용한 방법이다.
위와 같은 방법으로 이루어지지만, set을 이용해 훨씬 간결하게 작성된 방법.
- 추 배열을 순회하면서 우선 임시 set배열에 추의 무게(weight)를 넣어준다.
- 전체 set배열을 순회하면서, weight에 해당 set의 값(i, 이전까지의 추로 만들 수 있던 무게)를 더하거나, 뺐을때 경우를 임시 set배열에 넣어준다
- 전체 set배열에 임시 set배열을 병합해주고 반복
```python
N=int(input())
li=list(map(int,input().split()))
ball_N=int(input())
ball=list(map(int,input().split()))
dp_set=set()

for weight in li:
    tmp_set=set()
    tmp_set.add(weight)
    for i in dp_set:
        tmp_set.add(weight+i)
        tmp_set.add(abs(weight-i))
    dp_set=dp_set.union(tmp_set)
for i in ball:
    print("Y" if i in dp_set else"N",end=" ")

풀이

dp를 이용해 해결하는 문제이다. 최소비용은 책이 n권있다고 가정할 때, 매번 합칠때마다 비용이 중첩되어 발생한다 즉, 1~n권까지의 각각의 책의 비용+매번 합칠때 드는 비용 = 최소비용이다. dp[i][j]=i에서 j까지의 최소비용으로 점화식을 계산한다. 최소비용의 계산방법은 아래와 같다 **편한 계산을 위해 idx는 1부터 시작하게 임의로 설정했습니다. 주어진 크기가 li=[0,40,30,30,50,20]인 예시로 확인해본다. 책을 합치는 구간이 1일때, 먼저, dp[i][i]=는 존재하지않는다.(합치지 않아 비용이 발생하지 않으므로) 책을 합치는 구간이 2일때,

• dp[1][2]=li[1]+li[2]
• dp[2][3]=li[2]+li[3]
• ... dp[i][i+1]=li[i]+li[1] 이다.

책을 합치는 구간이 3일때,

• dp[1][3]=1+(2+3)의 방법과 (1+2)+3의 방법중 최소값이므로 =min(dp[1][1]+dp[2][3],dp[1][2]+dp[3][3])+li[1]+li[2]+li[3] =min(0+70,60+0)+40+30+30 = 160
• dp[2][4]=위와 동일하게 계산. =min(dp[2][2]+dp[3][4],dp[2][3]+dp[4][4])+li[2]+li[3]+li[4] =170
• dp[i][i+2]=min(dp[i][i]+dp[i+1][i+2],dp[i][i+1])+sum(li[2]~li[4])

책을 합치는 구간이 4일때,

• dp[1][4]=min(dp[1][1]+dp[2][4],dp[1][2]+dp[3][4],dp[1][3]+dp[4][4])+sum(li[1]~li[4]) =300
• dp[2][5]=min(dp[2][2]+dp[3][5],dp[2][3]+dp[4][5],dp[2][4]+dp[5][5])+sum(li[2]~li[5])
• dp[i][i+3]=min(dp[i][j]+dp[j+1][i+3])+sum(li[i]~li[i+3]), j는 i부터 i+3까지

즉, 점화식을 작성해보면 dp[i][i+k]=min(dp[i][j]+dp[j+1][i+k])+sum(li[i]li[i+k]), j는 i부터 i+k까지 이때, 뒤의 sum(li[i]li[i+k])는 매번 연산해줄필요 없이 li[i]번까지의 합인 배열 sums[i]를 미리 만들어서 계산해주면 시간단축에 용이하다. 즉, sum(li[i]~li[i+k]) -> sums[i+k]-sums[i-1] (sums[i]는 1부터 i까지의 합)

import sys
input=sys.stdin.readline
T=int(input())
for _ in range(T):
    K=int(input())
    li=[0]+list(map(int,input().split()))
    dp=[[0]*(K+1) for _ in range(K+1)]
    sums=[0]*(K+1)
    for i in range(1,K):
        dp[i][i+1]=li[i]+li[i+1]
        sums[i]=sums[i-1]+li[i]
    sums[K]=sums[K-1]+li[K]
    for k in range(2,K+1):
        for i in range(1,K+1):
            if i+k>K:
                break
            min_v=10**9
            for j in range(i,i+k):
                min_v=min(min_v,dp[i][j]+dp[j+1][i+k])
            dp[i][i+k]=min_v+sums[i+k]-sums[i-1]
    print(dp[1][K])

풀이

bfs(너비우선탐색)을 통해 해결하는 문제이다. N에서 k까지 주어진 3가지의 이동방법(N-1,N+1,N*2)를 통해 최단거리로 이동하면서, 그 이동횟수와 이동방법을 출력해야한다. 처음엔 dp를 이용해 풀려했지만, 시간초과가 날 것 같아서 pass!

먼저 이미 왔던 길인지 확인하기 위한 li배열과, 해당위치로 오기전 이전위치를 알기위한 move배열을 만든다. 그리고 bfs를 통해 N부터 시작한다.

• 만약 현재위치(x)가 K일 경우, li[x]를 출력하고 리턴
• x-1, x+1, x*2의 방법중 0<=i<=100000이고 해당위치를 방문하지 않았다면(li[i]==0) deque에 추가한 뒤, move[i]=x(i번째 위치를 오기전에는 x위치)

N이 K까지 도달할 수 없는 방법은 없으므로 예외는 생략한다.(N+1만 반복해도 도달하므로)

• res배열에 K를 추가한 뒤, x=K로 선언
• x가 N과 다를 때 까지 x=move[x]를 통해 왔던길을 되돌아 가면서 res배열에 추가해준다
• 마지막으로 res배열을 반대로 출력해주면 끝!

from collections import deque
N,K=map(int,input().split())
li=[0]*(100001)
move=[0]*(100001)
res=[]
q=deque()
q.append(N)
while q:
    x=q.popleft()
    if x==K:
        print(li[x])
        break
    for i in (x-1,x+1,2*x):
        if 0<=i<=100000 and li[i]==0:
            li[i]=li[x]+1
            q.append(i)
            move[i]=x

res=[K]
x=K
while x!=N:
    res.append(move[x])
    x=move[x]
print(*res[::-1])

풀이

문제설명이 좀 복잡한 문제다.

1. 주변 4칸중 청소되지 않은 빈칸이 있는 경우,

• a. 현재 바라보고 있는 방향에서 왼쪽으로 회전한다
• b. 바라보는 앞칸이 청소되지 않고 벽이 아닌경우, 전진한다.
• c. 바라보는 앞칸이 청소되어있는 칸이거나 벽인경우, a로 돌아간다.

2.주변 4칸중 청소되지 않은 빈칸이 없는경우

• 현재 바라보는 방향에서 뒤로 1칸 이동이 가능한 경우, 후진한다.
• 아닐경우(뒤에 벽이있을경우), 청소기 작동중지!

먼저, 지도를 li배열에 담아주고, 똑같은크기의 배열 visit를 만들어준다(청소확인용) 그리고 왼쪽으로 돌아가면서 청소가 가능한 빈칸이 있는지 찾는다. 이때, 방향회전에 주의한다! 시게 반시계방향(북,서,남,동)으로 돌아야하므로 dx,dy의 idx=0,1,2,3 -> 북동남서 에서 idx-=1씩 진행되게 (d+3*i)%4의 계산으로 세팅했다.

N,M=map(int,input().split())
dx,dy=[-1,0,1,0],[0,1,0,-1]  # 0,1,2,3 북동남서
li=[]
visit=[[0]*(M) for i in range(N)]
r,c,d=map(int,input().split())
visit[r][c]=1
res=1
for i in range(N):
    li.append(list(map(int,input().split())))
while True:
    ch=0
    for i in range(1,5):
        nd=(d+3*i)%4 #방향은 계속 바꾸어 주어야한다.
        nx=r+dx[nd]
        ny=c+dy[nd]
        if visit[nx][ny]==0 and li[nx][ny]==0:
            visit[nx][ny]=1
            r,c,d,ch=nx,ny,nd,1
            res+=1
            break
    if ch==0:
        nx=r+dx[d-2]
        ny=c+dy[d-2]
        if li[nx][ny]==0:
            r,c=nx,ny
        else:
            break
print(res)