알고리즘

문장에서 각 문자의 첫글자를 대문자로 바꾸고 나머지는 소문자. 단, 숫자가 있다면 모두 소문자.ex)"3people unFollowed me" -> "3people Unfollowed Me"split(" ")을 통해 문장을 단어 단위로 list를 만들었고,capitalize() 내장함수를 사용했습니다.def solution(s): answer = '' # 각 문자의 첫단어만 대문자, 나머지는 모두 소문자, 숫자가 나오면 모두 소문자 # 문장 나누기 words = s.split(" ") # 각 단어 앞글자만 대문자 cap_words = [ word.capitalize() for word in words ] # join을 활용해 다시 문장화 answer = ' '.join(cap_..

타겟 넘버.ex)numbers = [1, 1, 1, 1, 1], tartget = 3, return = 5이때,이와 같이 표현될 수 있다. index 0번부터 계속해서 빼고 더하는 동작을 반복하며, target에 맞는지 확인하는 작업을 해주면 된다.dfs에서도 재귀를 사용하여 알고리즘을 짰다.def solution(numbers, target): answer = 0 n = len(numbers) def dfs(idx, rlt): # index가 끝 if idx == n: # 결과와 target이 같을 때 if rlt == target: nonlocal answer answer += ..

위상정렬(Topology)위상정렬은 순서가 있는 작업을 수행해야 할 때 또는 순서를 결정하는 알고리즘입니다. 즉 노드 간의 선후 관계를 고려하여 정렬하는 알고리즘이라고 할 수 있습니다.1. 진입차수노드 간의 선후 관계를 고려해야 하는 점에서 그래프 알고리즘으로 생각할 수 있다. 선후 관계를 고려한다, 즉 방향성을 거스르지 않도록 순서를 나열하는 방법입니다.진입차수는 자기 자신으로 연결되어 들어오는 간선의 개수이다. 그림에서 보면 선형대수 박스의 진입차수는 0,머신러닝 박스의 진입차수는 1,딥러닝 박스의 진입차수는 2그림을 보면 머신러닝을 수강하려면 선형대수를 우선 수강해야 한다. 또한 머신러닝을 수강하면 딥러닝을 수강할 수 있지만 선형대수만 거쳐도 곧바로 딥러닝을 수강할 수 있다.2. 위상 정렬위상 정렬..

플로이드 워셜플로이드 워셜은 다익스트라와 마찬가지로 최단 경로를 구하는 알고리즘입니다.1. 다익스트라와 플로이드 워셜다익스트라와의 큰 차이점은 플로이드 워셜은 모든 노드에서 도착할 수 있는 모든 노드의 최소거리를 구하는 알고리즘, 다익스트라는 특정 노드에서 이동할 수 있는 모든 노드에 대해 최소거리를 구하는 알고리즘입니다. (다익스트라는 양의 가중치만 허용됩니다) 즉, 다익스트라는 부산에서 서울 대구까지의 최소 거리를 구하는 알고리즘이고 플로이드 워셜은 부산-대구, 부산-서울, 서울-대구의 거리를 한 번에 계산합니다 2. 플로이드 워셜 점화식모든 노드별로 특정 노드를 거쳐 다른 노드로 가는 최단 경로를 저장하기 위해 2차원 LIST를 사용합니다. 따라서 전체 노드가 N개일 때, 알고리즘의 시간 복잡도는 ..

백트래킹단어 그대로 자식 노드의 유망성을 판단한 뒤 해당 노드가 유망하지 않다면 부모 노드로 돌아가 다른 자식 노드를 찾는 방법이다.1. DFS와 백트래킹그래프 탐색 기법 중 하나인 DFS와 백트레킹의 차이를 먼저 알아보기 위해 예시를 한번 보자. 0  a+b+c+d = 30 이 되는 a, b, c, d를 모두 구하여라.a = 10이라도 b = 0 ~ 100, c = 0 ~ 100, d = 0 ~ 100 이 될 수 있다.만약 a = 10 이라면 b는 0 이러한 모든 경우의 수를 찾아서 탐색하는 것이 DFS이다.백트레킹의 경우를 찾아보자.이 경우 0부터 시작해서 모든 조합을 찾아나갈 것이다.b = 21이라면 그 이상은 탐색할 필요가 없어지게 되고 다음으로a = 11 일 때 b, c, d의 경우를 찾는 절차..

퀵 정렬 퀵 정렬... 말 그대로 가장 빠른 정렬 알고리즘입니다. 바로 알아봅시다. 1. 퀵 정렬 동작 과정 퀵 정렬 함수 코드 def quick_sort(lst): def sort(low, high): if high

문자열 게임1. 문제 설명문제는 간단합니다. W(지워야 하는) 문자열이 주어지고 그 대상 S 문자열이 주어집니다.그다음 N의 숫자가 주어지며 밑으로 N 개의 줄에는 명령어가 주어집니다.명령어 L 은 왼쪽에서 부터 탐색해 처음 등장하는 W 문자열을 제거합니다.명령어 R 은 오른쪽에서 부터 탐색해 처음 등장하는 W 문자열을 제거합니다.최종적으로 모든 명령을 수행했을 때 문자열 S에 남은 문자열 W 가 있다면 게임에서 패배하게 됩니다. 출력은 순서대로 성공한 명령어의 수, 남은 문자열 S, 승패 문구입니다.승리한 경우 Perfect!, 패배한 경우 You lose! 를 출력합니다.2. 접근과 풀이이 문제는 결론부터 말하자면입니다.그럼 스택으로 접근해 봅시다!aaaaabbbb라는 문자열 S가 주어지고 ab라는 ..

다익스트라1. 최단경로 알고리즘특정 지점까지 가장 빠르게 도달할 수 있는 경로를 찾는 알고리즘. 플로이드-워셜(Floyd-Warshall)다익스트라(Dijkstra)벨만-포드(Bellman-Ford)노드의 개수가 적을 경우 플로이드-워셜을 사용하는 것이 효율적입니다.노드와 간선의 개수가 모두 많을 때 다익스트라를 사용하는 것이 효율적입니다.오늘은 다익스트라를 배워봅시다.2. 특징순환 포함 허용간선에서 음의 가중치를 허용 않음(거리 또는 비용)기본적으로, 탐욕 알고리즘에 속함매번 가장 비용이 적은 노드를 선택하려고 함3. 동작최단거리 테이블을 최댓값으로 초기화시켜 줍니다. (INF)출발노드와 도착노드를 설정합니다. 1번 노드가 Start 노드 , 6번 노드가 End 노드입니다.테이블은 정점의 갯수 만큼 1..