알고리즘/알고리즘 이론 (24) 썸네일형 리스트형 소수 찾기 Goal 소수 찾기 알고리즘에 대해 설명할 수 있다. 상황에 맞게 소수 판별 알고리즘을 사용할 수 있다. 소수찾기 방법 2~n-1 까지 수와 나눠보고 소수 판별 n/2 범위까지 홀수 값으로 소수 판별 제곱수까지 확인해보고 소수 판별 에라토스테네스의 체 1. 2 ~ n-1 까지 수와 나눠보고 소수 판별 구현 코드 bool isPrime(int n) { if (n < 2) return false; for (int i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; } 시간 복잡도 : O(n) 3. n/2 범위까지 홀수 값으로 소수 판별 구현 코드 bool isPrime(int n) { if (n < 2) return false; // .. Kruskal 알고리즘 Goal Kruskal 알고리즘에 대한 이해 Kruskal 알고리즘을 구현할 수 있다. Kruskal 알고리즘이 사용되는 예시를 들 수 있다. 사전 필요 지식 최소 신장 트리 Union-Find 크루스칼 알고리즘(Kruskal's algorithm) 탐욕적인 방법(Greedy Method)을 이용하여 모든 정점을 최소 비용을 갖는 간선으로 연결하는 알고리즘 *탐욕적인 방법 : 결정을 할 때마다 "그 순간에 최적"이라고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것 순간의 최적이라고 생각했던 것들을 모아 최종적인 결과를 도출해 낼 때, 그것이 "궁극적으로 최적"이라는 보장은 없다. 하지만!! 다행히 Kruskal 알고리즘은 궁극적으로도 최적의 해를 구하는 것으로 증명 되었다. Kruskal 알고리.. Union-Find Goal Union-Find에 대한 이해 Union-Find 알고리즘을 구현할 수 있다 Union-Find란? Union-Find란, 서로소 집합(Disjoint-Set)을 표현하는 독특한 자료구조이다. (Union, Find라는 연산을 포함하기 때문에 Union-Find(합집합 찾기)라는 이름이 붙었다) *Disjoint Set : 서로소 집합을 다루는 자료구조 Union-Find의 연산 union-find에는 다음과 같은 연산을 제공한다. make-set(x) : x를 유일한 원소로 하는 새로운 집합을 만든다. => 초기화 union(x, y) : x가 속한 셋과 y가 속한 집합을 합친다 find(x) : x가 속한 집합을 찾는다 (집합을 반환, 또는 집합을 대표하는 대푯값(트리의 루트 등)을 반환).. 그래프 순회(Graph Traversal) - BFS , DFS Goal 그래프 순회(탐색)에 대한 이해 BFS, DFS에 대한 이해 BFS, DFS를 구현할 수 있다 그래프 순회(Graph Traversal/Search) 그래프에의 임의의 한 정점에서 시작하여 모든 정점들을 한 번씩 방문하는 작업 보통 그래프 순회, 그래프 탐색을 동일한 의미로 사용하므로 편의상 그래프 탐색이라 칭하겠다. (단어 의미를 엄밀히 따지자면 그래프 순회가 좀 더 정확한 표현이다) (참고) 더보기 Search vs Traversal 순회(Traversal)와 탐색(Search)이 동일한 의미로 사용 되기도 하는데, 굳이 구분하자면 다음과 같다. 탐색(Search) : index나 해싱 등의 방법으로 원하는 데이터를 빠르게 찾는 방법 순회(Traversal) : 특정 순회 알고리즘을 사용하여.. 반복과 재귀 Goal 순환과 반복을 적절하게 사용할 수 있다. 프로그래밍 언어에서 어떤 일을 반복적으로 수행하는 방법으로 반복(iteration)과 재귀(recursion)가 있다. 반복과 순환, 두 가지의 방법에 대해서 알아보자 반복(iteration) for, while 등의 반복 구문을 이용해서 특정 구문을 반복하는 방법 [반복 구현 코드] int factorial(int n) { int result = 1; for (int i = n; i > 0; i--) { result = result * i; } return result; } 재귀(recursion) 함수가 자기 자신을 호출하는 반복 방법 [재귀 구현 코드] int factorial(int n) { if (n == 1) return 1; else retu.. 코딩 테스트 입문 (with C++) 백준 온라인 저지(BOJ)를 통한 코딩 테스트 이해 하기 BOJ 동작 원리 : https://www.acmicpc.net/blog/view/55 BOJ 채점 결과 : https://www.acmicpc.net/board/view/23037 BOJ 채점 결과 FQA : www.acmicpc.net/board/view/4206 어떤 코딩 테스트 사이트를 이용하는지에 따라 조금씩 차이가 있겠지만, 대부분은 위 내용과 비슷합니다. 코딩 테스트를 위한 C++ 입출력 이해하기 입출력 방식에 따라 성능의 차이가 발생하기 채점 결과가 달라질 수 있습니다. => 코딩 테스트를 위해서 입출력에 대한 이해를 할 필요 저는 C++ 언어를 사용할 것이기 때문에 C++에서 코딩 테스트를 위한 입출력 방식에 대해 말씀 드리겠습니다.. 알고리즘 문제 풀이를 위한 C++ 개발 환경 개발 환경 세팅이 필요한 이유 : 프로그래밍 언어별, 버전별로 컴파일 환경이 달라진다. 다음은 백준 온라인 저지에서 C++ 소스 코드를 C++ 14로 컴파일 하는 정보입니다. 일반적으로 다음과 같은 절차로 알고리즘 문제 풀이 결과를 확인합니다. 프로그래밍 언어 선택 후 알고리즘 문제 풀이 채점 사이트에서 프로그래밍 언어와 버전 선택 후 소스 코드 제출 서버에서 채점 진행 (컴파일 되는지 검사, 제한 조건 검사, 출력 결과가 정상적인지 검사) 결과 확인 소스 코드를 제출하면 해당 컴파일러 환경에 맞게 서버에서 소스 코드를 컴파일해줍니다. 그렇기 때문에 최대한 비슷한 환경에서 코드를 작성하는 것이 좋습니다. 만약 다른 개발 환경에서 작성한 코드를 제출하면 정상동작 하지 않을 수 있습니다. ex) msvc 컴.. 알고리즘 Orientation Goal 알고리즘이란? 알고리즘 성능과 복잡도에 대한 이해 시간 복잡도와 Big-O 표기법에 대한 이해 알고리즘 어떤 문제를 해결하기 위한 일련의 절차나 방법을 표현한 것 알고리즘 성능 분석 일반적으로 효율적인 알고리즘이라고 하면 실행 시간이 짧고 컴퓨터 자원을 적게 사용하는 알고리즘이다. => 알고리즘 성능 측면에서 일반적으로 시간과 자원사용을 중요시하기 때문 복잡도(Complexity) 알고리즘을 직접 구현하지 않고 대략적인 효율성을 분석하는데 사용하는 방법 종류 - 시간 복잡도(Time Complexity) - 공간 복잡도(Space Complexity) 복잡도 표현 방법 : 주로 점근적 표기법(Asymtotic Notation)을 사용 (주로 Big-O Notation이 사용됨) => 가장 좋은 .. 이전 1 2 3 다음
