그래프
정점 : 그래프 노드 또는 점
간선 : 정점 간의 연결, 부모-자식 개념 없음
가중치 : 간선(엣지)에 할당된 값
차수 : 정점에 연결된 간선의 수
진입 차수 : 방향 그래프에서 특정 정점으로 들어오는 간선의 수
진출 차수 : 방향 그래프에서 특정 정점에서 나가는 간선의 수
경로 :두 정점 간에 존재하는 간선의 연속
사이클 : 시작 정점에서 출발하여 다시 시작 정점으로 돌아오는 경로. 트리와 가장 큰 차이
연결 그래프 : 모든 정점이 서로 연결된 그래프
포화 그래프 : v개의 정점을 가지는 그래프는 최대 V * (V-1) / 2 간선이 가능
부분 그래프 : 원래 그래프의 일부 정점과 간선으로 구성된 그래프
방향 그래프 : 간선에 방향이 있는 그래프
무방향 그래프 : 간선에 방향이 없는 그래프
DFS
최대한 깊이 들어간 후, 더 이상 갈 곳이 없으면 되돌아오는 방식

BFS
현재 노드에서 가까운 노드를 먼저 탐색하고, 점차 멀리 탐색하는 방식

인접 행렬 vs 인접 리스트
그래프를 표현하는 방법에는 인접 행렬(Adjacency Matrix) 과 인접 리스트(Adjacency List) 가 있음
인접 행렬 : 2차원 배열을 사용하여 그래프의 연결 정보를 저장, 연결되지 않은 노드 정보도 저장
인접 리스트 : 각 노드마다 연결된 노드 리스트를 저장, 연결된 노드만 저장하므로 메모리 절약 가능
도전문제
[JAVA]SWEA - 1873. 상호의 배틀필드 (D3)
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int x, y, H, W; static char[][] map; static char direction; public static void main(String[] args) throws
leeemingyu.tistory.com
[JAVA]SWEA - 1954. 달팽이 숫자 (D2)
package graph;import java.util.Scanner;public class Main { static int[] dr = { 0, 1, 0, -1 }; static int[] dc = { 1, 0, -1, 0 }; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int t = 1; t = N || r
leeemingyu.tistory.com
[JAVA]SWEA - 1873. 상호의 배틀필드 (D3)
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int x, y, H, W; static char[][] map; static char direction; public static void main(String[] args) throws
leeemingyu.tistory.com
개인 과제
[JS]프로그래머스 - 최댓값과 최솟값 (Lv.2)
나의 풀이function solution(s) { var answer = ''; let arr = s.split(" "); let min = parseInt(arr[0]); let max = parseInt(arr[arr.length-1]); for(i of arr){ if(min > parseInt(i)){ min = parseInt(i); }else if (max 주어진 문자열을 split을 통해
leeemingyu.tistory.com
[JS]프로그래머스 - 카펫 (Lv.2)
나의 풀이function solution(brown, yellow) { var answer = []; for(i = 1; i b-a); return answer;}전체 격자의 개수가 brown + yellow가 맞는지 확인바깥쪽 brown을 제외한 안쪽 부분이 yellow가 맞는지 확인맞는지 확인 후 저
leeemingyu.tistory.com
'[LG 유플러스] 유레카 > Today I Learned' 카테고리의 다른 글
[TIL][02.24] MST, Kruskal, Prim, Dijkstra (0) | 2025.02.25 |
---|---|
[TIL][02.21] 그래프, 트리, BFS, DFS, 스택, 큐 (0) | 2025.02.24 |
[TIL][02.19] 비선형 자료구조, 트리, 이진트리, 이진검색, 분할정복 (0) | 2025.02.20 |
[TIL][02.14] Stack, Queue, PriorityQueue, Heap, Scanner (0) | 2025.02.16 |
[TIL][02.13] 재귀, Serialization, 배열, Exception (0) | 2025.02.13 |
그래프
정점 : 그래프 노드 또는 점
간선 : 정점 간의 연결, 부모-자식 개념 없음
가중치 : 간선(엣지)에 할당된 값
차수 : 정점에 연결된 간선의 수
진입 차수 : 방향 그래프에서 특정 정점으로 들어오는 간선의 수
진출 차수 : 방향 그래프에서 특정 정점에서 나가는 간선의 수
경로 :두 정점 간에 존재하는 간선의 연속
사이클 : 시작 정점에서 출발하여 다시 시작 정점으로 돌아오는 경로. 트리와 가장 큰 차이
연결 그래프 : 모든 정점이 서로 연결된 그래프
포화 그래프 : v개의 정점을 가지는 그래프는 최대 V * (V-1) / 2 간선이 가능
부분 그래프 : 원래 그래프의 일부 정점과 간선으로 구성된 그래프
방향 그래프 : 간선에 방향이 있는 그래프
무방향 그래프 : 간선에 방향이 없는 그래프
DFS
최대한 깊이 들어간 후, 더 이상 갈 곳이 없으면 되돌아오는 방식

BFS
현재 노드에서 가까운 노드를 먼저 탐색하고, 점차 멀리 탐색하는 방식

인접 행렬 vs 인접 리스트
그래프를 표현하는 방법에는 인접 행렬(Adjacency Matrix) 과 인접 리스트(Adjacency List) 가 있음
인접 행렬 : 2차원 배열을 사용하여 그래프의 연결 정보를 저장, 연결되지 않은 노드 정보도 저장
인접 리스트 : 각 노드마다 연결된 노드 리스트를 저장, 연결된 노드만 저장하므로 메모리 절약 가능
도전문제
[JAVA]SWEA - 1873. 상호의 배틀필드 (D3)
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int x, y, H, W; static char[][] map; static char direction; public static void main(String[] args) throws
leeemingyu.tistory.com
[JAVA]SWEA - 1954. 달팽이 숫자 (D2)
package graph;import java.util.Scanner;public class Main { static int[] dr = { 0, 1, 0, -1 }; static int[] dc = { 1, 0, -1, 0 }; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int t = 1; t = N || r
leeemingyu.tistory.com
[JAVA]SWEA - 1873. 상호의 배틀필드 (D3)
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int x, y, H, W; static char[][] map; static char direction; public static void main(String[] args) throws
leeemingyu.tistory.com
개인 과제
[JS]프로그래머스 - 최댓값과 최솟값 (Lv.2)
나의 풀이function solution(s) { var answer = ''; let arr = s.split(" "); let min = parseInt(arr[0]); let max = parseInt(arr[arr.length-1]); for(i of arr){ if(min > parseInt(i)){ min = parseInt(i); }else if (max 주어진 문자열을 split을 통해
leeemingyu.tistory.com
[JS]프로그래머스 - 카펫 (Lv.2)
나의 풀이function solution(brown, yellow) { var answer = []; for(i = 1; i b-a); return answer;}전체 격자의 개수가 brown + yellow가 맞는지 확인바깥쪽 brown을 제외한 안쪽 부분이 yellow가 맞는지 확인맞는지 확인 후 저
leeemingyu.tistory.com
'[LG 유플러스] 유레카 > Today I Learned' 카테고리의 다른 글
[TIL][02.24] MST, Kruskal, Prim, Dijkstra (0) | 2025.02.25 |
---|---|
[TIL][02.21] 그래프, 트리, BFS, DFS, 스택, 큐 (0) | 2025.02.24 |
[TIL][02.19] 비선형 자료구조, 트리, 이진트리, 이진검색, 분할정복 (0) | 2025.02.20 |
[TIL][02.14] Stack, Queue, PriorityQueue, Heap, Scanner (0) | 2025.02.16 |
[TIL][02.13] 재귀, Serialization, 배열, Exception (0) | 2025.02.13 |