'알고리즘' 카테고리의 글 목록 (4 Page)

[SWEA] 2814 최장경로 - Java

2023.11.15

최장경로 구하기 ➔ DFS https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&problemLevel=3&problemLevel=4&contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=JAVA&select-1=4&pageSize=10&pageIndex=3 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📍 고려해야할 점 최단경로가 아닌 최장경로를 구해야..

알고리즘/SWEA

[SWEA] 1954 달팽이 숫자 - Java

2023.11.13

삼성 기출에 종종 나온 적이 있는 구현 문제. (0, 0)에서 시작 https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&problemLevel=3&problemLevel=4&contestProbId=AV5PobmqAPoDFAUq&categoryId=AV5PobmqAPoDFAUq&categoryType=CODE&problemTitle=&orderBy=SUBMIT_COUNT&selectCodeLang=JAVA&select-1=4&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📍 고려해..

알고리즘/BOJ

[BOJ] 4179 불! - Java

2023.10.25

✨ BFS ➔ 동시에 이동시키기 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 📍 고려해야할 점 불과 지훈이를 동시에 이동시켜야한다. 동시에 이동시키기 위해서 두 개의 큐를 사용한다. 불은 지훈이의 존재 여부에 대해 영향을 받지 않는다. (지훈이가 있거나 없어도 언제든지 벽만 아니라면 언제든지 전파 가능) 지훈이는 불의 존재 여부에 대해 영향을 받는다. (불이 존재한다면 이동 불가) 지훈이가 가장자리에 도달하면 미로를 통과할 ..

알고리즘/🗂️ 정리

MST(최소신장트리) - 크루스칼 & 프림 알고리즘

2023.10.23

최소신장트리(MST / Minimum Spanning Tree)는 방향성이 없는 가중 그래프에서 간선의 가중치의 합이 최소인 신장 트리이다. 🕹️ 크루스칼 알고리즘 & 프림 알고리즘 과정 🔹 크루스칼 알고리즘 : 간선 중심으로 최소 신장 트리 구하기 (간선의 개수가 적다면 프림보다 효율적 !) 간선들의 가중치를 오름차순으로 정렬한 후 가중치가 낮은 간선부터 선택한다. 선택한 간선으로 인해 사이클이 형성된다면 다음 간선으로 넘어가고, 사이클이 형성되지 않는다면 해당 간선을 선택한다. ➔ 사이클이 형성되는지 파악하기 위해 Union-Find 연산을 진행한다. 정점이 N개인 그래프일 때, N-1개의 간선을 선택했다면 반복문을 종료한다. 🔹 프림 알고리즘 : 정점 중심으로 최소 신장 트리 구하기 (정점의 개수가..

알고리즘/BOJ

[BOJ] 14502 연구소 - Java

2023.09.28

✨ BFS + DFS + 완전탐색 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 📍고려해야할 점 벽을 3개 세운다. ➔ 일일이 3개의 벽을 세워본 후 바이러스를 퍼뜨려 안전영역이 최대인 경우를 구한다. (백트래킹 + 완전탐색) 벽을 3개 세운 후 바이러스가 퍼지는 경우는 다양하므로 복사본을 만들어서 구한다. 🕹️ 풀이과정 1️⃣ 바이러스와 벽이 있는 곳의 정보를 2차원 배열에 저장한다. 2️⃣ 벽을 세운다. ➔ 3개의 벽을 세워야 하므로 조합을 생각하면 ..

알고리즘/BOJ

[BOJ] 3190 뱀

2023.09.25

✨ 구현 ➔ '큐' 이용하기 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 📍 고려해야할 점 자료구조 '큐'의 특성을 이용해서 풀기 뱀의 머리를 먼저 이동시켜 몸길이 늘리기 해당하는 칸에 사과가 있으면 사과를 먹고 사과를 없애주기 뱀의 꼬리가 아닌 몸통을 만나면 끝내기 ➔ return !! 벽에 닿으면 끝내기 ➔ return !! 뱀은 (1, 1)에 존재 행, 열 잘 구분하기 ! 방향 바꿀 때 효율적인 방법 생각해보기 🕹️ 풀이과정 1️⃣ 행, 열에..

알고리즘/BOJ

[BOJ] 11657 타임머신

2023.09.08

✨ 최단경로 알고리즘 ➡️ 벨만 포드 알고리즘 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 📍 고려해야할 점 C < 0 인 경우 타임머신으로 시간을 되돌아가는 경우이다. ➔ 음의 가중치 존재 1번 도시에서 출발한다. 음의 사이클이 있거나 경로가 아예 없다면 -1 출력 오버플로우 범위 조심 🕹️ 풀이과정 1️⃣ 간선과 정점, 비용의 정보를 저장한다. 2️⃣ 벨만 포드 알고리즘을 사용..

알고리즘/BOJ

[BOJ] 1865 웜홀

2023.09.08

✨ 최단경로 알고리즘 ➡️ 벨만 포드 알고리즘 https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 📍 고려해야할 점 한 지점에서 출발하여 다시 출발했던 지점으로 돌아왔을 때 처음 출발했을 때보다 시간이 되돌아가 있는 경우 판단 ➔ 웜홀 내에서 시간이 거꾸로 흘러간다. ➡️ 음수 가중치 존재 & 음의 사이클 존재 O 한 지점에서 출발한다. (특정 지점에서 출발 X) 임의의 정점에서 출발 모든 정점에서 출발 두 지점을 연결하는 도로가 한 ..

티스토리툴바