분류 전체보기

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 매우 모범적인 문제라고 생각한다. 기계적으로 BFS를 막 때려맞히는 것이 아니라, BFS의 근본적인 목적 = 그래프 탐색을 이해하고 있는지 스스로 점검을 하기 좋은 문제라고 생각이 된다. 가중치가 모두 동일한 그래프에서 특정 지점에서 특정 지점으로의 최단 경로를 찾을 때 가장 빠른 알고리즘이 BFS이다. 최단경로를 찾는 알고리즘으로는 다익스트라 알고리즘 플로이드 와샬 알고리즘 벨만 포드 알고리즘 이렇게 존재하고 저 셋중 가장 빠른 것은 우선순위 큐를 사용한 다익스트라 알고리즘이다. O(Nlogn) 다익스트라 알고리즘은 가중치가 여러개인 경우 사용할 수 있는 가장 빠른 알고리즘이나 가중치가 모두 같다면, BFS가 가장 빠르다 O(N) BFS는 사실 최단경..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 문제 상황에서 시작점과 도착점이 동일하게 주어진 경우를 놓쳐서 여러번 틀린 문제이다. 문제 자체는 그렇게 어렵지 않은 BFS문제이다. 내가 작성한 코드 from collections import deque F, S, G, U, D = map(int, input().split()) graph = [0 for _ in range(F + 1)] search = deque() dx = [U, -D] moves = -1 search.append((S,1)) graph[S] = 1 while search: C, T = search.popleft() if C == G: moves = T - 1 break for i in range(2): nC = C + dx[i] ..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 BFS를 진행할 때, 독립된 그래프의 순회를 해도 되는 상황이다. 우선 BFS 특성 상 동시에 두개의 이동이 가능한 주체에 대한 BFS는 불가능하다. 그러나 이 문제는 이동이 가능한 대상이 둘이다. 따라서 각각 진행을 하되 앞서서 BFS를 진행한 주체의 타임 스탬프와 비교하는 과정이 필요하다. 내가 작성한 코드 from collections import deque # 입력 받기 TC = int(input()) for _ in range(TC): bY, bX = map(int, input().split()) board = [[0 for _ in range(bY)] for _ in range(bX)] visF = [[0 for _ in range(bY)] ..

분류 완전 탐색 혼자 힘으로 해결 했는가? △ (엄청난 삽질을 해서 애매함) 느낀 점 이번 문제를 직접 모두 백트래킹으로 구현을 하려고 하니 너무 실수가 잦았다. 우선 각 칼럼마다 가능한 조합을 만들고 (백트래킹 + for문) 각 조합마다 다시 겹치는지 검사를 위해 다시한번 완전탐색을 사용하고 (2중 for) 만들어진 조합이 최소성을 충족하는지 따지기 위해 다시 백트래킹을 사용했다. 이렇게 구현을 하니 너무 힘이들었다. 이후 다른 분은 어떻게 해결했는지 참고했고 itertools와 set을 활용하는 인사이트를 얻을 수 있었다. 우선 각 칼럼마다 가능한 조합 자체를 itertools로 만들고 (물론 순수 백트래킹으로 만드는 방법도 알아야 한다고 생각한다.) 이후 하나의 칼럼의 조합이 유일성을 만족하는지 체..

분류 스택, 재귀 혼자 힘으로 해결 했는가? △ (예외를 못 잡아서 오래걸림) 느낀 점 스택을 사용하는 문제이나 구현력이 조금 필요한 문제라고 생각한다. 처음에는 재귀로 접근을 했으나 2(1)3(12(2)) 와 같이 완전한 괄호 쌍이 여러개가 나오는 경우를 놓쳤고, 이런 경우까지 해결하기에는 스택을 사용해야 해결이 가능 할 것 같았다. 이를 위해 스택에 앞 부분부터 집어넣고 )를 만난 경우 스택에서 값을 빼서 계산하는 방식으로 구현을 했으나 한가지 발목은 잡은 부분이 이 문제는 딱 봐도 문자열을 직접 만들면서 진행하면 시간초과 or 메모리 초과가 무조건 생길 문제이다. 즉, 나는 중간 값으로 문자열 자체를 활용하면 안되고 길이만을 저장해야 하는데, 562(12(2))와 같은 경우, 스택에 5 6 2 이런..

