이번 포스팅은 파이썬의 heapq모듈의 코드를 참고하여 작성하였습니다. 우선순위 큐 (Priority Queue) 우선순위 큐의 각 원소들은 우선순위를 갖고 있고, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리되는 자료구조로, 배열, 연결리스트, 힙 등으로 구현할 수 있습니다. 그러나 힙으로 우선순위 큐를 구현하면 데이터의 삽입이나 삭제를 위한 시간 복잡도 모두 $O(log2n)$ 로 빠른 처리 속도를 기대할 수 있습니다. 실제로 파이썬 모듈 코드를 보면 주석 제일 첫 번째 줄에서 다음과 같이 언급하였습니다. Heap queue algorithm (a.k.a Priority Queue) 큐 (Queue) 우선순위 큐를 알아보기 전에 먼저 큐를 간단히 정리하겠습니다. 큐는 먼저 들어..

의존성 설정하기 Maven의 경우에는 pom.xml Gradle의 경우에는 build.gradle 파일에 아래의 내용을 추가합니다. 저는 Gradle로 작업했습니다. implementation 'org.springframework.boot:spring-boot-starter-data-jpa' runtimeOnly 'com.h2database:h2' Entity 생성하기 테이블에 입력할 데이터를 취급하는 클래스 public class Hello { private long id; private String name; private String author; public Hello(long id, String name, String author){ this.id = id; this.name = name; th..

JDBC (Java Database Connectivity) 데이터베이스를 이용하기 위해서는 많은 SQL쿼리를 작성하고 어플리케이션에서 데이터베이스를 활용하기 위해서는 자바 코드로 SQL쿼리를 동작시켜야 하는데 JDBC가 그것을 가능케합니다. 코드 예시 public void deleteData(int id){ PreparedStatement st = null; try{ st = db.conn.prepareStatement(DELETE_DATA_QUERY); st.setInt(1, id); st.execute(); } catch(SQLExceptrion e){ logger.fatal("Query Failed : " + DELETE_DATA_QUERY, e); } finally{ if (st != null)..

H2 메모리 데이터베이스 H2 데이터베이스는 우리 메모리에 데이터를 임시로 저장하는 것으로 어플리케이션 제작에 있어서 어떤 데이터베이스 서버를 이용할 지 지정하기 전에 어플리케이션의 작동을 테스트하기 위해 사용하는 모의 데이터베이스입니다 우선 H2데이터베이스를 스프링에서 사용하기 위해서는 아래의 코드들을 pom.xml에 추가해야합니다. org.springframework.boot spring-boot-starter-data-jpa com.h2database h2 runtime 서버를 구동시키면 로그중에 다음과 같이 h2데이터베이스가 연동되는 것을 볼 수 있습니다. 데이터베이스는 특정한 랜덤 아이디에 이용 가능합니다. 하지만 데이터베이스에 연결하는 데 랜덤 아이디를 사용하기 보다는 고정 아이디로 사용하는 ..

VScode에서 Spring 실행하기 마켓플레이스에서 Spring Boot Extension Pack 설치 Ctrl + Shift + p를 누르고 Spring Initializer 선택 2.7.7 선택 (나중에 더 나은 버전이 있다면 그 버전을 선택하세요) Java 선택 프로젝트 이름 지정 메인 프로젝트 이름 설정 jar 선택 Java 버전 선택 Spring 의존성선택 의존성에 대한 자세한 사항은 좀 더 공부해서 올리겠습니다. 여기서는 Spring Web을 사용했습니다. Spring Web을 클릭하고 엔터 누르시면 됩니다. work space지정하기 생성할 Spring 프로젝트를 저장할 위치를 지정합니다. work space를 지정하면 해당 위치에 프로젝트 폴더가 생성되어있는 것을 확인할 수 있습니다. ..

개념 브루트 포스는 흔히 암호를 해독하기 위해 암호학에서 연구되고있으나 알고리즘에서는 탐색의 방법으로 사용되고 있다. Brut : (형) 짐승 같은, 난폭한 Force : (명) 힘 브루트 포스는 완전탐색알고리즘으로 무식하다 싶을 정도로 처음부터 끝까지 쭉 탐색하는 방식이다. 장점 항상 정확도 100%를 보장한다. 알고리즘 설계가 간단하다. 단점 시간이 너무 오래 걸린다. 비효율적인 메모리 사용 종류 선형 순차 탐색 비선형 깊이 우선 탐색(DFS/Depth First Search) 너비 우선 탐색(BFS/Breadth First Search) 백트레킹

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 내 코드 import sys curr = 100 # 현재 채널 target = int(sys.stdin.readline()) # 목표 채널 n = int(sys.stdin.readline()) broke_num = list(map(str,sys.stdin.readline().split())) # 망가진 버튼 ans = abs(curr - target) # 현재 채널에서 목표 채널까..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 내 코드 import sys n, m = map(int, sys.stdin.readline().split()) trees = list(map(int, sys.stdin.readline().split())) start = 0 end = max(trees) def check(cut): result = 0 for i in trees: if i > cut: resu..

이분 탐색 혹은 이진 탐색이라고도 불리며 탐색하고자 하는 값들이 정렬되어있어야 사용할 수 있습니다. 예를 들어 1부터 10까지의 배열이 있고 7을 찾는다고 합니다. 여기서 우리는 시작 값은 1 끝 값은 10으로 설정합니다. 이제 중앙값을 찾아줘야 하는데 끝값과 시작값을 더하고 2로 나눈 값을 중앙값으로 합니다. 계산해보면 (10 + 1) / 2 = 5 입니다. (반올림 한 값입니다.) 이제 여기서 중앙값과 찾고자 하는 7을 비교해봅니다. 7이 5보다 크므로 이제 우리는 5 이상의 값들 안에서 7을 찾으면 됩니다. 그럼 여기서 한번 더 중앙값을 찾아줍니다. 이번에는 (10 + 5) / 2 이므로 중앙값은 7이 되겠네요. 이제 중앙값은 우리가 찾던 7이므로 처리를 종료합니다. 이분 탐색을 구현하면 한 번 확..

https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 내 코드 import sys q = sys.stdin.readline().rstrip() answer= set() for i in range(1, len(q)+1): for j in range(len(q)-(i-1)): answer.add(q[j:j+i]) print(len(answer)) 내 풀이 이번 문제는 부분 문자열을 구하고 중복되지 않은 문자열의 총 개수를 구하는 문제입니다. 저는 파이썬의 기본 자료구조인 집합을 활용하였습니다. 집합은 기본적으로 중복되는 ..