본문 바로가기
반응형

[IT] 알고리즘4

[JAVA] BFS 기본 코드 (큐 사용) BFS BFS는 Breadth First Search의 줄임말로 너비 우선 탐색입니다. DFS와 같이 기본적인 그래프 알고리즘 중 하나로, 시작 정점에서 연결된 모든 정점을 방문하고, 다시 방문한 하나의 정점을 시작점으로 해서 또 연결된 모든 정점을 방문하는 식으로 구현됩니다. 아래의 예시를 보면, 0부터 시작하여, 0에 연결된 1과 2를 방문하고, 다시 1을 시작점으로 1에 연결된 3과 4를 방문하고, 2로 와서 방문할 점을 찾았는데 더 이상 방문할 점이 없고, 3과 4에서 연결 점을 찾았는데 둘 다 없으므로 종료하는 식으로 동작합니다. JAVA BFS 구현 위의 이미지를 구현해보면 아래와 같습니다. DFS와 동일하게 간선(Node)나 정점(Edge)의 정보는 ArrayList의 배열로 저장을 하였습니.. 2022. 5. 27.
[JAVA] DFS 리스트 + 재귀 기본 코드 DFS DFS는 Depth Frist Search의 줄임말로, 깊이 우선 탐색입니다. 그래프 알고리즘에서 BFS와 함께 기본 알고리즘으로 하나의 정점에서 시작해 연결된 모든 정점을 방문할 때, 깊은 정점을 우선 방문하고 더 이상 방문할 정점이 없을 때, 다시 왔던 정점으로 돌아와서 방문하지 않은 정점을 방문하는 식으로 구현이 됩니다. 아래의 간단한 예시에서 보면, 0 > 1 > 3 을 깊이 우선으로 방문하고 더 이상 방문할 정점이 없으므로, 1로 돌아와 4를 방문하고, 다시 0으로 돌아와 2를 방문하는 식으로 모든 연결된 정점을 방문하고 있습니다. JAVA DFS 구현 위의 이미지를 간단하게 DFS 기본 코드를 구현해보면 아래와 같습니다. ArrayList의 배열과 재귀 함수를 이용하여 구현을 했는데, .. 2022. 5. 20.
[JAVA][프로그래머스] Lv1 신고 결과 받기 (자바 풀이 및 코드) https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr Input id_list : 전체 유저의 ID 배열 ["muzi", "frodo", "apeach", "neo"] report : "신고한유저 신고당한유저"의 배열 ["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"] k : 특정 유저의 신고 횟수가 k보다 같거나 클경우, 그 유저를 신고한.. 2022. 5. 13.
기본 정렬 알고리즘 - 선택정렬, 버블 정렬, 삽입 정렬 안녕하세요, 자바 프로그래밍 알고리즘 첫 포스팅으로 가장 기본이자 알고리즘의 시작이라고 할 수 있는 기본 알고리즘 3종 (선택/버블/삽입 정렬)에 관해서 정리하도록 하겠습니다. 알고리즘 시험이나 코딩 테스트에서는 해당 알고리즘을 그대로 이용해서 구현하는 식의 문제가 나올 가능성은 적겠지만, 기본 정렬 알고리즘을 완벽히 이해하고 구현할 수 있어야 다른 복잡하고 어려운 알고리즘 문제를 이해하고 해결하는데 큰 도움이 될 것입니다. 만약 아래와 같이 정렬이 되지 않은 배열 크기 N이 5인 int 배열이 있고, 해당 배열을 좌측부터 오름차순으로 정렬을 해야 한다고 가정을 하고 선택/버블/삽입 정렬을 이용하여 정렬을 하도록 하겠습니다. { 3, 5, 1, 2, 4 } -> { 1, 2, 3, 4, 5 } 1. 선택.. 2021. 12. 29.
반응형

티스토리툴바