이숭간 공부기록

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

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

www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제유형 : 수학, DP 문제풀이 : 정답코드 : 1. 내가푼코드 (DP 로품, 근데 걍 빨리 풀고싶어서 좀 안좋게품 호호 _ 메모리낭뷔, 그래도 편법은 아니지않나? ) import sys input = sys.stdin.readline n = int(input()) dp = [-1] * (n+8) dp[2]=1 dp[4]=2 dp[5]=1 dp[6]=3 dp[7]=2 dp[8]=4 for i in range(9, n+1): dp[i] = min(dp[i-2], dp[i-5])+1 print(dp[n]) 2. 다른분 코드 ( DP..

www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제유형 : 큐 (자료구조) 문제풀이 : 원 형태로 연결되어있는 자료구조를 큐로 구현하기 내가 원하는 곳 (타겟지점) 으로 도달하기까지 거치는 것들은 큐에서 빼고 다시 큐에 넣어주는 형식으로 하면 원 형태의 자료구조를 큐로 구현할 수 있다. ex ) 1,2,3,4,5,6,7에서 3을 타겟으로 할때 거치는 1,2,는 다시 뒤에 넣어줌으로써 3,4,5,6,7,1,2를 구현할 수 있다. 정답코드 : import sys input = sys.stdin.readline n,k = map(int, inpu..

www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제유형 : 수학, 에라토스테네스의 체 문제풀이 : 2부터 차례대로 담긴 배열을 순회하면서, 배수들을 전부 표시하고 표시된걸 만나면 건너뛰는식으로 소수가 아닌것들을 전부 표시한다 예를들어 2는 표시가 안되어있으므로 4,6,8,10 ... 로 표시를 하고 3도 마찬가지로 6,9,를 표시할건데 이미 앞에서 6이 표시되었으므로 이때는 건너띄고 9로 넘어간다. 만약 4처럼 처음부터 바로 2에의해 표시된 수를 만난경우 바로 건너뛴다. (다음으로_ 5로) 참고 : m.blog.naver.c..

www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 문제유형 : 정렬 문제풀이 : 사용자들 정보가 담긴 배열의 원소를 튜플로 저장 , 튜플의 형태는 (나이, 이름, 가입한순서) 정렬하는데 1순위 나이, 2순위 가입한순서로 정렬 출력은 나이, 이름 파이썬 튜플정리 ! 튜플은 생성후 변경 불가능 (삽입, 삭제 불가능) 소괄호를 이용해 선언 + 연산자를 이용해 튜플 2개를 한개의 튜플로 합칠 수 있다. 슬라이스 기능 이용가능 (리스트와 방법 동일) len(), max(),..