컴퓨터/알고리즘24 Sort에 사용하는 Compare 커스텀 + priority_queue 비교연산자 차이 주로 vector를 정렬할 때 sort를 사용하는데 vector 가 아니라 vector vector 같은 것을 사용하게 되는 경우 기본 오름차수 sort가 의도하는 대로 작동이 안되거나 그냥 작동이 안되기 때문에 커스텀으로 compare함수나 오브젝트를 만들어서 sort(v.begin(), v.end(), compare)로 사용할 필요가 있습니다. https://www.cplusplus.com/reference/algorithm/sort/ sort - C++ Reference custom (2)template void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); www.cplusplus.com 레퍼런스를 참고해보면.. 2021. 11. 9. 깃허브를 이용한 알고리즘 스터디 하는법 Github에 잔디심기가 은근히 신경쓰일 때도 있습니다. 그럴 때는 알고리즘 스터디를 할 때 깃허브를 이용하면서 잔디도 심을겸 알고리즘 공부도 할 수 있습니다! 깃허브를 이용한 알고리즘 그룹스터디 하는 법 직접 깃허브 레파지토리를 만드셔도 됩니다!! 제가 이용하고 있는 스터디 기준으로 소개하겠습니다. https://github.com/ellynhan/Challenge100_Code_Test_Study GitHub - ellynhan/Challenge100_Code_Test_Study: 알고리즘 코딩테스트 문제풀이 스터디 - 100문제를 목표로🔥 알고리즘 코딩테스트 문제풀이 스터디 - 100문제를 목표로🔥. Contribute to ellynhan/Challenge100_Code_Test_Study dev.. 2021. 10. 24. [c++] 이중 벡터 초기화 선언하고 사용하기 벡터를 선언하고 초기화해서 바로 사용할 때 vector v(number,value); ㅤ 이렇게 쓰면 number개 개수의 공간만큼에 value값을 넣고 초기화를 하는 것이다. 예를 들면 vector v(4,100)이면 v에는 {100,100,100,100}이 들어간채로 초기화된다. 그렇다면 이중 벡터는 어떻게 초기화 할 수 있을까 생각을 해봤다. (사실 헷갈려서 정리함) ㅤ vector vv(number,value); ㅤ 를 하려면 n은 똑같이 만들고싶은 vector 개수만큼 적으면 되고 v에는 vector의 값을 넣어줘야한다. 근데 int값은 vector와 다르니까 vector의 초기화된 형태를 넣어주면 된다. 위에서 말한 것 처럼 vector의 초기화를 하면 된다. 예를 들면 ㅤ vector vv(.. 2021. 9. 12. 알고리즘(코테) 스터디 [포도농사] 파일 공유 및 사용법 목차 1. 파일 공유 2. 구글 드라이브 이용 스터디 세팅 법 지난 게시글에서 알고리즘(코테) 공부법을 소개해 드렸습니다. 이번에는 지난 게시글에서 소개해드린 포도농사 스터디법에 사용된 양식을 공유하고자 합니다. 아래는 엑셀 파일입니다. 이 파일을 가지고 혼자 공부하셔도 좋지만!! 스터디를 하시는 경우 공유가 필요합니다. 이 때 구글 드라이브 공유 문서를 이용합니다!! 1. 구글 드라이브 들어가기 2. 새로 만들기 > 스프레드 시트 > 빈 스프레드 시트 3. 파일 > 열기 > 업로드 새로 생성된 빈 스프레드 시트에서 파일 > 열기를 누르면 파일열기 창이 뜨는데 거기에서 업로드 탭을 누른 후 다운받은 포도농사 엑셀파일 (알고리즘 공부 엑셀파일) 을 선택합니다. 그러면 다음과 같이 업로드가 됩니다!! 4. .. 2021. 8. 26. 알고리즘 공부, 코테 스터디 하는 법 공유!! - 알고리즘 문제 풀이 순서, 공부 방법 (1) - 비전공자/문제풀이 처음: https://waytocse.tistory.com/114 - 알고리즘 문제 풀이 순서, 공부 방법 (2) - 전공자/문제풀이 초보: https://waytocse.tistory.com/115 아래에서 다루는 것은 위에 다루는 내용도 일부 포함되어있고 다른점은 3번!입니다 :) 목차 1. 알고리즘 공부 사이트 2. 알고리즘 공부 시작 하는 법 3. 코테 공부 / 스터디 하는 법 공유 1. 알고리즘 공부 사이트 보통 알고리즘을 공부할 때 백준(https://www.acmicpc.net/), 프로그래머스(https://programmers.co.kr/)를 많이 이용합니다. 삼성 역량테스트에 관심있는 분들은 SW Expert Acad.. 2021. 8. 26. 0-1 knapsack problem 가방에 최대 무게가 있고 그 무게 안에 물건을 넣는데 물건의 가치가 최대로 넣는 경우를 구하는 문제. Brute force로 문제를 풀면 모든 가능한 부분집합의 경우를 비교해보면 되므로 2의 n번을 비교해보게 된다. 예를 들어 보석1, 2, 3, 4 가 있고 각각의 무게와 가치가 있을 때 0부터 최대 가방무게 n까지 열의 속성으로 두고 0부터 최대 보석 가지수를 4개까지 행이 속성으로 두어서 보석 가지 수⑊가방 무게 0 1 2 .. n 0 0 0 0 0 1 0 2 0 3 0 4 0 이런 식으로 테이블이 만들어진다 생각하고 이해해보면 쉽다. 처음에 이 문제를 이해하려고 했을 때 많이 애를 먹었던 부분이 왜 보석을 여러개를 안넣고 1개만 넣는거지??였다. 예를들어 보석1의 무게가 1이면 가방 무게가 2이므로.. 2021. 6. 9. 다익스트라 알고리즘 Dijkstra's algorithm 일정 시간 복잡도 다익스트라 알고리즘은 시작 정점이 정해져있다. 정점을 선택해가며 진행하고 각 정점까지 총 가중치를 합한 값을 저장하고 비교해 나간다. 앞서 살펴본 프림 알고리즘의 일정 시간 복잡도와 유사하다. T(n) = 2(n-1)(n-1)로 모든 정점을 방문하기 위해서는 시작 정점을 제외하고 n-1개의 정점을 방문해야한다. 그러므로 repeat n-1번을 해준다 (가장 바깥쪽 반복문) 이 repeat내부에서는 각 정점까지 현재 진행상태에서의 최단거리를 비교하고 (n-1번) 이동할 정점을 고른 후에는 다시 각 정점까지의 거리를 업데이트한다 (n-1번) 그렇기 때문에 (n-1 + n-1)(n-1) = 2(n-1)(n-1)이 되는 것이다. 의사 코드를 보면 다음과 같다. void dijkstra(int n, const n.. 2021. 6. 9. 프림 알고리즘 증명 Prim's Algorithm Proof 그리디 알고리즘은 매 순간 최적의 결과만 추구하기 때문에 최종적으로 얻게 되는 결과가 최적의 결과인지는 알 수 없다. 그렇기 때문에 그리디 알고리즘은 최적의 결과인지 판단하는 것이 필요하다. 프림 알고리즘 역시 그리디 알고리즘에 속한다. 그러므로 프림 알고리즘을 통해서 얻는 결과가 최적 결과인지 확신할 수 없다. 그런데 프림 알고리즘 결과는 항상 최적의 결과라고한다. 이를 증명하는 법을 알아보자. G는 가중치가 있고 방향성이 없는 그래프이다. 이는 전체 정점 V와 전체 간선 E로 이루어져있다. F는 방문한 간선이다. F는 E에 속한다. Y는 V에 속하면서 간선 F를 통해 방문 했던 정점들이다. 그래서 G = (V,E) 이고 F ⊆ E, Y ⊆ V, F는 promising하다고 해보자. 이 때 promis.. 2021. 6. 8. 프림 알고리즘 Prim's Algorithm 일정 시간 복잡도 MST(minimum spanning tree)구하는 알고리즘 정점 선택 기반으로 가중치 제일 낮은 방향으로 이전 단계의 신장트리를 확장해나간다. 트리가 N-1개의 간선을 가질 때까지 반복한다. 의사 코드를 보면 다음과 같다. void prim(int n, const numberW[][], set_of_edges& F) //정점 개수, 간선 정보, 방문 간선 { index i, vnear; number min; edge e; index nearest[2..n]; //해당 인덱스의 정점에서 가장 가까운 정점 정보 number distance[2..n]; //현재 방문한 정점에서 해당 인덱스의 정점까지 거리(최단) F = ∅; for(i = 2; i 2021. 6. 8. [알고리즘] Hash 해쉬 알고리즘이라기보다 검색하면 자료구조라고 더 많이 나온다. Key -> Hash Function -> Hash -> Value -> Bucket(Slot) 으로 진행된다. Key: 입력 값. 무한할 수 있다. Hash Function: Key로 부터 Hash값을 반환하는 함수. 사용자 임의로 설정 Hash : 해쉬값을 통해서 value값과 매칭시켜 Bucket(Slot)에 저장한다. (유한) Value: 저장 값 Bucket(Slot): Value 저장소. vector / map / list / queue등을 이용한다. hash_map이라는 라이브러리가 있지만 표준은 아니기 때문에 C++ STL(자료구조) 공부할 때 목차에 없다. 예를 들면, Hash Function이 key%10 이라면 hash로 나올 .. 2020. 3. 25. [알고리즘] 퀵 정렬 | Quick Sort | C++코드 해석 병합정렬(Merge Sort)과 함께 기본 정렬알고리즘인 퀵정렬. 병합정렬이 수열을 반으로 쪼개가며 정렬했다면, 퀵정렬은 기준을 두고 기준보다 작은값들, 기준보다 큰값들로 쪼개가며 정렬한다. 병합정렬은 따로 정렬해둔 값을 저장해둘 메모리공간이 필요했다면 퀵정렬은 따로 메모리공간이 필요하지 않다. 하지만 병합정렬은 언제나 시간복잡도가 일정한 반면 퀵정렬은 잡히는 기준에 따라 시간복잡도가 O(n^2)까지 올라갈수있다고한다. 코드는 이러하다. pivot이 기준 값이 되고 i가 pivot의 자리를 찾아준 다고 생각하면된다. 이해하기 쉽게 예시를들어 그림으로 설명해보자면 이런식이다. 2020. 2. 20. [알고리즘] 병합정렬 알고리즘 | Merge Sort | C++코드 해석 분할정복(Divide and Conquer) 알고리즘을 공부하고있습니다. 병합정렬을 이해해보겠습니다, 우선은 코드는 이렇게 생겼습니다 코드를 이해하기 쉽도록 병합정렬의 개념과 예시그림을 설명하겠습니다! 병합정렬은 분할과 정렬로 나눌수있습니다. 먼저 처음과 끝의 중간에서 두 개로 분할합니다. 이후 분할된 블록들을 계속해서 최소단위까지 분할해줍니다. 8개의 수열을 분할하는 과정을 예로 들면, 이런 식이 됩니다. 코드를 보면 이에 재귀함수를 이용하였는데요, 빨간색 숫자는 재귀함수에 따라 분할이 되는 순서입니다. 재귀함수가 머리아프신분들은 저 순서를 보시면 직관적으로 바로 이해가 되실 거에요! 분할이 끝났으면 5번에서 정렬&병합 한번, 8번에서 한번, 8번 병합이끝나고 6번에 돌아와서 한번, 6번에서 끝나고 2.. 2020. 2. 20. 이전 1 2 다음
