정구리의 우주정복

최단경로 알고리즘엔 크게 두가지 종류가 있다 1. 한지점 -> 다른지점 최단경로 2. 모든지점 -> 다른 모든지점 최단경로 1번은 주로 다익스트라를 이용해서 풀고 2번은 플로이드 워셜 을 이용해서 푼다고 한다 근데 나는 어려운건 잘 못해서 오늘은 다익스트라만 하려고 한다 다익스트라 알고리즘 알고리즘에서는 그리디로 분류한다 한마디로 모든곳을 방문방문 하면서 제일 작은 값을 찾아내는 거임 과정은 1) 출발 노드 설정 2) 최단거리 테이블을 초기화 3) 방문하지 않은 노드 중에서 최단거리가 짧은 노드 선택 4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신 5) 위 과정에서 3과 4를 반복 이 과정을 그림으로 이해해보자 (발그림 ㅈㅅㅈㅅ) 나름 열심히 써봤는데 .. 암튼 이런 과정..

보호되어 있는 글입니다.

이진 탐색은 반으로 쪼개가면서 탐색을 하는 방식이다 *내부의 데이터가 정렬되어야만 사용이 가능하다는 특징이 있음 시작 , 끝 , 중간 데이터가 있어야 한다 찾으려는 데이터와 중간점의 데이터를 비교하고 다시 시작 , 끝 , 중간 을 조절해주면서 범위를 좁혀가는 탐색 방법이다 0 2 4 6 8 10 12 14 16 18 중에서 4 를 찾고자 한다면 0 2 4 6 8 10 12 14 16 18 처음값 0 중간값 8 끝값 18 일때 찾으려는 4 보다 중간값인 8 이 더 크므로 더이상 8-16 까지의 데이터는 볼 필요가 없다 그리고 끝 값을 8의 하나 앞인 인 6으로 해주자 0 2 4 6 8 10 12 14 16 18 처음 값 0 중간값 2 끝값 6 일때 4는 중간값인 2보다 크므로 0-2 까지 의 데이터는 볼 ..

학생의 이름과 점수를 입력받았을때 점수가 낮은 순서대로 "이름" 을 출력하는 방법 ex) 2 홍길동 95 이순신 77 >> 이순신 홍길동 #성적이 낮은 순서로 학생 출력하기 n = int(input()) array = [] for _ in range(n): input_data = input().split() #!!! 학생 정보를 (점수,이름) 으로 묶어줄 수 있다 !!!! array.append((input_data[0],int(input_data[1]))) array = sorted(array,key = lambda array : array[1]) #[1] 기준으로 정렬 for student in array: print(student[0],end = ' ') array 에다가 (점수,이름) 의 형태로 ..

문제에서 상하 좌우로 이동을 시킨뒤에 최종적인 좌표를 구하세요 ! 라고 하는 문제가 자주 나온다 N*N 크기의 정사각형 공간에서 L : 왼쪽으로 한칸 이동 R : 오른쪽으로 한칸 이동 U : 위로 한칸 이동 D : 아래로 한칸 이동 이라고 했을때 L (0,-1) R (0, 1) U (-1, 0) D (1, 0) 으로 이동하게 된다 정사각형의 공간을 벗어나는 움직임은 무시된다고 생각 했을때 #상하좌우 n = int(input()) move = list(map(str,input().split())) x,y = 1,1 move_x = [0,0,-1,1] move_y = [-1,1,0,0] move_type =['L','R','U','D'] for i in move: for j in range(len(move_..

그리디 알고리즘은 "현재 상황에서 지금 당장 좋은걸 고르는 방법" 을 이용한 알고리즘이다 대표적인 문제로 거스름돈 문제가 있다 동전의 갯수를 최소화하여 돈을 거슬러 주는 문제이다 거스름 돈을 줄때에 제일 큰 금액부터 거슬러 주면 성립이 된다 #greedy 의 대표 문제 거스름돈 money = int(input()) count = 0 coins = [500,100,50,10] for i in coins: count += money // i money %= i print(count)

python 소스로 공부를 해볼거임 선형 탐색이란 ? 앞에서 부터 뒤로 순차적으로 탐색을 하는 알고리즘 ! 정렬이 되어있다고 해도 앞에서부터 뒤로 탐색을 하는거라서 정렬이 된 경우와 안된경우 모두 O(n) 이다 리스트의 길이에 비례해서 소모시간이 늘어나게 된다 가장 쉬운 탐색 코드이지만 리스트의 길이가 길어질수록 비효율적인 탐색방법이다 :-) 파이썬 소스 def linear_search(L,x): i =0 while i

그리디 알고리즘이란 ? 당장 눈앞의 최적의 조건을 따르는 알고리즘 ! ex) 거스름돈 문제 주로 무조건 큰, 긴 , 작은 , 짧은 등등 극단적으로 접근한다는 점에서 '정렬'과 같이 쓰이는 경우가 많다 최적의 해를 보장하는 경우도 많지만 그렇지 못하는 경우가 더 많아서 DP(다이나믹 프로그래밍 ) 등을 사용할 수도 있다 ex) 거스름돈 문제 500,100,50,10 원의 동전으로 거스름돈을 반환해야 할 때 가장 적은양의 거스름돈을 반환하도록 해보자 !! 500원이 가장많아야하고 100->50->10 순서로 거슬러주면 된다 파이썬 코드 value = int(input()) #거스름돈 result = 0 #동전의 개수 result += value//500 #500으로 나눈것의 몫을 더해준다 value %= 5..