Meluu_의 코딩 공부 일지

✔️ OIDC(OpenID Connect) 란 ? OpenID Connect 1.0은 OAuth 2.0 [RFC6749] 프로토콜 기반의 간단한 신원 계층입니다 . 클라이언트는 권한 부여 서버에서 수행한 인증을 기반으로 최종 사용자의 신원을 확인하고, 상호 운용 가능하고 REST 방식과 유사한 방식으로 최종 사용자의 기본 프로필 정보를 얻을 수 있습니다. - openid.net - OIDC(OpenID Connect)에서 로그인 제공자(예: 소셜 서버)는 공개 키를 JWKS(JSON Web Key Set) 형식으로 제공하며, 클라이언트는 로그인..

🧫 문제 분석✔️ 출처2048 (Easy) 골드 1 📖 문제 보드 크기가 N이며, 매 이동마다 변화하기때문에완전탐색 말고는 답이없는 것 같아서 완전탐색으로 풀이방향을 정했다. 문제에서 알고리즘 분류는 백트래킹 쪽이지만 나는 BFS로 풀었다.BFS + 완전탐색 이 문제에서 어려웠던 건 단순히 어떻게 한 방향으로 보내면서 합치고, 다를땐 이동시키는가 이다. 합쳐지지않은 위치를 추적한다. notUnionIdxnotUnionIdx ~ 현재 위치 전까지를 이동 가능한 곳을 탐색한다. 이때 같은 값을 가지고 있다면 합친다. 값을 2배로 하고 현재 위치의 값은 0으로 저장한다. 그리고 notUinonIdx 를 합친 위치의 다음 위치로 갱신한다. 각 방향은 4개의 함수로 각각 작성하였다. 🔅 문제 풀이impo..

🧫 문제 분석✔️ 출처Four Squares 실버 3 📖 문제DP문제 1~n-1까지의 four squares를 구하고 n의 four squares 를 구한다. 단순히 현재 자신의 최대 제곱근의 제곱을 자신의 수에서 뺀 나머지의 four squares를 이용하면 틀린다. 12의 경우최대 제곱근은 3이며 12 - 9 = 3 이므로 dp[3] 의 값을 더해주면 dp[3] (3) + 3^3(1) = 4개 로 최소가 된다 싶겠지만 2^2 + 2^2 + 2^2, 단 3개만으로 12를 완성할 수 있다. 때문에 해당 수의 1~최대 제곱근까지를 탐색해야한다. 점화식dp[i] = Math.min(dp[i - (j*j)] + 1, dp[i]) [i = 2~N , j = 1 ~ sqrt(i)] 🔅 문제 풀이imp..

🧫 문제 분석✔️ 출처트리의 순회 골드 1 📖 문제이진 트리 (완전 이진 트리 X) 이기에 한쪽으로 기울어긴 트리가 가능하다. 때문에 직접 배열로 이진트리를 만들 생각을 하면 안된다. 순회 특징후위 순회는 마지막이 항상 중앙노드다. 중앙 순회는 중앙노드 기준으로 왼쪽, 오른쪽 서브트리를 갖는다. 중앙노드, 서브트리, 왼쪽 끝 오른쪽 끝 노드를 알 수 있는데 어떻게 해야 전위순회를 할 수 있을까 분할 정복을 이용하면 쉽게 알 수 있다.후위 순회의 마지막 노드는 항상 중앙노드이므로 중앙 노드를 얻고 이 노드의 중앙 순회에서 위치를 얻은다음 중앙 순회에서 중앙 노드를 기준으로 왼쪽을 서브트리, 오른쪽을 서브트리로 나눠서 분할한다. 나눠지면 또 그 서브트리에서의 후위 순회의 마지막 노드는 그 서브트리의 중..

🧫 문제 분석 ✔️ 출처할로윈의 양아치 골드 2 📖 문제2차원 DP로 좀 많이 복잡하게 풀었다.시간 제한 거의 닿을정도로 ㅋㅋ.. 유니온-파인드Set + 넵샥 알고리즘으로 풀었다.그리고 다른사람 풀이를 봤더니 1차원으로 충분히 가능하다는 것이다. 이번 풀이의 문제점Set으로 아이들의 값을 굳이 배열로 만듦경로 압축을 했어도 중간 부모가 있음을 알지 못했음 (항상 최상위 부모를 찾을려면 find 할 것)1차원 냅샥을 생각했지만 정방향으로만 생각해서 중복 연산될거라고 한 점 - 이는 역방향으로 하면 중복연산하지 않는다. 🔅 문제 풀이import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;impor..

