개발하는 삶

#대부분 구글링, 백준사이트의 코드를 참고해서 학습하였습니다 10610 https://www.acmicpc.net/problem/10610 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라. //풀이방법 //30의 배수 : 뒷자리 0 포함, 3x의 배수 (숫자 0, 3의 배수 필요..

최단경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든지점까지의 최단 경로 각 지점을 그래프에서 노드로 표현 지점간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단경로 알고리즘 특정한 노드에서 출발. 다른 모든 노드로 가는 최단경로 계산 음의 간선이 없을때(음수가 아닐시) 정상적으로 동작함. 그리디 알고리즘으로 분류됨 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복 출발 노드를 설정 최단거리 테이블을 초기화함 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산, 최단거리 테이블을 갱신 위 과정에서 3,4반복 매 상황마다..

다이나믹 프로그래밍(동적계획법) 다음 두가지 조건을 만족할 때 사용하기 최적부분구조 큰 문제를 작은문제로 나눌수있음 중복되는 부분 문제 동일한 작은 문제를 반복적으로 해결해야함 피보나치 수열 1,1,2,3,5,8,13,21,34,55,89 ... 점화식 : 인접한 항들 사이의 관계식 1,1을 더해 2. /// 2,3을 더해 5 ... 문제점 : 재귀함수를 통해 해결하면, 같은 것이 중복적으로 호출되는 문제가 있다 탑다운 VS 보텀업 메모이제이션(탑다운, 하향식) 이전에 한 번 계산된 결과를 일시적으로 메모리 공간에 메모하는 기법 값을 기록해 놓는다는 점에서 캐싱이라고도 함 #메모이제이션 하기 위한 리스트 초기화 d = [0] * 100 #피보나치 함수를 재귀함수로 구현 def fibo(x): #종료 조건..

순차 탐색 리스트 안에 특정 데이터를 찾기위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진탐색 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점을 이용해 탐색범위 설정 재귀함수로 소스코드 구현 import sys def binary_search(array, target, start, end): if start > end: #만약 값을 못찾을경우 None 반환 return None mid = (start+end)//2 #중간값 if array[mid] == target: #값을 찾았을때 return mid # 중간값이 찾는 값보다 큰 경우. 왼쪽으로 중간값을 옮김 elif array[mid] > target: return binary_search(array..

선택 정렬 데이터를 특정한 기준에 따라 순서대로 나열하는 것 아이디어가 매우 간단함 선택 정렬 방법 처음에 가장 작은 수를 선택하고 맨 앞과 위치를 바꿈 그 다음 작은수를 맨앞의 두번째와 자리를 바꿈 이 과정을 반복 #순서가없는 0~9의 수 array = [7,5,9,0,3,1,6,2,4,8] for i in range(len[array]): #인덱스 첫~끝 차례대로 대입 min_index = i #가장 작은 원소가 들어있는 인덱스 찾기(1번으로 기준) # 인덱스 두번째부터~ # 맨앞의 인덱스 > 두번째,세번째... 비교했는데 # 비교한 값이 더 작으면 그 인덱스를 min으로 바꿈 for j in range(i+1, len(array)): if array[min_index] > array[j]: min_..

그래프 탐색 알고리즘 DFS/BFS 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 DFS 깊이를 우선으로 하는 탐색 스택자료구조(혹은 재귀함수)를 이용. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문처리함. 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼낸다 더이상 2~3 과정을 수행할 수 없을때까지 반복 #다 골고루 방문해서 (중복없이) 출력하는것. 위 그림을 보고 아래를 만듬. #숫자 오름차순대로 방문한다고 생각하고 짜기 #각 노드가 연결된 정보 표현. 0번째는 비워두기! graph = [[],[2,3,8],[1,7],[1,4,5],[3,5],[3,4],[7],[2,6,8],[1,7]] ..