알고리즘
-
[DFS] 인접 행렬, 인접 리스트알고리즘 2023. 4. 19. 13:29
세가지 그래프 방향 그래프 무방향 그래프 가중치 그래프 인접 행렬 문제 유형 1) 방향그래프가 주어지고 1번에서 N번으로 가는 모든 경로의 가지 수를 구하시오. 필요 자료구조 - 중복 탐색을 방지하기 위한 check 배열, check 배열은 n+1 크기를 갖는다(1 ~ n) - 간선 설정을 위한 graph 2차원 배열(행, 열 모두 n+1 크기) - n개의 정점과, m개의 간선 수 설정 - 문제를 해결하기 위한 DFS 메서드 구현 로직 핵심 로직 public void DFS(int val){ if(val = n) answer++; else{ for(int i = 1; i
-
[알고리즘] BFS(Breadth - First Search), 송아지 찾기알고리즘 2023. 4. 13. 15:31
BFS(Breadth-First Search) 알고리즘은 그래프 탐색을 위한 대표적인 알고리즘 중 하나이다. 그래프를 탐색하면서 같은 레벨에 있는 노드를 모두 방문한 후 다음 레벨로 이동하여 탐색하는 방법을 사용한다. 이 알고리즘은 그래프에서 최단 경로를 찾는 문제를 푸는 데 활용된다. BFS 알고리즘은 다음과 같이 동작한다. 시작 노드를 큐(queue)에 추가. 큐에서 노드를 하나 꺼내어 방문. 해당 노드와 인접한 노드들 중 방문하지 않은 노드를 모두 큐에 추가. 큐가 빌 때까지 2-3 단계를 반복. 이 알고리즘을 구현할 때는 큐를 사용하여 노드를 관리하며, 방문한 노드를 표시하기 위한 visited 배열을 사용. BFS 알고리즘의 시간 복잡도는 노드의 수를 V, 간선의 수를 E라고 할 때 O(V+E)..
-
[자료구조] Queue알고리즘 2023. 4. 12. 21:21
자바(Java)에서 Queue는 데이터를 순서대로 관리하기 위한 자료구조 중 하나이다. 이 자료구조는 선입선출(FIFO, First-In-First-Out)의 원칙을 따르며, 데이터가 들어온 순서대로 처리된다. Java에서 Queue는 java.util 패키지에 속해 있으며, 다양한 구현체를 제공한다. 대표적인 Queue 구현체로는 LinkedList, ArrayDeque, PriorityQueue 등이 있다. LinkedList는 연결 리스트를 기반으로 한 Queue 구현체이다. 요소를 추가하거나 삭제할 때마다 리스트의 노드를 생성하거나 제거하기 때문에 처리 속도가 느리지만, 요소를 삽입하거나 삭제하는 작업에는 빠르게 대응할 수 있다. ArrayDeque는 배열을 기반으로 한 Queue 구현체이다. Q..
-
[프로그래머스][기지국설치]알고리즘 2023. 2. 9. 22:42
문제 설명 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다. 예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.) 더 자세한 문제 설명은 프로..
-
[프로그래머스][스티커모으기(2)]알고리즘 2023. 2. 9. 22:41
문제 설명 N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다. 예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다. 나의 풀이(실패) package pr..
-
[프로그래머스][숫자 게임]알고리즘 2023. 2. 8. 19:58
문제 설명 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다. 각 사원은 딱 한 번씩 경기를 합니다. 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다. 만약 숫자가 같다면 누구도 승점을 얻지 않습니다. 전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 ..
-
[DFS][부분집합]알고리즘 2023. 2. 5. 14:00
public class Subset { static int n; static int[] ch; public void DFS(int L) { if(L == n+1){ String tmp = ""; for(int i = 1; i 0) System.out.println(tmp); }else{ ch[L] = 1; DFS(L+1); ch[L] = 0; DFS(L+1); } } public static void main(String[] args) { Subset T = new Subset(); n = 3; ch = new int[n+1]; T.DFS(1); } } 코드에 대한 설명을 영상으로 남겨놨습니다. [https://www.notion.so/d45e6af251f740ae91e0fe4e497a59f8]
-
[DFS][스택프레임][재귀함수]알고리즘 2023. 2. 3. 13:46
스택 프레임은 매개변수, 지역변수, 복귀 주소를 갖고 있다. 스택 프레임은 백트래킹이라는 알고리즘을 사용할 수 있다. 위 코드는 9번 라인에서 함수 호출로 인해 스택프레임에 DFS(n-1) 함수가 저장되어 있다가 if(n==0) 조건으로 인해 DFS() 함수가 return 되면서 위에서부터 차례대로 9~12번 까지 로직을 실행하게 되면서 1 2 3 이라는 값을 출력하게 된다. 위 코드는 전 그림과 다르게 DFS(n-1) 함수가 출력 코드 위에 아래에 선언되어 있게되면서 3 2 1이라는 결과를 출력한다.