오늘의 기록

스택 & 큐

스택 stack=[] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) print(stack[::-1]) 결과 [5,2,3,1] [1,3,2,5] 스택은 그냥 리스트의 형태로 사용할 수 있다. 큐 from collections import deque queue=deque() queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.popleft() queue.append(1) queue.append(4) queue.popleft() print(queue..

최단 경로

가장 빠르게 도달하는 방법 최단 경로(Shortest path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 '길 찾기' 문제라고도 불린다. 최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점(국가 or 마을 등)은 그래프에서 '노드'로 표현되고, 지점간 연결된 도로는 그래프에서 '간선'으로 표현된다. 또한 실제 코딩테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출력된다. 코딩 테스트 수준에서는 다익스트라 최단 경로와 플로이드 워셜 알고리즘 유형만 파악해도 충분하다. 더불어 앞서 공부한 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다는 특징이 있다. 다익스트라 최단 경로 알고리즘 다익..

[JPA] 객체지향 쿼리 언어2 - 중급 문법

자바 ORM 표준 JPA 프로그래밍 - 기본편 스프링 핵심 원리 - 기본편 - 인프런 스프링 입문자가 예제를 만들어가면서 스프링의 핵심 원리를 이해하고, 스프링 기본기를 확실히 다질 수 있습니다. 초급 프레임워크 및 라이브러리 웹 개발 서버 개발 Back-End Spring 객체지향 온 www.inflearn.com 강의를 들으며 생각 정리 + "자바 ORM 표준 JPA 프로그래밍" 책 참고 경로 표현식 경로 표현식이란 .(점)을 찍어 객체 그래프를 탐색하는 것이다. 다음 JPQL을 보자. select m.username -> 상태 필드 from Member m join m.team t -> 단일 값 연관 필드 join m.orders o -> 컬렉션 값 연관 필드 where t.name = '팀A' 용..

편집 거리

편집 거리 알고리즘이란, 두 문자열의 유사도를 판단하는 알고리즘이다. 리벤슈테인 거리라는 이름으로도 불린다. 문제를 통해 알아보자. 문제 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B를 만들고자 한다. 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있다. 삽입 : 특정한 위치에 하나의 문자를 삽입한다. 삭제 : 특정한 위치에 있는 하나의 문제를 삭제한다. 교체 : 특정한 위치에 있는 하나의 문자를 다른 문자로 교체한다. 이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하라. 입력 문자열 A, B 각 문자열은 영문 알파벳으로만 구성되어 있으며,..

못생긴 수

문제 못생긴 수란 오직 2,3,5만을 소인수로 가지는 수를 의미한다. 1은 못생긴 수라고 가정한다. n번째 못생긴 수를 찾아라. 못생긴 수 : {1,2,3,4,5,6,8,9,10,12,15....} 입력 n (1 ~ 1,000) 출력 n번째 못생긴 수를 출력한다. 풀이 n = int(input()) ugly = [0] * n # 못생긴 수를 담기 위한 테이블 (1차원 DP 테이블) ugly[0] = 1 # 첫 번째 못생긴 수는 1 # 2배, 3배, 5배를 위한 인덱스 i2 = i3 = i5 = 0 # 처음에 곱셈 값을 초기화 next2, next3, next5 = 2, 3, 5 # 1부터 n까지의 못생긴 수들을 찾기 for l in range(1, n): # 가능한 곱셈 결과 중에서 가장 작은 수를 선택..

백준 18353 - 병사 배치하기

www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예..

금광

문제 N*M 크기의 금광이 있다. 금광은 1*1 크기의 칸으로 나누어져 있다. 채굴자는 첫 번째 열, 어느 행에서 출발하여 금을 캐기 시작한다. 이후에 m번에 걸쳐 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 구한다. 입력 첫째 줄에 테스트 케이스 T (1 ~ 1000) 매 테스트 케이스 첫째 줄에 n, m (1 ~ 20) 둘째 줄에 n*m개의 위치에 매장된 금의 개수 (1 ~ 100) 출력 매 테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력한다. 풀이 # 테스트 케이스(Test Case) 입력 for tc in range(int(input())): # 금광 정보 입력 n, m = map(int, input()...

[JPA] 객체지향 쿼리 언어1 - 기본 문법

자바 ORM 표준 JPA 프로그래밍 - 기본편 스프링 핵심 원리 - 기본편 - 인프런 스프링 입문자가 예제를 만들어가면서 스프링의 핵심 원리를 이해하고, 스프링 기본기를 확실히 다질 수 있습니다. 초급 프레임워크 및 라이브러리 웹 개발 서버 개발 Back-End Spring 객체지향 온 www.inflearn.com 강의를 들으며 생각 정리 + "자바 ORM 표준 JPA 프로그래밍" 책 참고 소개 EntityManager.find() 메소드를 사용하면 식별자로 엔티티 하나를 조회할 수 있다. 이렇게 조회한 엔티티에 객체 그래프 탐색(a.getB() 등)을 사용하면 연관된 엔티티들을 찾을 수 있다. 그러나 만약 나이가 30살 이상인 회원을 모두 검색하고 싶다면 find 메소드만으로 해결되지 않는다. 결국 ..