Algorithm 썸네일형 리스트형 프로그래머스) 길 찾기 게임 Lv3 C++ 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/42892 문제 정리 전위 & 후위 순회 결과 반환하기 방문지점들로 이진트리 만들기 방문지점들은 x, y 정수좌표 / 모든 지점의 x축은 서로 다 다름 / 같은 레벨인 지점의 y 좌표는 동일 / 자식노드의 y값은 항상 부모의 y보다 작음 / left subtree의 모든 x값은 해당 서브트리의 루트의 x값보다 모두 작음/ right에 대해선 모두 큼 한 팀은 전위 순회 & 다른 팀은 후위 순회 구현 순서1. 모든 정점들의 좌표가 담긴 nodeinfo 배열에 인덱스(노드번호)를 추가한다 이 때, 해당 배열의.. 더보기 WILDCARD (DP) https://www.algospot.com/judge/problem/submit/WILDCARD #include #include #include #include using namespace std;// Match 함수의 while 종료 조건// 1. pos == wildcard.size() // 와일드카드가 끝에 도달했을 때, 파일명도 끝에 도달했으면 true /파일명은 끝에 도달 못했으면 false// 2. pos == filename.size()// 파일명의 끝에 도달했으면, // 1번을 먼저 처리했기에 filename은 끝이고 wildcard는 끝이 아니기에 무조건 false라고 생각했다. // 하지만, wildcard[pos]가 * 가 아닌 경우에만 false 이다.// // 3. w.. 더보기 삼성 SW역량테스트 대비 PS (C++ 문제 및 풀이 링크 포함) 실버 & 골드 문제들 (#implementation *g) : https://solved.ac/#기출 : https://www.acmicpc.net/workbook/view/1152Silver VSilver IVSilver IIISilver IISilver IGold VGold IVGold IIIGold IIGold I 셀프넘버 Silver Vhttps://www.acmicpc.net/problem/4673https://www.acmicpc.net/source/79323814 연구소 Gold IVhttps://www.acmicpc.net/problem/14502https://www.acmicpc.net/source/82515004-- 그룹단어체커Silver Vhttps://www.acmicp.. 더보기 [ 그리디(Greedy, 탐욕) ] 알고리즘 정리 및 문제 그리디(Greedy, 탐욕) 알고리즘 최적해를 구하는 데에 사용되는 근사적인 방법 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다. 매순간마다 여러 경우 중 하나를 결정해야할 때, 그 순간에 최적의 경우를 선택해 나아가는 방식으로 최적인 해를 구한다. 하지만, 순간마다 하는 선택은 지역적으로는 최적이지만, 최종적(전역적)으로는 최적이라는 보장이 없다. 그렇기에 그리디 알고리즘을 사용하여 최종적으로 최적의 해를 구하려면 지역적으로 최적을 선택한 결과가 최종적으로도 최적일 수 있는 문제여야한다. 그러기 위해선 아래의 2가지 조건을 만족하는 문제여야한다. 그리디 알고리즘 적용 시.. 더보기 [ DP ] 알고리즘 정리 및 문제 DP ( Dynamic Programming, 동적 계획법 ) 하나의 큰 문제를 여러 개의 작은 문제로 나누어 계산하고 그 결과를 저장하여 문제를 해결할 때 똑같은 연산을 반복하지 않도록 하기위해 사용. 특정한 알고리즘이 아닌 하나의 문제해결 패러다임(방법론)DP 사용 이유이전에 방문/탐색/계산한 값을 저장하여 동일한 문제들을 반복하여 계산하게 되는 비효율적인 문제를 막을 수 있다. ex ) 피보나치 수열문제에서 재귀로 함수를 구성하면, return f(n) = f(n-1) + f(n-2) 이며위의 사진과 같이 동일 부분을 반복 계산 하게된다. O(2^n) 하지만, DP 방식을 사용하면 앞에서 계산한 값을 다시 반복할 필요가 없기에, O(n)으로 개선할 수 있다. ( 다항식 수준, 문제에 따라 다름 )D.. 더보기 [ 최단 경로 탐색 ] 알고리즘 정리 및 문제 그래프에서 최단 경로를 찾는 문제는 1. unweighted graph에서 가장 짧은 경로를 찾는 문제 or 2. weighted graph에서 간선의 가중치 합이 최소가 되도록 하는 경로를 찾는 문제 2-a ) 양수 가중치 2-b ) 음수 가중치최단 경로 문제 분류a. 단일 출발(Single-Source) 최단 경로 : 단일 정점 v ➔ 나머지 모든 정점으로 도착하는 최단 경로 // 1 to All b. 단일 도착(Single-Destination) 최단 경로 : 모든 정점 ➔ 단일 정점 v 로 도착하는 최단 경로 // All to 1 ( 뒤집어 생각하면 단일-출발 최단 경로 문제 ) c. 단일 쌍(Single-Pair) 최단 경로 : 단일 정.. 더보기 [ A* ] 알고리즘 개념 > 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 다익스트라와 유사하나, 최상의 경로를 추정하는 순위값은 heuristric 추정값 h(n)을 현재값 g(n)에 더한 값으로 탐색한다.( h(n) 값이 0이면, 다익스트라 ) " 휴리스틱 비용 * heuristric : 경험적f(n) = g(n) + h(n)- g(n) : 출발노드로부터 특정노드 n 까지의 경로 가중치 // start -> node 현재까지의 값- h(n) : 휴리스틱 힘수 특정노드 n으로부터 목표노드까지의 추정 경로 가중치 // node -> goal 앞으로 예상되는 값 현재 상태와 목표 상태를 상호 비교 h(n).. 더보기 [백준] 전화번호 목록 5052번 C++ https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; // https://www.acmicpc.net/problem/5052 전화번호 목록 struct Trie { bool isEnd; unordered_map child; Trie() { isEnd = false; } .. 더보기 이전 1 2 3 다음
