반응형 알고리즘/SW역량테스트10 (3장-1) DFS(깊이 우선탐색) 알고리즘이란? 안녕하세요. 지칸입니다. 오늘 설명할 알고리즘은 DFS입니다. 삼성 SW역량테스트에서 자주 사용되는 알고리즘 중 하나입니다. (주로 2차원 좌표상에서의 문제에 사용) 1) DFS란? 2) 구현하기 1) DFS란? 이전 편에서 그래프라는 개념에 대해 공부하였습니다. mydirectorystory.tistory.com/13 그래프 개념과 탐색방법 안녕하세요. 지칸입니다. 삼성전자 역량 테스트에 자주 등장하는 DFS/BFS 알고리즘에 앞서 그래프의 개념에 대해서 살펴보겠습니다. 1) 그래프의 개념 정점과 정점들 간의 관계를 묘사하여 임의의 mydirectorystory.tistory.com 이 그래프를 탐색하는 방식에 따라 DFS/BFS 알고리즘이 구분되고 있습니다. 그래프 탐색은 시작점에서 모든 정점을 차례.. 2021. 3. 8. 그래프 개념과 탐색방법 안녕하세요. 지칸입니다. 삼성전자 역량 테스트에 자주 등장하는 DFS/BFS 알고리즘에 앞서 그래프의 개념에 대해서 살펴보겠습니다. 1) 그래프의 개념 정점과 정점들 간의 관계를 묘사하여 임의의 한 정점에서 다른 정점으로 이동이 가능한지 등의 문제가 그래프 문제입니다. 다양한 문제들에 그래프 개념이 사용되는데 흔히 2차원 좌표에서의 문제에 많이 사용됩니다. - 특정 지점 A,B 사이의 최소 거리 이동 - 벽이 존재하는 미로에서 길찾기 좌표 한칸을 정점으로 보고 정점끼리의 간선이 존재하는지 문제에서 파악하여 그래프로 표현할 수 있습니다. 위 예시처럼 정점과 간선으로 문제를 그래프화하여 표현이 가능합니다. 2) 그래프의 요소 V : 정점 E : 간선, 두 정점을 연결하는 선 무방향 그래프 : 두 정점 사이에.. 2021. 3. 4. (2장-2) 역량 테스트 출제 유형 안녕하세요. 지칸입니다. 2장-2에서는 나머지 유형에 대해 간단히 살펴보겠습니다. 마찬가지로, 문제 분석 과정에서 어떤 알고리즘을 써야겠다고 생각이 든다면 기계적으로 외웠던 템플릿을 먼저 작성합니다. 2-1) DFS, BFS 유형 2-2) 경우의 수, 순열, 조합 유형 2-3) 시뮬레이션 유형 2-4)1~3 혼합 유형 2-2) 경우의 수, 순열, 조합 유형 수많은 선택지 중 어떤 선택을 할 때 최적의 값이 무엇인지 등의 문제로 출제되는 유형입니다. 각 알고리즘에 대한 설명은 추후 설명하도록 하겠습니다. 자주 사용하는 코드를 보여드리겠습니다. 그림1은 순열 코드입니다. 벡터를 사용하여 구현하였습니다. 저는 STL를 적극적으로 사용하는 편인데 수많은 기능을 사용할 수 있어 구현시간을 에러없이 단축시킬 수 있.. 2021. 2. 7. (2장-1) 역량 테스트 출제 유형 안녕하세요. 지칸입니다. 2장에서는 자주 출제되는 유형에 대해 간단히 살펴보겠습니다. 1장에서 처럼 기본적으로 자주 사용하는 템플릿이 있고 문제에서 요구하는 사항을 반영하여 약간의 수정이 필요합니다. 문제 분석 과정에서 어떤 알고리즘을 써야겠다고 생각이 든다면 기계적으로 외웠던 템플릿을 먼저 작성합니다. 2-1) DFS, BFS 유형 2-2) 경우의 수, 순열, 조합 유형 2-3) 시뮬레이션 유형 2-4)1~3 혼합 유형 2-1) DFS, BFS 유형 그래프 탐색으로쓰이는 DFS, BFS는 자주 출제되는 유형입니다. 각 알고리즘에 대한 설명은 추후 설명하도록 하겠습니다. 자주 사용하는 코드를 보여드리겠습니다. 그림1은 DFS 코드입니다. DFS는 재귀함수로 구현하는 경우가 대부분인데 저는 stack를 사.. 2019. 4. 26. 이전 1 2 3 다음 반응형
