일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- MCU 딥러닝
- 자료구조
- dfs
- 컴퓨팅사고
- 포스코 ai 교육
- TensorFlow Lite
- tinyml
- BFS
- 임베디드 딥러닝
- 포스코 AI교육
- 포스코 교육
- 삼성역테
- 삼성코테
- 다이나믹프로그래밍
- 코딩테스트
- 초소형머신러닝
- 그리디
- 알고리즘
- DP
- bfs문제
- 영상처리
- 딥러닝
- 코테 문제
- sort
- dfs문제
- tflite
- 삼성코딩테스트
- DP문제
- 삼성역량테스트
- 코테
- Today
- Total
목록알고리즘 (84)
코딩뚠뚠

풀이일시 : 2020-08-30 DFS : 깊이우선탐색으로 DFS보다 좁고 깊게 탐색해나가며 전체 정점을 탐색하는 방법이다. 주로 stack을 이용한다. 아래그림이 dfs를 한눈에 보여준다고 생각한다 출처 : http://www.aistudy.com/heuristic/depth-first_search.htm 문제 : DFS를 구현하라 풀이 : recursive하게 구현한다. #include #include #define MAX 9 using namespace std; int d[MAX] = { 0, }; //방문체크하는배열 vector a[MAX]; void dfs(int x) { if (d[x] == 1) return; d[x] = true;//방문체크하기 cout
풀이 일시 : 2020-08-29 그리디알고리즘 : 당장 눈앞에의 최적의 상황만 쫓는 알고리즘이다. 대표적인 알고리즘으로는 가장 짧은 간선부터 연결하는 크루스칼 알고리즘이 있다. 문제 : 총 몇개의 동전을 거슬러줘야되는가? => 최소값을 구하라 풀이 : 가장 큰 단위부터 거슬러줄 수 있다면 거슬러 주는 것이 동전을 가장 적게 사용하는 방법일 것이다. #include using namespace std; //총 몇개의 동전을 거슬러 줘야되는가 int main() { int n, result = 0; cin >> n; result += n / 500; n %= 500; //나머지 연산을 해서 다음 레이어로 간다. result += n / 100; n %= 100; result += n / 50; ..
풀이 일시 : 2020-08-22 라빈카프 알고리즘 : 문자열 매칭 알고리즘으로 해시기법을 이용한다. 충돌하는 경우에는 포인터를 이용해 연결자료구조(link)를 이용해 해결한다. 문제 : 라빈카프 알고리즘을 이용하여 "ababacabacaabacaaba" 에서 "abacaaba"의 시작점을 찾아라 풀이 : #include #include using namespace std; void hashs(string parent, string pattern) { int parentHash=0, patternHash=0, power = 1; int parentSize = parent.size(); int patternSize = pattern.size(); for (int i = 0; i
풀이 일시 : 2020-08-21 KMP알고리즘 : Knuth Morris Pratt 알고리즘 / 대표적인 문자열(string)매칭 알고리즘 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘 문제1 : 일반 문자열 매칭 알고리즘 (KMP알고리즘 X) 풀이 : BCDEF가 있고 그 중 DE를 찾을거면 자리를 하나씩 옮기며 비교하면서 매칭한다. O(N*M) #include using namespace std; int findString(string parent, string pattern) { int parentSize = parent.size(); int patternSize = pattern.size(); for (int i = 0; i ABCDABEDFS 에서 ABE를 찾고자..
풀이 일시 : 2020-08-21 이분매칭 : A집단이 B집단을 선택하는 방법에 대한 알고리즘 효과적으로 집단을 매칭해준다. (최대매칭) 문제 : 연결될 수 있는 쌍을 나타내고 그 중 최대 매칭을 계산 후 매칭 된 것을 나타내자 풀이 : DFS로 풀이 가능 dbstndi6316.tistory.com/64?category=953968 [기본문제풀이] DFS 깊이우선탐색 풀이일시 : 2020-08-30 DFS : 깊이우선탐색으로 DFS보다 좁고 깊게 탐색해나가며 전체 정점을 탐색하는 방법이다. 주로 stack을 이용한다. 아래그림이 dfs를 한눈에 보여준다고 생각한다 출처 : http:// dbstndi6316.tistory.com #include #include #define MAX 101 ..
풀이 일시 : 2020-08-17 강한결합요소 : strongly connected component SCC로 부르기도 한다. 같은 SCC에 속하는 두 정점은 서로 도달이 가능하다. 문제 : SCC의 갯수와 각 SCC에 담긴 인자들을 출력하라 풀이 : 모든 정점에 대해 DFS를 수행해서 SCC를 찾는 알고리즘으로 풀이한다. 1->2->3->4 에서 다시 1로 돌아갈 수 있어야 SCC가 성립하는 것. #include #include #include #include #define MAX 10001 using namespace std; int id, d[MAX]; bool finished[MAX]; //특정한 dfs가 끝났는지 확인하기위해 vector a[MAX]; vectorSCC; stack..
풀이 일시 : 2020-08-16 위상정렬 : 순서가 정해져 있는 작업을 차례로 수행해야 할 때 순서를 결정하기 위해 큐 사용 문제 : topology sort 수행 시간복잡도 : O(V+E) 풀이 : #include #include #include #define MAX 10 using namespace std; int n, inDegree[MAX]; vector a[MAX]; void topologySort() { int result[MAX]; queue q; for (int i = 1; i
풀이 일시 : 2020-08-13 플로이드와샬 알고리즘 : 그래프 정점간 최단거리를 구하는 알고리즘 중 모든 최단 경로를 구하는 방법이다. (다익스트라는 한 점에서 다른점까지의 최단 경로) 또한 플로이드와샬에서는 음의 가중치를 가진 간선을 사용할 수 있다. 모든 정점에 대한 경로를 계산하므로 거리를 저장할 자료구조는 2차원 배열이 된다. 문제 : 주어진 인접행렬에서 플로이드 와샬 알고리즘을 사용하여 모든 거리를 구하라 {0 , 5 , inf , 8}, {7 , 0 , 9 , inf}, {2 , inf , 0 , 4}, {inf , inf , 3 , 0} 풀이 : #include int number = 4; int inf = 10000000; int a[4][4] = { {0,5,inf,8}, {7..