반응형 분류 전체보기71 섹션 6. 그래프(Graph) 그래프의 기본 유니온 파인드 : 그래프의 사이클이 생성되는지 판별되는 알고리즘 위상 정렬 조건 사이클이 없다 방향이 있는 그래프이다. 노드를 정렬해줌, 정렬 결과가 꼭 1개가 아니다. 사용 예시) 수강신청, 롤 아이템 트리등 방향이 있어야 한다. 다익스트라 : 시작점이 있고 다른 모든 노드로 가는 최단거리 알고리즘 단, 음수 간선이 있으면 안된다. 벨만-포드 : 음수 간선이 있어도 괜찮다. 주로 음수 사이클이 있는지 구할때 사용 ex) 시간 여행, 웜홀등 워프 플로이드-워셜 : 시작점이 없는 임의의 모든 노드에서의 최단거리 알고리즘 ex) 모든 도시간의 최단거리를 구하기, 모든 도시를 가는데 최소 시간 최소 신장 트리(MST) : 그래프에서 최소의 가중치 합으로 노드를 연결 할 수 있게 해주는 알고리즘으.. 2023. 3. 31. 섹션 5. 정수론 소수 구하기 소수(prime number)은 1과 자기 자신 외에 약수가 존재하지 않는 수이다. 소수를 구하는 대표적인 판별법은 에라토스테네스의 채가 있다. 구하고자 하는 소수의 범위만큼 1차원 배열 생성 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다. ← 소수 배열의 끝까지 2번 과정을 반복한 후 배열에서 남아 있는 모든 수를 출력한다. 에라토스테네스의 체를 사용하는 경우 시간 복잡도 일반적으로 에라토스테네스의 체를 구현하기 위해 이중 for문을 사용하므로 O(n^2)으로 판단 할 수 있다. 하지만 실제 시간 복잡도는 O(nlog(logn))이다. 배수를 삭제하는 연산으로 실제 구현.. 2023. 3. 30. 섹션 4. 탐욕 알고리즘(Greedy Algorithm) 그리디 알고리즘 그리디(greedy) 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지중 최선의 선택지라고 가졍하는 알고리즘이다. 최적의 해를 보장하지는 않는다. 그리디 알고리즘 수행 과정 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 과정을 반복 ex) 회의실 배정하기 (백준 1931) 문제 분석하기 가장 많이 진행하려면 회의가 겹치치 않게 최대한 많은 회의를 배정 → 그리디 알고리즘 현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는게 유리 종료 시.. 2023. 3. 29. 2023 네오플 상반기 공개채용 시작 2023 네오플 공개채용 기간 : 2023. 03. 27 ~ 2023. 04. 16 프로젝트 소개 제주 던전앤파이터 : 던전앤파이터는 2005년 8월 10일부터 지금까지 긴 시간 동안 많은 모험가님의 사랑을 받아온 2D 액션 RPG 게임입니다. 17개의 개성 있는 클래스를 기반으로, 각 클래스마다 최대 5개의 전직이 존재하여 특색 있는 전투를 즐길 수 있으며, 이런 다양하고 매력이 넘치는 캐릭터들과 함께 방대하게 펼쳐진 세계를 모험해 나갑니다. 매력적인 그래픽과 화려한 일러스트, 컨트롤을 통한 극한의 '액션쾌감'은 던전앤파이터만의 매력으로 자리잡고 있습니다. 프로젝트 오버킬 : Project Overkill은 던전앤파이터의 후속작으로, 원작의 횡스크롤 액션과 세계관을 계승하고, 3D 액션 8방향 전투로 .. 2023. 3. 28. 이전 1 ··· 9 10 11 12 13 14 15 ··· 18 다음 반응형
