본문 바로가기
반응형

알고리즘9

[BOJ-9466] 텀 프로젝트(JAVA) 백준 9466 텀 프로젝트 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 설명 - 프로젝트 팀을 구하기 위해서 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단 한 명만 선택할 수 있고, 자기 자신도 선택할 수 있다.) - 학생들이(S1, S2, S3, ... , Sr) 이라 할 떄 S1이 S1을 선택하는 경우나, S1이 S2를, S2가 S3를, .., Sr-1이 S1을 선택하는 경우 한 팀이 될 수 있다. - 예를 들어 아래와 같이 학생들이 선택을 했다고 가정해보자. - 위 결과를 통해 .. 2021. 10. 13.
[BOJ-2118] 두 개의 탑(JAVA) 백준 2118 두 개의 탑 2118번: 두 개의 탑 첫째 줄에 지점의 개수 N(2≤N≤50,000)이 주어진다. 다음 N개의 줄에는 차례로 두 지점 사이의 거리가 정수로 주어진다. 전체 거리의 총 합은 1,000,000,000을 넘지 않는다. www.acmicpc.net 문제 설명 - 1번부터 N번까지의 지점이 있다. - 각 지점들은 차례로, 그리고 원형으로 연결되어 있다. - 이 지점들 중 두 곳에 두 개의 탑을 세우려 한다. 이때 두 탑의 거리가 최대가 되도록 만들어야 한다. - 지점들 사이는 원형으로 연결되어 있기 때문에, 두 지점 사이에는 시계방향과 반시계방향의 두 경로가 존재한다. - 두 지점 사이의 거리를 잴 때에는, 이러한 값들 중 더 작은 값을 거리로 한다. - 연결되어 있는 두 지점 사이.. 2021. 10. 11.
[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기(C++) 문제 제목 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 문제 설명 - 카카오 초등학교의 "니니즈 친구들"이 "라이언" 선생님과 징검다리를 건너려 한다. - "라이언" 선생님은 징검다리를 무사히 건너기 위해 다음과 같은 규칙을 만들었다. 징검다리는 일렬로 놓여 있고 각 징검다리의 디딤돌에는 모두 숫자가 적혀 있으며 디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어듭니다. 디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없으며 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있습니다. 단, 다음으로 밟을 수 있는 디딤돌이 여러 개인 경우 무조건 가장 가까운 디딤돌로만 건너뛸 수 있습니다. - "니니즈 친구들"은 한 번에 한.. 2020. 12. 5.
탐색 알고리즘 - 너비 우선 탐색(Breadth First Search, BFS) 너비 우선 탐색(Breadth First Search, BFS) 너비 우선 탐색이란? - 임의의 노드에서 인접한 노드를 먼저 모두 탐색하고 다음 단계로 넘어간다. - 순환 알고리즘의 형태 - 그래프 탐색 시 방문 노드를 반드시 검사해야 한다. - 두 노드 사이의 최단 경로, 임의의 경로를 탐색할 때 사용한다. - DFS보다 빠른 탐색 속도를 보인다. - 큐를 이용하여 구현한다. 너비 우선 탐색 방법 - 1. A노드를 먼저 방문하고, 방문한 노드를 표시한다. - 2. A노드와 인접한 노드를 큐에 넣고, 해당 노드들을 차례로 방문한다. - 3. A노드와 인접한 노드를 방문하며 해당 노드와 인접한 노드를 다시 큐에 넣는다. - 4. 위 과정을 반복하며 모든 노드를 방문한다. 너비 우선 탐색 코드(C++) #i.. 2020. 6. 22.
반응형

티스토리툴바