알고리즘/python

H-index는 음... 연구자의 역량을 나타내는 지표..? 라는데일단 문제 해설을 하면 예시로 보는것이 편하다.ex) citations = [3, 0, 6, 1, 5] , return = 3citations의 길이는 논문 수,각 요소는 각 논문의 인용횟수이다. 즉, 0번 인덱스의 논문을 3회 인용했다는 것이다.여기서 H-index는 n개의 논문 중, h번 인용된 논문의 갯수가 h개와 같거나 보다 커야한다.물론 h는 h번 인용되거나 그보다 적게 인용된 논문의 갯수를 disused라 했을때,h >= disused 여야한다. 이를 토대로 깊은 생각없이 바로 코드를 작성했다.def solution(citations): answer = 0 n = len(citations) # 논문 수 use..

이번 문제는 줄 서는 방법.3명이 줄을 서는 방법은 3!, 총 6가지이다. 물론 배치는 사전순.이 문제 lv2라 얕보고 고생했다.우선 손으로 풀어보면 3명이 줄서는 방법은 아래와 같다.[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]여기서, 5번째 순서를 도출해야한다.보면 앞자리에 특정숫자는 (n-1)!의 갯수를 가진다. 무슨 소리냐면1이 앞에 오는 배열은 2개 즉 (3-1)! 개 이다. 처음엔 이게 맞는가 했는데 직접 해보니 맞다.그렇다면 우리가 구해야하는건 5번째, (k-1)/(n-1)! 해주면 해당 index가 나온다.index에 맞는 숫자를 꺼내 answer에 추가한다.그 뒤 숫자배열은 또 (n-1)!이 된다. 즉 n이 0이 될때까지 반복.k는 매번..

이번 문제는 각 노드의 관계가 주어지고, 1번 마을로부터 각 마을까지의 최소거리를 구하여 원하는 결과를 도출한다는 점에서 다익스트라 또는 플로이드 워셜을 생각했다.다익스트라와 힙구조를 사용하였다.거리를 담을 dist 리스트를 생성해주고, 값은 inf로 초기화 했다.(최소거리를 구하기 때문)관계를 담을 graph 리스트를 생성하였다. graph에 담기는 순서는 [ 노드, 배달시간 ] 순서이다.다익스트라 알고리즘을 작성하는데,heap 을 생성하고 그 안에 시작 값을 담았다. [ 1, 0 ] 이후 반복문을 통해 heap이 빌때까지, 각 노드의 관계와 시간을 꺼내면서 시간을 비교하여 작은것을 담는 동시에 경유할때 발생하는 시간 또한 포함하였다. dist에 값을 계속해서 변경하였고, 이후 다시 heap에 담고 이..

문장에서 각 문자의 첫글자를 대문자로 바꾸고 나머지는 소문자. 단, 숫자가 있다면 모두 소문자.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의 경우를 찾는 절차..