전체 글

[Programmers/Python] 자물쇠와 열쇠 || 구현

프로그래머스 자물쇠와 열쇠 파이썬 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 더보기 ❍ 문제 설명 고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다. 자물쇠에는 ..

[Programmers/Python] 문자열 압축 || 구현

프로그래머스 60057 문자열 압축 파이썬 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr더보기❍ 문제 설명 데이터 처리 전문가가 되고 싶은 **"어피치"**는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와..

[BOJ/Python] 럭키 스트레이트 || 구현

백준 18406 럭키 스트레이트 파이썬 18406번: 럭키 스트레이트첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다.www.acmicpc.net더보기❍ 문제어떤 게임의 아웃복서 캐릭터에게는 럭키 스트레이트라는 기술이 존재한다. 이 기술은 매우 강력한 대신에 항상 사용할 수는 없으며, 현재 게임 내에서 점수가 특정 조건을 만족할 때만 사용할 수 있다.특정 조건이란 현재 캐릭터의 점수를 N이라고 할 때 점수 N을 자릿수를 기준으로 반으로 나누어 왼쪽 부분의 각 자릿수의 합과 오른쪽 부분의 각 자릿수의 합을 더한 값이 동일한 상황을 의미한다. 예를 들어 현재 점수가 123,402라면 왼쪽 부분의 각 자릿수의 합은 1+2+3, ..

[Programmers/Python] 무지의 먹방 라이브 || 그리디, 우선 순위 큐, 최소 힙

프로그래머스 42891 무지의 먹방 라이브 파이썬 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 더보기 ❍ 문제 설명 효율성 테스트에 부분 점수가 있는 문제입니다. 평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다. 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다. ..

[BOJ/Python] 1439번: 뒤집기 || 그리디, 문자열

백준 1439 뒤집기 파이썬 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 더보기 ❍ 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2..

[Algorithm/Python] 위상 정렬(Topology Sort)란?

들어가며본 포스팅에서는 위상 정렬에 대해 소개합니다.📌 위상 정렬이란?위상 정렬(Topology Sort)이란 방향 그래프의 모든 노드를 방향성을 모두 지키며 순서대로 나열하는 것을 의미합니다. 특정한 노드로 들어오는 간선의 개수를 진입차수라 합니다. 1️⃣ 진입차수가 0인 노드를 큐에 담습니다. 2️⃣ 큐가 비어있을 때까지 다음의 과정을 반복합니다. - 1 ) 큐에 담긴 노드를 꺼내어 해당 노드에서 출발하는 모든 간선을 그래프에서 제거합니다. - 2 ) 진입차수가 0인 노드를 큐에 담습니다. 모든 원소를 방문하지 않았는데 큐가 비었다는 것은 사이클이 발생했다는 것을 의미합니다. 큐에 담기는 노드가 2개 이상인 경우, 위상 정렬된 후의 결과가 여러 개일 수 있습니다. 1. 진입차수가 0인 노드 1을 큐에..

[Algorithm/Python] 크루스칼 알고리즘이란? || 최소 신장 트리

들어가며본 포스팅에서는 신장 트리에 대해 그리고 최소 신장 트리 알고리즘인 크루스칼 알고리즘에 대해 소개합니다. 📌 신장 트리란?신장 트리(Spanning Tree)란 하나의 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 말합니다.예를 들어 위와 같은 그래프가 존재한다고 할 때, 아래의 경우는 신장 트리인지를 확인해보겠습니다. 이 그래프는 노드 1을 포함하고 있지 않기 때문에 신장 트리에 해당하지 않습니다. 이 그래프는 모든 노드를 포함하고 있지만, 사이클이 존재하므로 신장 트리에 해당하지 않습니다. 이 그래프는 모든 노드를 포함하고 있으며, 사이클이 존재하지 않으므로 신장 트리에 해당합니다. 신장 트리의 노드 개수와 간선의 관계를 보면, 노드의 개수가 5개일 때, 간선..

[Error] h2-console 403 오류 해결

들어가며Spring에서 MariaDB를 사용해오다가, 최근에 친구와 H2로 DB를 사용하는 과정에서 403 오류가 계속 발생하였다. 이 문제를 간단하게 해결하는 과정을 포스팅해본다..!📌 h2-console 403 오류 해결프로젝트를 실행한 후, h2-console로 접근 시, 403 오류로 DB를 열어볼 수가 없었다. 이를 해결하기 위해 SecurityConfig 클래스를 살펴보았다. "/h2-console/**"로 다른 api처럼 permitAll을 해주어도 해결되지 않았고,, 다음과 같이 설정해주니 해결되었다. @Bean public SecurityFilterChain securityFilterChain(HttpSecurity http, AuthenticationConfiguration authen..

[Algorithm/Python] 서로소 집합(Disjoint Sets) 알고리즘이란?

들어가며본 포스팅에서는 서로소 집합과 구현 방식에 대해 소개합니다.📌 서로소 집합이란?서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미합니다. 예를 들어 {1, 2}와 {3, 4}는 서로소 관계이지만, {1, 2}와 {2, 3}은 서로소 관계가 아닙니다. 서로소 집합 자료구조는 union과 find라는 2개의 연산이 이루어집니다. union(합집합)이란, 하나의 집합으로 합치는 연산을 의미하며, find(찾기) 연산은 특정 원소가 어느 집합에 속하였는지를 찾아내는 연산입니다. 1️⃣ union(합집합) 연산을 통해, 서로 연결된 두 개의 노드를 확인합니다. - 1 ) 노드 A와 노드 B의 루트 노드인 A'와 B'를 찾습니다. - 2 ) 루트 노드 A'를 루트 노드 B'의 부모 노..

[Algorithm/Python] 플로이드 워셜 알고리즘이란?

들어가며 본 포스팅은 플로이드 워셜 알고리즘에 대해 소개합니다. 📌 플로이드 워셜 알고리즘 플로이드 워셜(Floyd-Warshall) 알고리즘이란, 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘입니다. 기존에 소개된 다익스트라 알고리즘에서의 최단 거리 테이블에서 거리가 가장 짧은 노드를 탐색해야 했던 과정을 생략할 수 있다는 점이 차이점입니다. 모든 노드가 다른 노드로 가는 최단 거리의 정보를 2차원 리스트에 담아 저장합니다. 노드의 개수 N만큼 점화식에 맞게 2차원 리스트를 갱신하므로 다이나믹 프로그래밍으로 볼 수 있습니다. ☑️ 시간 복잡도 모든 최단 경로를 2차원 리스트에 담아 처리하므로 매번 $O(N^2)$의 시간이 소요되며, 노드의 개수 N만큼 $O(N..