Algorithm/Study24 문제해결 전략 - 27. 그래프 표현과 정의 그래프 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현 여러 도시들을 연결하는 도로망 사람들 간의 지인 관계 웹사이트 간의 링크 관계 트리에 있던 부모 자식 관계에 관한 제약이 없기 떄문에 트리보다 훨씬 다양한 구조를 표현할 수 있다. 그래프의 정의 그래프 G(V,E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조 그래프의 종류 방향 그래프(directed graph) : 각 간선이 방향이라는 새로운 속성을 가짐 무향 그래프(undirected graph) 가중치 그래프(weighted graph) : 각 간선에 가중치(weight)라고 불리는 실수 속성을 부여함 다중 그래프(multigraph) : 두 정점 사이.. 2020. 5. 7. 문제해결 전략 - 15. 계산기하 정리 계산기하 알고리즘 점, 선, 다각형과 원 등 기하학 적 도형을 다루는 알고리즘 학부 선형 대수나 고등학교 수준의 기하학을 코드로 구현할 수 있는 능력 기초적인 수학 이론을 어떻게 간결하고 예외가 적은 형태로 구현하는지에 초점 계산기하 도구들 벡터의 구현 2차원 평면의 서로 다른 두 점의 상대적 위치 벡터는 방향과 거리의 쌍이므로 시작점이 중요하지 않다. 벡터의 시작점은 항상 좌표공간의 원점으로 둔다 벡터를 화살표 끝점의 위치 (x,y)로 표현할 수 있다. const double PI = 2.0 * acos(0.0); struct vector { double x, y; explicit vector(2double x_ = 0 double y_ =0) 등등 여러 operator x 좌표가 작은 벡터일수록, 끝.. 2020. 4. 29. 알고리즘 문제 접근 및 최적화 방법 알고리즘 문제 접근 순서 듣기 : 문제 설명과 관련된 것이라면 어떤 정보든지 집중해서 듣는다. 최적 알고리즘을 설계하기 위해선 모든 정보가 필요하다. 예제 : 대부분의 예제들은 크기가 아주 작거나 특별한 사계인 경우가 많다. 직접 예제를 만들어서 디버깅하자. 직접 만든 예제가 특별한 경우인지 충분히 큰 입력인지 고려한다. 무식하게 풀기 : 무식한 방법으로 풀어보자. 알고리즘의 효율을 생각하지 말고 단순한 알고리즘과 시간 복잡도를 먼저 생각한 다음 최적화를 시도한다. (아직 코딩 금지) 최적화 : 무식한 방법을 개선해 나간다. 문제에서 언급된 정보를 모두 사용했는가? 예제를 손으로 풀어본뒤 어떻게 풀었는지 과정을 다시 생각해본다. '잘못된'방법으로 풀어본뒤 왜 알고리즘이 틀렸는지 생각해 본다. 시간과 공간.. 2020. 3. 26. 이전 1 2 다음
