https://www.cdnetworks.com/ko/cloud-security-blog/web-application-firewall-waf/

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

BFS로 최단거리 찾기 문제인데, 3차원인 경우이다.

따라서 배열을 3중으로 사용하였다.

그것만 헷갈리지 않으면 전혀 어렵지 않은 문제.

정답 풀이:

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

dh = [-1, 1, 0, 0, 0, 0]
dr = [0, 0, -1, 1, 0, 0]
dc = [0, 0, 0, 0, -1, 1]

while True:
    h, r, c = map(int, input().split(" "))
    if h == 0 and r == 0 and c == 0:
        break

    sh, sr, sc = -1, -1, -1
    eh, er, ec = -1, -1, -1

    graph = []
    for H in range(h):
        tgraph = []
        for R in range(r):
            tlist = list(map(str, input().rstrip()))

            for C in range(c):
                if tlist[C] == 'S':
                    sh, sr, sc = H, R, C
                elif tlist[C] == 'E':
                    eh, er, ec = H, R, C

            tgraph.append(tlist)
        graph.append(tgraph)
        input()

    queue = deque()
    visited = [[[False for _ in range(c)] for _ in range(r)] for _ in range(h)]
    queue.append((sh, sr, sc, 0))
    visited[sh][sr][sc] = True

    escapeTime = -1
    while queue:
        H, R, C, time = queue.popleft()

        if H == eh and R == er and C == ec:
            escapeTime = time
            break

        for i in range(6):
            nh = H + dh[i]
            nr = R + dr[i]
            nc = C + dc[i]

            if 0 <= nh < h and 0 <= nr < r and 0 <= nc < c and graph[nh][nr][nc] != '#' and visited[nh][nr][nc] == False:
                queue.append((nh, nr, nc, time+1))
                visited[nh][nr][nc] = True

    if escapeTime == -1:
        print("Trapped!")
    else:
        print("Escaped in {} minute(s).".format(escapeTime))

결과

오타 하나 나서 틀렸었다 ^^..

SVN, Git 차이

일단 공통점은?

• 둘 다 형상관리 툴이다.

형상관리란?

• 영어로 Version Control Revision Control
• 소프트웨어의 버전관리를 뜻함.
• 소스코드의 변화를 관리하는 것.

그게 왜 필요한지?

• 소스를 버전 별로 관리할 수 있음
• 그래서 소스가 삭제되거나, 수정되었을 때 그리고 과거 버전으로 복구하고 싶을 때 유용함.
• 여럿이서 개발을 하는 경우, 누가 어느 부분을 수정했는지 관리가 됨.
• 그래서 코드 병합, 코드 리뷰를 할 때 용이함.

형상관리 툴의 종류

• Client/Server 타입
  • Subversion(SVN), CVS, Perforce, ClearCase, TFS
• 분산저장소 타입
  • Git,. Mercurial, Bitkeeper, SVK, Darcs
• Folder 공유 타입
  • RCS, SCCS

차이점

1. SVN은 중앙서버를 이용해 소스코드를 보관, Git은 여러 분산 서버와 PC 로컬저장소를 통해 소스코드를 보관
   • SVN에선 Commit을 하면 바로 서버와 연동됨.
   • Git에선 Commit을 하더라도 push 하기 전까지는 서버에 영향을 미치지 않음
   • 그래서 commit을 할 때 더욱 신중해야 하는 것은 SVN이다.
   • 사본을 로컬에서 관리하는 Git은 SVN보다 소스코드에 더 빨리 접근할 수 있음.

2. SVN은 version history를 가지지 않으나, Git은 가짐.
   • 그래도 SVN에서도 몇 일 전까지의 history는 확인 가능.
   • 그러나 확인만 가능. 그것을 다시 복구하거나 하는 행위 불가능
   • Git은 원하는 순간에 history를 통해 이전 소스코드를 보거나, 이용할 수 있음

3. Git이 SVN보다 더 빠르고, 많은 기능을 가지는 것처럼 보임.
   • 그래서 Git이 SVN보다 좀 더 사용하기 힘듬.
   • 이용하기 위해 공부가 더 필요한 것은 Git 이다.

reference

https://hahahoho5915.tistory.com/40

JPA FetchType

서로의 Entity가 N:1 매핑이 되어있는 상태에서 fetch 설정을 할 수 있음

• @??ToOne 상황에서는 EAGER 이 디폴트 값
• @??ToMany 상황에서는 LAZY 가 디폴트 값

FetchType.LAZY

• 지연로딩
• JPA는 필요한 값만 딱 가져오기 위해 필요한 쿼리만 보냄.

FetchType.EAGER

• 즉시로딩
• JPA는 필요하지 않든 어쨌든 일단 연관된 테이블의 모든 값에 대한 쿼리를 보내서 가져와놓고 생각함.
• n+1 문제를 발생시킬 수 있으므로 EAGER은 가급적이면 쓰지 않는게 좋다.

정리