일반적으로 배낭문제는정해진 무게 안에 가장 가치 있는 물건을 고르는 것 이다. 이번 포스팅에서는 배낭 문제의 3가지 유형 (0/1, 무한, 개수제한)에 대해 이해해보려한다.사실 배낭문제도 2차원 배열을 활용한 DP 문제다 따라서 제일 먼저 문제를 보고 할 일은 최적 부분 구조 + 부분 반복 문제 확인하는 것이다. 이전 상태 유지 + 개수 제한 일 때는 중복 사용 방지를 위해 2차원 배열을 사용이 유리할 수 있다. 개수제한일 때를 생각해보면 1차원 배열 사용시 중복 사용될 가능성이 있다. 제한이 2개일때 배낭 무게 최대 무게 6아이템 1개에 대하여 무게 2, 가치 10 이라하면dp = {0, 0, 10, 0, 20, 0, 30} 이런식으로 3번 같은 아이템을 사용해 버린다. 때문에 2차원 배열로 같은..

🧫 문제 분석 ✔️ 출처호텔 골드 4 📖 문제배낭문제처음에는 우선 가격대비 효율이 가장 좋은 도시를 찾아서 C / 도시의 고객수 * 가격 + C % 도시의 고객수 를 만족하는 모든 도시의 최소값을 구할라했으나이는 불가능했다. 가격 대비 효율을 단순히 (고객수 - 가격) 순으로 내림차순 정렬하려했으나4 91 5 위의 경우 4 9 가 더 효율이 좋다고 판단해버린다. 즉, 완전 잘못 설계했다. DP로 풀어야하는 문제이다. 각 도시에 대하여 1~C 까지의 가격 최솟값을 구하면된다. 1. 현 도시의 홍보만으로 c를 채우는 경우2. 현 도시의 홍보 1개만 사용하고 나머지 c를 다른 최솟값으로 채우는 경우3. 이전 도시까지와 현재 도시를 비교하여 최솟값을 갱신 그런데 이 문제는 1차원 DP로도 충분히 풀 수 ..

🧫 문제 분석 ✔️ 출처벽 부수고 이동하기 4 골드 2 📖 문제 그래프 탐색 문제기존 벽 부수기와 달리 벽을 부쉈을때 이동가능한 칸의 개수를 부순 자리에 출력하고 벽이 아닌 곳 즉, 0인곳은 그대로 0 을 출력한다. 벽을 부쉈을때 마다 0을 탐색하는것보다 미리 0의 영역을 나눠서 탐색하여 해당 영역의 0의 개수를 구해놓고 각 벽의 위치에서 상하좌우 인접한 칸이 0인지 확인후 해당 칸의 영역에 구해놓은 0의 개수를 더하는 식으로 하면된다. 중요한 점은 영역 중복 연산 처리이다. boolean 이중 배열로 했다가 메모리초과를 계속당했다. Set을 사용하여 해결하였다.✔️ Set.claer()에 대해서set이 가능한 이유는 상하좌우 4가지에 대해서만 영역을 체크하기 때문이다.clear()메서드는 모든 s..

🧫 문제 분석 ✔️ 출처공항 골드 2 📖 문제 서로소 집합의 경로 압축 방법을 사용하여 풀었다. 각 게이트는 도킹 가능한 게이트를 가리킨다. 처음에는 각자 자신을 가리키지만 비행기 도킹시 각 게이트는 자신의 게이트는 이미 도킹되었으므로 도킹 가능한 게이트를 가리켜준다. 만약 가리킨 게이트가 0이라면 이는 더이상 도킹할 수 없다는 의미이다. 예제 2번을 예시로 들어보면2 2 3 3 4 4 비행기 순서 1 2 3 4 게이트 1 2 3 4 게이트가 가리키는 도킹 가능 게이트 1) 1번째 비행기 도킹1 2 3 4 2번째에 도킹후 2번 게이트는 방문처리후 -1로 이전 게이트를 가리키게 한다. 1 1 3 4 2) 2번째 비행기 도킹1 2 3 4 2번째 도킹 시도시 이미 방문을 했기에 가리..

🧫 문제 분석 ✔️ 출처1의 개수 세기 골드 2 📖 문제 BigInteger 로 풀었는데 굳이 안써도 long타입으로 커버쳐지나보다.2^i 인 수의 1의 개수를 누적합으로 구하는데 너무 큰 범위까지 구해서 그렇다.10^16이하까지만 구하면됐는데 ... 포스팅한 이유는 사실 다른사람의 코드를 이해하기 위함이다. https://tussle.tistory.com/1022 이 분의 풀이를 이해하고 정리해보겠다.i = i번째 자리일때 최댓값까지의 1의 개수 i = 2 이면 000~ 111 까지의 1의 개수를 구하는 것이다. i = 3 : 0000 ~ 1111까지의 1의 개수 2^n일때 1의 개수 dp[n] = dp[n-1] * 2 + 2^n if (n == 0) dp[0] = 1;이런 점화식이 나오는데..