java29 자료구조 - 한방향 연결리스트, 양방향 연결리스트 1. 연결리스트1) 개념자료의 논리적인 순서와 메모리 상의 물리적인 순서가 일치하지 않고, 개별적으로 위치하고 있는 원소의 주소를 연결하나의 전체적인 자료구조를 이룸.링크를 통해 원소에 접근하므로, 순차 리스트에서처럼 물리적인 순서를 맞추기 위한 작업이 필요하지 않음자료의 크기를 동적으로 조절해 메모리의 효율적인 사용 가능.(추가 삭제 빠름)2) 노드연결 리스트에서 하나의 원소에 필요한 데이터를 갖고 있는 자료단위- 구성요소데이터 필드 : 원소의 값링크 필드 : 다음 노드의 주소 ( 마지막 노드는 링크 값을 null로 가짐)- 헤드 : 리스트의 처음 노드를 가리키는 레퍼런스 2. 한방향 연결리스트1) 연결구조노드가 하나의 링크 필드에 의해 다음 노드와 연결되는 구조를 가짐헤드가 가장 앞의 노드를 .. 2024. 5. 24. 백준 12904번. A와B (Java) 1. 문제 조건 2. 아이디어 주어진 시간은 2초이다. S의 길이는 최소 1에서 최대 999, T의 길이는 최대 1000이다. S에서 T가 만들어질 수 있는 지 확인하기 위해 문자열 뒤에 A을 한 번 추가해보고, 또 문자열을 뒤집고 B를 추가하는 연산을 각각 수행해보는 완전탐색 방식은 시간초과가 난다. S의 길이가 1이고 T의 길이가 1000인 최악의 상황을 고려했을 때, 999자리만큼 문자를 늘려야한다. 위에서 설명한 방식은 한 자리씩 늘릴 때마다 2가지 경우의 수가 존재하므로 2의 999제곱이 되어 시간초과가 발생한다. 따라서 S에서 완전탐색으로 T를 만들어나가는 과정은 적용할 수 없다. 그렇다면 반대로 T에서 S를 만들어나가면 된다. S에 1번 연산을 적용하면 맨 뒤 알파벳은 A가 되고 2번 연산을.. 2024. 4. 12. (알고리즘/Java) 벨만-포드 (Bellman-Ford) 알고리즘 1. 개념 그래프의 최단 경로를 구하는 알고리즘으로 벨만-포드 외에도 그래프의 다익스트라(Dijkstra)와 플로이드-와샬(Floyd-Wrasahll)이 있으며 이전 포스팅을 통해 다뤘었다. 벨만-포드 알고리즘은 다음과 같은 특성을 가진다. 그래프의 최단 경로를 구하는 알고리즘 하나의 정점에서 출발하는 최단거리를 구함 음수 가중치는 허용하되, 음수 사이클이 없어야 함 O(nm)의 시간복잡도 동적 계획법 사용 하나의 출발지를 지정해 최단거리를 구한다는 측면에서 다익스트라와 같지만 음수가중치를 허용한다는 점에서 다익스트라와 차이가 있다. 2. 알고리즘 단계 알고리즘 과정 벨만-포드 알고리즘의 과정에 대해 단계별로 살펴보자. 다익스트라와 마찬가지로 dist배열을 통해 최단거리를 기록할 것이다. N개의 노드가 .. 2024. 2. 25. 백준 1240번. 노드사이의 거리 (Java) 1. 문제 조건 2. 아이디어 주어진 예제 입력을 살펴보면 아래와 같다. 인접행렬은 메모리 차지를 많이 할 수 있다고 생각되어 인접리스트로 구현하려고 했다. 또한, 두 노드 사이의 거리를 구하기 위해서는 간선 사이에 양방향 통행이 가능해야 하므로, 부모, 자식 상관 없이(문제에서 부모 자식을 구분할 수도 없었다.) 양 쪽 노드의 자식 노드 list에 노드를 모두 추가해줘야겠다고 생각했다. 이 때, 거리도 함께 기억해야 하므로 class를 생성하여 관리하고자 했다. 문제풀이를 하는 방식은 BFS와 DFS를 떠올렸다. 단순히 하나의 노드에서 목적지 노드까지 간선을 따라 타고 가기만 하면 되는 문제였기 때문이다. 실제로 두가지 방식으로 구현하여 제출 후 정답처리 되었으며 이 문제는 메모리와 시간복잡도 두가지 .. 2024. 2. 16. 백준 2579번 계단 오르기(Java) package baek.silver3; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main_2579계단오르기 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int[] map = new int[N]; int[][] dp = new int[N+1][3];.. 2023. 10. 1. 백준 17182번 우주탐사(JAVA) package baek.gold3; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main_17182우주탐사 { static int answer = Integer.MAX_VALUE; static boolean[] visited; static int[][] dist; static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead.. 2023. 9. 30. 이전 1 2 3 4 5 다음