분류 BFS 혼자 힘으로 해결 했는가? O 느낀 점 BFS 유형의 문제는 여러가지 유형이 존재한다. 가장 기본 유형은 하나번의 BFS만을 이용하는 경우이며 이런 경우는 대개 그래프가 연결이 되었는지를 체크할 때 주로 사용이 된다. 그러나 해당 유형은 난이도가 낮아서 BFS 익힐 때 푸는 정도이다. 이 문제는 BFS를 여러번 시도를 해야 하는 경우에 대한 인사이트를 제공하는 것 같다. 문제 난이도가 그렇게 높지 않기 때문에 무의식적으로 잘 해결을 할 수 있지만 한번 고민을 해볼 필요는 있다고 생각한다. BFS를 여러번 수행하는 경우에도 아래와 같이 나눌 수 있다고 생각한다. 각각의 BFS를 따로 진행해도 된다. 그리고 서로에게 어떠한 영향도 없다. 각각의 BFS를 따로 진행해도 되지만 서로에게 영향이 있다..

분류 스택 혼자 힘으로 해결 했는가? O 느낀 점 앞서 2493번을 통해 monotone 스택 문제에 대한 감을 잡은 뒤 도전했다. 등급은 골드4로 2493보다 한단계 더 높지만 둘 다 난이도가 똑같이 느껴졌다. 다만 이 문제는 2493과 달리 검사의 대상이 되는 숫자가 담긴 배열의 역순으로 진행을 해야했다. 아마 현재 값의 우측 값에 관심이 있기 때문에 우측부터 시작해서 현재 값을 기준으로 선행 된 값 중 나보다 큰 값이 처음으로 나오는가? 이렇게 문제를 해결하기 때문인 것 같다. 그리고 이 문제에서 중요한 키워드는 현재 값을 기준으로 오른쪽 값 중에서 가장 왼쪽에 있는 큰 값 이라고 생각한다. 위의 말을 다시 풀어서 쓰면 나보다 우측에 있는 값 중에 처음으로 발견되는 큰 값 따라서 스택을 써서 처음으..

분류 스택 혼자 힘으로 해결 했는가? X 느낀 점 스택 문제를 많이 풀지 않았기 때문에 억지로 스택을 활용하려고 하다가 시간 초과를 맞이했고 결국 실패했다. 스택 하나만으로 이 문제를 어떻게 해결해야하는지 감이 오지 않아 구글링을 해 보았고 Monotone 스택 유형임을 알게 되었다. 그와 동시에 이 문제에서 제시하는 사고 흐름은 반드시 익혀야겠다는 생각을 했다. 내가 작성한 코드 오답 import sys from collections import deque N = int(input()) tower = list(map(int, sys.stdin.readline().rstrip().split())) stack = deque() for i in range(N): tower[i] = (tower[i], i +..

Briefing 프로젝트를 진행하면서 스프링 시큐리티와 관련된 요구사항들이 있었습니다. 그러나 Spring Security에 대한 이해도가 낮았기 때문에 필터 체인의 흐름, 내부적인 인증 과정에 대한 이해를 하기 위해 학습을 진행했고 이번 포스팅은 인증 과정에 대한 포스팅입니다. 인증에도 여러가지 인증이 존재합니다. OAuth2에 대한 인증, form Login에 대한 인증 각각 모두 다른 형태의 인증을 거치게 됩니다. 이번 포스팅은 가장 쉬우면서도 인증 과정에 대한 흐름을 익히기 좋은 form Login에서의 인증 과정을 다룹니다. 🌐 Spring Security 인증의 과정 위의 이미지는 Spring Security의 인증 과정에 대한 과정을 나타낸 다이어그램입니다. 그러나 위의 이미지는 아래의 인증..

해당 포스팅은 Briefing Service에서 요구 사항에 대한 문제 해결 과정에서 학습한 내용에 대한 내용입니다! 🌐 Spring Security 에 대한 학습의 계기 지금까지 Spring Security를 도입한 프로젝트가 다수 있었지만, 제가 직접 학습을 해서 적용을 하지 않고 친구의 코드와 블로그에서 제공하는 예시를 통해서 사용했습니다. 따라서 추가적인 Spring Security의 기능을 활용해야 하거나 혹은 문제가 생긴 경우 효율적으로 해결하지 못하고 임시방편으로 문제를 해결하는 정도에 그쳤습니다. 이번에 실제로 런칭을 하고 지속적인 서비스를 하기 위해 많은 신경을 쓰고 있는 Briefing 서비스에서 JWT 인증에 추가적으로 Swagger 접속 시에만 Form Login을 구현해야하는 요구..