• 비지니스 로직에서 Over fetching과 같은 현상, 그리고 불필요한 쿼리 요청은 로직의 효율성을 떨어뜨린다.
• EAGER(즉시로딩)을 사용하면 Over fetching 현상을 발생시킬 수 있음.
• 또한 연관된 테이블의 갯수만큼 계속 select 요청을 보내는 n+1 문제를 야기시키기도 함.
• 따라서 FetchType은 LAZY를 쓰는 것을 권장한다.
  • (FetchType LAZY를 사용한다고 해서 반드시 n+1 문제가 해결되는 것은 아님)

Reference:

https://ict-nroo.tistory.com/132

https://developer-hm.tistory.com/37

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

최단거리를 구하는 BFS와 시뮬레이션이 합쳐진 문제다.

불을 먼저 퍼트리고, 지훈이 그 다음 이동하도록 하였다.

그 반대로 하려면 좀 까다로웠기 때문이다.

불과 지훈이 한 번에 한 칸씩만 퍼져야 했기 때문에

queue에서 popleft 할 때 fcnt, jcnt 만큼만 꺼내서 퍼지도록 했다.

정답 소스코드

import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int, input().split(" "))
graph = []
for i in range(R):
    s = input().rstrip()
    graph.append(list(s))

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

fqueue = deque()
jqueue = deque()

fcnt = 0
jcnt = 0
for r in range(R):
    for c in range(C):
        if graph[r][c] == 'F':
            fqueue.append((r, c))
            fcnt += 1
        if graph[r][c] == 'J':
            jqueue.append((r, c))
            jcnt += 1


time = 0
escaped = False
while True:
    time += 1
    # 불번짐 먼저 시작
    ftmp = 0
    for f in range(fcnt):
        r, c = fqueue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < R and 0 <= nc < C:
                if graph[nr][nc] == 'J' or graph[nr][nc] == '.':
                    fqueue.append((nr, nc))
                    ftmp += 1
                    graph[nr][nc] = 'F'
    fcnt = ftmp

    # 지훈이 이동
    jtmp = 0
    died = True
    for j in range(jcnt):
        r, c = jqueue.popleft()
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < R and 0 <= nc < C:
                if graph[nr][nc] == '.':
                    died = False
                    jqueue.append((nr, nc))
                    jtmp += 1
                    graph[nr][nc] = 'J'
            else:
                # 탈출 성공
                escaped = True
    jcnt = jtmp

    if escaped == True:
        print(time)
        break
    if died == True:
        print("IMPOSSIBLE")
        break

# 시뮬레이션과 BFS가 합쳐진 문제
# 반례를 찾느라 정말 많이 틀렸다..

결과

F가 하나도 없을 수 있다는 점을 간과해서 몇 번 틀렸고

jcnt를 사용하지 않고 단 1번만 popleft 해서 이상하게 퍼져서 몇 번 더 틀렸었다.

출력 초과는 디버깅용 print 삭제 안하고 제출했다가 틀린 것..

504ms -> 476ms 줄인 건 visited 배열을 쓰려고 선언만 해놓은거 안써도 풀리길래 삭제했더니 줄었다.

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

그래프 문제인데, N이 50밖에 안되고

진실을 아는 사람은 2로, 모르는 사람은 1로 체크하여

인접행렬 방식을 사용하면 더 편리할 것 같아서

그런 방식으로 코딩을 해봤는데

인접행렬을 약간 오랜만에 다뤄봐서 그런지 버벅였다.

나열된 파티 순서와는 관계 없이,

진실을 아는 사람이 포함된 경우는 거짓말을 할 수 없다는 것을 염두해야함.

정답 코드

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split(" "))  # 사람 수(1부터 시작) , 파티 수

graph = [[0 for i in range(N+1)] for i in range(N+1)]
know = list(map(int, input().split(" ")))[1:]
for k in know:
    for n in know:
        graph[k][n] = 2

queue = deque()
rememberParties = []
for m in range(M):
    partyMember = list(map(int, input().split(" ")))[1:]
    rememberParties.append(partyMember)
    isKnowHere = False
    for p in partyMember:
        if graph[p][p] == 2:
            isKnowHere = True
            break

    if isKnowHere == True:
        # BFS로 2로 싹 변경
        visited = [False for i in range(N+1)]
        for p in partyMember:
            queue.append(p)
            visited[p] = True
            while queue:
                cur = queue.popleft()
                for idx in range(1, N+1):
                    if graph[cur][idx] != 0:
                        graph[cur][idx] = 2
                        if visited[idx] == False:
                            queue.append(idx)
                            visited[idx] = True

        # 2중for로 2로 싹 연결
        for p in partyMember:
            for j in partyMember:
                graph[p][j] = 2

    else:
        # 2중for로 1로 싹 연결
        for p in partyMember:
            for j in partyMember:
                graph[p][j] = 1

answer = 0
for rem in rememberParties:
    canLie = True
    for r in rem:
        if graph[r][r] == 2:
            canLie = False
            break
    if canLie == True:
        answer += 1
print(answer)

