th42500의 TIL

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ✔ 입출력 예시 💡 포인트 1️⃣ 항상 "ICN" 공항에서 출발 2️⃣ tickets 배열의 원소는 [출발지, 도착지] 형태로 이루어짐 3️⃣ 주어진 항공권을 모두 사용해야 함 4️⃣ 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return ❓ 풀이방법 처음에는 BFS 알고리즘을 이용해볼까 생각했지만 알파벳 순서가 앞서는 경로를 답으로 구해야했기 때문에 DFS 알고리즘을 이용..

처음에는 배열을 먼저 정렬해야하나 싶었지만 배열의 우선순위로 정렬해도 원하는 답이 나오지 않아 배열 정렬 없이 DFS로 도전했던 문제 🔥 https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ✔ 입출력 예시 1️⃣ 첫번째 시도 ❓ 풀이방법 👉 모든 경우의 수를 구하기 위해 DFS 활용 1️⃣ DFS 함수에 필요한 변수들 넣기 (dungeons, 방문 배열, k, 탐험한 던전 수) 2️⃣ 반복문을 돌리며 완전 탐색 진행 (이미 탐험했던 던전은 ❌, 아..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 코드 효율 👉 메모리 : 15760 KB 👉 시간 : 164 ms 👉 코드 길이 (주석 및 print()함수 제외) : 1430 B ✔ 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { //..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 코드 효율 👉 메모리 : 14124 KB 👉 시간 : 124 ms 👉 코드 길이 (주석 및 print()함수 제외) : 1029 B ✔ 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main ..

DFS (Depth-First Search) ✔ 그래프 탐색 알고리즘 탐색(Search)이란 많은 양의 데이터 내에서 원하는 데이터를 찾는 과정을 의미 ✔ DFS 특징 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로, 깊이 우선 탐색이라고도 불림 재귀적으로 구현 또는 후입선출 구조의 스택을 적용 트리일 경우 순회 방향 (번호 순서대로 진행) 시간복잡도는 O(V+E) 👉 V : 노드 수, E : 에지 수 ✔ 동작 과정 1️⃣ 탐색 시작 노드를 스택에 삽입하고 방문 처리 2️⃣ 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼내기 3️⃣ 더 이상 2️⃣번의 과정을 수행할 수 없을 때까지 반복 ..