본문 바로가기

분류 전체보기

 (403)
DFS를 활용한 순열 이전에 dfs를 활용한 조합을 봤습니다. 순열도 비슷한 방식으로 백트래킹을 사용합니다. 조합과 순열의 가장 큰 차이는 순서입니다. 조합은 1 2 3, 1 3 2 가 같지만 순열은 다르다고 봅니다. 때문에 조합은 idx라는 인수를 갱신하면서 1 2 3 에서 2개를 뽑는다고 치면 1 2, 1 3 하고 끝! 이었습니다. 그러나 순열은 순서를 중요시 생각하기 때문에 2 부터 시작하는 순서도 2 1 가 나와줘야합니다. 이를 이해해야합니다. #include #include #define MAX 4 using namespace std; vector num; vector result; bool visited[5] = { false, }; void dfs(int cnt) { if (cnt == MAX) { for (in..
프로그래머스 - N개의 최소공배수(C++) https://tigerfrom2.tistory.com/70 유클리드 호제법(Euclidean algorithm) - 최대공약수, 최소공배수 알고리즘 최대공약수는 암호학에도 자주쓰이고 알고리즘 문제를 풀 때도 자주 등장합니다. 우리가 초등학교 때 배웠던 최대공약수 구하는 법은 ex) 4 8 이라 하면 두 수가 공통으로 나누어질 것 같은 수를 tigerfrom2.tistory.com 이 글을 참고! 어차피 몇개가 들어오던 (1,2,3,4) 라고 하면 1, 2의 최소공배수 a, a와 3의 최소공배수 b, b와 4 의 최소 공배수 c 라고 순차적으로 구해나가면 그게 정답이다. 수학적 증명은 하지않았지만 뭐 맞았다. #include #include using namespace std; int gcd(int a,..
유클리드 호제법(Euclidean algorithm) - 최대공약수, 최소공배수 알고리즘 최대공약수는 암호학에도 자주쓰이고 알고리즘 문제를 풀 때도 자주 등장합니다. 우리가 초등학교 때 배웠던 최대공약수 구하는 법은 ex) 4 8 이라 하면 두 수가 공통으로 나누어질 것 같은 수를 나눕니다. 2로 나누겠죠. 그럼 2 4 가 되고 이를 또 2로 나누면 1 2 가 되며 이때 마지막으로 더 나누어지는 수가 없으면 지금까지 나눈 수들을 곱한 값이 최대공약수 입니다. 이는 사람머리로는 간단하지만 알고리즘적으로 생각하면 복잡합니다. 이를 타개하기 위해 무려 기원전 유클리드라는 천재가 발명한 것이 유클리드 호제법 입니다. 먼저 유클리드 호제법의 원리는 다음과 같습니다. 1980 , 168 의 최대공약수를 구한다면 1980 % 168 = 132 -> 나누어 떨어지지 않습니다. 즉 최대공약수는 168이 아닌..
프로그래머스 - 삼각 달팽이(c++) 처음보면 되게 난해할 수 있는 문제이다. 방법이 있긴한가 싶었다. 처음 생각한 풀이는 DP였다. 그러나 DP는 최적의 값을 찾는 것인데 단순 배열 채우기가 DP?는 아닐거라 생각했다. 그다음은 dfs였는데 하삼각행렬만 가능하다고 치고 방향을 계속 바꿔주면 될 것 같았다. 이런 식으로 계속 규칙이 있음을 알 수 있다. 어차피 방향은 3가지뿐이라 재귀만 잘 따지면 가능할 것 같았다. dir 이라는 방향을 저장해두는 변수를 하나 만들고 dir = 0 이면 아래방향 dir = 1 이면 오른쪽 dir = 2 이면 왼쪽 대각선 으로 이동하게 만들고 각 방향마다 몇번 이동해야하는지 정해두었다. 그런데 그림으론 저렇지만 코딩을하고나니 첫번째때 0,0 에서 시작하니까 첫 아래방향에 cnt = n - 1 이 되는 것을 알..
Spring Boot - 카카오 로그인 인가 받기 스프링 부트에서는 구글과 페이스북 로그인을 도와주는 하위 프레임워크가 있을 정도. 그러나 우리나라에선 카카오 로그인이 더 대표적입니다. 먼저 우리가 자체적으로 만들어놓으면 유저(클라이언트) 우리의 서비스(서버) 데이터베이스 로그인 요청 이렇게 로그인 요청이 들어오면 데이터 베이스에 맞는 정보가 있는 지 확인하고 세션을 만듭니다. 그러나 카카오 로그인 api 서비스를 사용한다면 관계는 이렇게 바뀝니다. 유저(리소스 오더) 우리의 서비스(클라이언트) 카카오 API 서버 카카오 자원 서버 그렇다면 유저가 로그인시 이렇게 보일 겁니다. 여기서 사용자는 일반 로그인과 카카오 로그인 중 하나를 선택하게 될것이고 일반 로그인을 선택하면 이전에 만든 스프링 시큐리티로 로그인할 것이고 저 깨진 걸 누르면 카카오 로그인이..
프로그래머스 - 마법의 엘리베이터(C++) 처음 문제를 읽고 바로 BFS구나! 싶어서 bfs로 코딩했다. 얼마 전 워딩이 거의 비슷한 문제를 만났어서 더욱 그랬다(아래 첨부) 그러나 시간초과에 틀렸습니다가 무더기로 나왔다. 잘 읽어보니 저 위의 100까지의 숫자 외에도 1000 10000까지도 나갈 수 있는 것이었다. 그래서 주어진 숫자의 자릿수까지만 bfs 할 수 있도록 했는데도 38점 밖에 받지 못했다. 너무도 당연하게 bfs가 맞다고 생각하고 있어서 내 코드가 어디가 잘못된 건지 갈피를 못잡고 있었다. 이 풀이가 잘못된건가? 라고 생각했을 땐 이미 늦었다. 이것과 비슷한 문제를 풀어본적이 있는데도 풀이를 바로 떠올리지 못한 것이 참 아쉽다. 아직까지도 시간복잡도 계산을 잘 못하는 것이 컸다. 시간복잡도를 통해 bfs가 불가함을 바로 알아챘어..
Spring Boot - 로그인 정보 변경, 세션 변경 이전에 보았듯, 스프링 시큐리티는 엄격한 보안 규칙으로 로그인시 몇번의 검증을 합니다. 그렇다면 유저정보를 바꾸면 어떻게 될까요? 개발자가 사용자 정보를 바꾸는 기능을 코딩했다고 가정합시다. ex) 사용자의 사는곳 서울시 동작구 -> 서울시 광진구 변경 후 사용자가 자신의 정보를 클릭하면 사는곳 : 서울시 동작구 이렇게 바뀌지 않았을 겁니다. 바뀐 정보를 보려면 재로그인 해야합니다. 왜일까요? 데이터베이스는 바뀌었지만 세션이 바뀌지 않았기 때문입니다. 지금 스프링 시큐리티는 이전의 정보를 갖고 있는 유저의 정보가 들어간 세션이기 때문이죠. 이때는 강제로 세션을 바꿔야합니다. Authentication authentication = authenticationManager.authenticate( new U..
Spring Boot - 스프링 시큐리티의 로그인 로직 스프링 시큐리티는 이름부터 알 수 있듯 권한, 인증 등 보안의 관련된 스프링의 하위 프레임워크 입니다. 스프링 시큐리티는 비밀번호가 암호화되어 있지 않으면 아에 입구컷 해버리는 매우 깐깐한 녀석인데 그만큼 안전하게 사용자 보안을 지켜준다고 볼 수 있습니다. 스프링 시큐리티는 SecurityContextHorder라는 공간을 만듭니다. 이 공간에는 유저 정보가 들어갈 수 있는데 유저의 정보가 들어간 상태를 "세션" 이라고 합니다. 우리가 로그인시 보이는 화면과 비로그인시 보이는 화면이 다른 경우가 많은데 전부 세션이 유지되고 있냐, 안되어 있냐로 화면을 구분하여 보여주는 것입니다. 먼저 HTTP 통신으로 로그인 요청으로 아이디와 비밀번호가 들어올겁니다. 그럼 스프링 시큐리티가 이 로그인 명령을 가로챕니다...

티스토리툴바