자료구조 & 알고리즘 & cs (88) 썸네일형 리스트형 [python] 1167 - 트리의 지름 1167번: 트리의 지름 (acmicpc.net) 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름이란? 트리의 모든 경로들 중 가장 긴 경로의 길이를 의미한다. 문제 자체는 dfs나 bfs 로 구현하면 되는 문제였는데 트리의 지름을 구하기 위해 필요한 공식이 있었다. 트리의 지름이 u-v라고 할 때, 임의의 점 x에서 가장 먼 노드는 u 또는 v가 된다. 따라서 임의의 노드에서 가장 먼거리에 있는 노드를 찾고 그 노드에서 다시 가장 먼 거리의 노드를 찾으면 트리의 지름을 찾을 수 .. [TIL] 백트래킹 - N-Queen 문제 백트래킹(Backtracking) 제약 조건 만족 문제에서 해를 찾기 위한 전략 해를 찾기 위해 답이 될 수 있는 후보군의 제약 조건을 체크하다가 만족할 수 없는 경우 즉시 backtrack하고 다른 후보군으로 넘어간다. 고려할 수 있는 경우의 수를 상태공간트리(State Space Tree)를 통해 표현한다. DFS 방식으로 확인한다. promising (해당 루트가 조건에 맞는지를 검사하는 기법) pruning(가지치기 : 조건에 맞지 않으면 포기하고 다른 루트로 돌아서서 탐색의 시간을 절약하는 기법) N-Queen 문제 백트래킹의 대표적인 문제 - N*N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치한다. - 퀸은 수직, 수평, 대각선으로 이동 가능하다. ex)N이 4일 경우 다음과 같이.. [TIL] 최단 경로 알고리즘 - 벨만 포드 알고리즘 벨만 포드 알고리즘 최단 경로 알고리즘 중 하나로 가중치가 음수인 경우 적용 가능하다. 다익스트라보다 시간복잡도가 느리다. 음수 사이클 존재의 여부를 파악할 수 있다. 관련문제 11657번: 타임머신 (acmicpc.net) 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 처음 문제를 접근 할 때 벨만 포드 알고리즘을 몰랐기 때문에 다익스트라 알고리즘으로 접근하였다. 3개의 테스트 케이스를 분석한 뒤에 나름대로(?) 가중치가 음수인 경우를 따로 분리하.. [TIL] - 유클리드 호제 - 최소공배수와 최대공약수 유클리드 호제 (Euclidean algorithm) - 2개의 자연수 혹은 정식의 최대공약수(gcd)를 구하는 알고리즘의 하나이다. - 2개의 자연수 a,b에 대하여 r을 a%b (a>b) 라고 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다. - 결론적으로 b%r 인 r'를 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대 공약수가 된다. - 최소공배수는 두 자연수 (a*b)/gcd(a,b) 이다. 관련 문제 코딩테스트 연습 - N개의 최소공배수 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기.. [java/python] 프로그래머스 Lv2. - JadenCase 문자열 만들기 코딩테스트 연습 - JadenCase 문자열 만들기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 파이썬으로 코드를 짤 때 처음에는 isupper, islower 등의 함수를 이용하여 짰는데 풀이코드를 참고하던 중 간단한 함수가 있어 기록하려 한다. [python] def solution(s): answer='' s=s.split(" ") for i in range(len(s)): s[i] = s[i].capitalize() answer =' '.join(s) return answer capital.. [TIL] 플로이드-워셜 - Floyd-Warshall 플로이드-워셜 알고리즘(Floyd-warshall) 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘 2차원 테이블에 최단 거리 정보를 저장한다. 다이나믹 프로그래밍 유형에 속한다. 각 단계마다 특정 노드 k를 거쳐 가는 경우를 확인하여 a-b의 최단 거리보다 a-k-b가 짧은지 검사한다. 플로이드-워셜 알고리즘 문제 1956번: 운동 (acmicpc.net) 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net import sys #플로이드 워셜 input .. [java/python] 프로그래머스 Lv2. - 하노이 탑 코딩테스트 연습 - 하노이의 탑 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이전에 백준에서 똑같은 문제를 풀었을 때 잘 이해가 가지 않았는데 이번에 다시 풀어보니 이해가 갔던 문제였다. 재귀함수의 기본인 하노이탑 문제를 정리해보았다. 1. 원반 n개를 가장 오른쪽 기둥으로 모두 옮겨야 한다. 2. 한 번에 하나씩만 옮길 수 있다. 3. 크기가 큰 원반 위에 작은 원반을 올려야 한다. 이 사항들을 지키며 주어진 원반을 옮겨야 한다. 문제에서는 최소로 움직이는 경로를 구해야하는데 재귀함수를 이용하여.. [TIL] 최소 신장 트리(MST) 2 - 프림(prim) 알고리즘 프림 알고리즘(Prim's algorithm) 시작 정점을 선택한 후 정점에 인접한 간선 중 최소 가중치의 간선이 연결된 정점을 선택한다. 선택한 정점에서 위의 과정을 반복하며 최소 신장 트리를 확장해 나간다. 프림 알고리즘 구현 노드의 연결을 확인하기 위한 집합과 연결된 간선들을 관리하기 위한 간선 리스트를 사용한다. 임의의 정점을 선택 후 노드 집합에 삽입한다. 해당 정점에 연결된 간선들을 간선 리스트에 삽입한다. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출한다. -> heapq 사용 만약, 해당 간선에 연결된 정점이 위의 노드 집합에 들어 있다면 다른 간선을 찾는다. (사이클 x) 그렇지 않다면 그 간선을 선택하고 mst를 리스트에 삽입한다. 추출된 간선은 간선 리스트에서 제거한다. 간선 리.. 이전 1 2 3 4 5 6 7 ··· 11 다음