# N이 50개라 인접행렬 방식을 사용.
# 진실을 아는 사람을 탐색할 때 BFS 사용
# 순서와 관계없이 진실을 아는 사람과 파티에 있었던 경우도 거짓말을 하지 못하는 것을 고려해야함.
# 아니 그러면 지민이는 몸이 1개인데 많은 파티에 동시에 참석한다는거야 뭐야
# 아무튼 그래서 모든 파티에 대해 진실을 아는 사람이 있었는지 확인하고, 진실을 아는 사람을 알아낸 뒤 다시 한 번 파티에 대입해서 answer 구함

결과

코드가 길다보니 푸는데 좀 시간이 걸렸는데

풀고나서 정답자 코드를 보니까 정말 짧게 잘 풀었더라..

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

구현 카테고리로 검색했는데

이건 그냥 완전탐색 문제 아닌가?

일단은 풀었다.

치킨집이 최대 M개까지 있을 수 있다고 했으니까,

1부터 M까지 치킨집의 위치를 조합(combination)으로 내놓은다음

거기에다 모든 집의 위치와 일일히 치킨거리를 구하고

도시의 치킨거리를 최솟값으로 갱신했다.

itertools의 combination을 오랜만에 사용해볼 수 있는 문제였다.

정답 소스코드

import sys
import itertools
input = sys.stdin.readline
N, M = map(int, input().split(" "))
graph = []
for i in range(N):
    graph.append(list(map(int, input().split(" "))))
home = []
chicken = []
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            home.append([i, j])
        if graph[i][j] == 2:
            chicken.append([i, j])

answer = sys.maxsize
# 1부터 탐색
for m in range(1, M+1):
    # 조합 이용 (중복 X)
    for chi in itertools.combinations(chicken, m):
        tmp = 0
        # 모든 집에 대해서 일단 탐색 후, 최솟값으로 갱신
        for h in home:
            chilen = sys.maxsize
            for i in range(m):
                chilen = min(chilen, abs(h[0]-chi[i][0]) + abs(h[1]-chi[i][1]))
            tmp += chilen
        answer = min(answer, tmp)

print(answer)

# 완전탐색, 조합

결과

ps.

최근에 삼성SW역량테스트를 보고왔는데,

거기는 아예 외부 라이브러리 사용을 금지했었다.

조합이나 순열같은 알고리즘은 매번 itertools 라이브러리의 힘을 빌리고있는데,

자력으로 풀 수 있도록 공부를 해놓는게 좋을 것 같다.

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

시간초과로 못풀었던 문제였는데, 이제는 풀 수 있을까 해서 다시 도전해봤다.

그래프이론, 구현이 동시에 들어간 문제이다.

시간을 단축시키기 위해 모든 맵을 돌면서 섬의 개수를 세는 동시에,

rlist 라는 배열에 바로 줄여야할 값을 추가해나갔다.

(rlist에 기억해놓는 방식이 아닌, 바로 줄여버리면 바다가 아닌데, 바다로 착각해서 오류난다)

섬의 개수를 셀 때는 BFS를 사용했다.

그리고 한바퀴 다돌면 rlist에 기억해놓은 내용으로

graph의 값을 줄였다.

다 풀었다고 생각해서 제출했지만

빙하가 다 녹아서 사라질때까지 섬이 2개 이상으로 나눠지지 않는 예외처리를 잊어먹어서

1회 틀렸다 ㅠ 역시 문제는 꼼꼼히 읽자.

정답 소스코드

import sys
from collections import deque
input = sys.stdin.readline
R, C = map(int, input().split(" "))

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
graph = []
for i in range(R):
    graph.append(list(map(int, input().split(" "))))

answer = 0
queue = deque()
while True:
    visited = [[False for i in range(C)] for i in range(R)]
    islandCnt = 0
    rlist = []
    for r in range(1, R):
        for c in range(1, C):
            if graph[r][c] != 0 and visited[r][c] == False:
                visited[r][c] = True
                queue.append((r, c))
                islandCnt += 1
                while queue:
                    rr, cc = queue.popleft()
                    zeroCnt = 0
                    for i in range(4):
                        nr = rr + dr[i]
                        nc = cc + dc[i]
                        if graph[nr][nc] == 0:
                            zeroCnt += 1
                        if graph[nr][nc] != 0 and visited[nr][nc] == False:
                            queue.append((nr, nc))
                            visited[nr][nc] = True
                    rlist.append((rr, cc, zeroCnt))

    # 만약 빙하 개수가 2개 이상이다?
    if islandCnt >= 2:
        print(answer)
        break

    # 만약 빙하가 다 녹아서 사라졌는데 빙하 개수가 2개를 넘은적이 없다?
    if len(rlist) == 0:
        print(0)
        break

    # 빙하 녹이기
    for rval in rlist:
        r, c, cnt = rval[0], rval[1], rval[2]
        graph[r][c] -= cnt
        if graph[r][c] < 0:
            graph[r][c] = 0

    answer += 1

결과

예전엔 자바로 알고리즘을 풀곤 했었다..