이숭간 공부기록

www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 문제유형 : 다익스트라 문제풀이 : 다익스트라 알고리즘 구현 단 노드의 개수가 10000개이상이므로 힙 자료구조를 써서 우선순위큐로 구현해야한다. 정답코드 import sys import heapq input = sys.stdin.readline INF = int(1e9) v, e = map(int, input().split()) start = int(input()) graph = [..

최단경로 알고리즘이란, 가장 짧은 경로를 찾는 알고리즘 다양한 문제상황 한지점에서 다른 한지점 한 지점에서 다른 모든지점 모든 지점에서 다른 모든지점 각 지점은 그래프에서 노드로 표현하고 지점간 연결된 도로는 간선으로 표현함 ex ) 마을과 마을을 있는 도로, 도시를 있는 통로 등등 1. 다익스트라 알고리즘 특정한 노드(출발노드)에서 다른모든 노드로 가는 최단경로를 계산 (음의간선이 없을때) 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. (일종의 그리디 알고리즘) 동작과정 출발노드를 설정 최단거리 테이블을 초기화 (자기자신을 제외한 모든노드까지의 거리를 무한대로 설정, 자기자신은 0) 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택 ( 이 과정을 통해 특정 노드까지의 최단..

자바와 데이터베이스의 중간단계역할의 변천과정(?) 순수JDBC -> JDBC템플릿 -> JPA (MyBatis랑 같은선상) JPA는 개발자가 직접 작성해야하는 SQL쿼리도 자동으로 해주기때문에 개발생산성이 매우 높아짐. 객체를 JPA에 넣으면 JPA가 중간에서 디비에 sql날리고 데이터가져고오고 하는것을 알아서 처리해준다. JPQL = 테이블을 보고 질의를 날리는게 아니라 객체를 대상으로 쿼리를 날리면 SQL로 번역됨 JPA는 인터페이스고 각 구현체는 여러가지가 있다. 대표적인게 Hibernate! JPA는 객체와 ORM이라고 표현할수있는데 ORM은 객체와 관계형디비를 매핑해준다는 뜻이다. 이때 매핑은 어노테이션을 통해서 한다. @Entity JPA가 관리하는 엔티티가 되는것 @Id 얘는 PK다 @Gne..

www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제유형 : 수학, 그리디, 문자열 문제풀이 : 괄호를 적절히 넣어 최솟값을 만드는 방법이므로 - 를 만나면 앞에 괄호를 넣는다. 언제 괄호를 닫아주는가? 그다음 - 를 만나면 괄호를 닫고 다시 괄호를 열여준다. +일때는 계속 지나간다. 만약 배열이 모두 끝났는데 아직 괄호가 열려있는 상태라면 맨 마지막에 괄호를 추가하여 닫아준다. 괄호가 열려있냐 닫혀있냐의 여부는 flag변수를 통해 수행한다. 위 과정을..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제유형: BFS 문제풀이 answer배열 = 해당노드를 몇초에 처음 방문하게 되는지 저장하기 위한 배열 + 방문여부또한 체크할수있다. 큐에서 노드하나 빼서 해당노드를 기준으로 -1, +1, 2배를 해준다. 결과로 나온 3개의 노드를 순회하며 아직 방문전이고 ((이미 방문한 노드일경우 중복해서 큐에 넣을필요가 없기때문)) n이아니면 (만약 어떤 이동을 수행한 결과가n이면 결국 자기자신..

www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net 문제유형 : 스택, 리스트, 구현 문제풀이 : 커서의 위치를 0으로 두고 앞뒤로 움직일때마다 커서도 움직이는 형태로 진행하면 구현은 되나 시간복잡도가 높아져서 시간초과가난다. 처음에나도 이런 방식으로 코딩하고 구현은 됬는데 시간초과가 나서 실패함 사실 조금만 생각해봐도 테스트의 길이가 최대 1,000,000이므로 커서위치를 구해서 커서위치에서 지우거나 삽입할때 시간이 오래걸리게된다 . (pop(커서위치)..