본문 바로가기

알고리즘23

[Java] Tree 트리 자료구조의 종류 : Tree, Binary Tree, Binary Serach Tree, Balanced Binary Serach Tree, Heap, Trie이번 포스트에서는 기본적인 Tree에 대해서만 작성해보자. Tree란 ? Node와 Edge로 구성된 방향이 존재하는 비순환 Graph의 한 종류이다. 그래서 DAG(Directed Acyclic Graphs)라고도 한다.그럼 Graph로 분류하면 되지 왜 Tree냐는 의심을 하게 된다.Tree는 Graph에서 몇가지 특성을 더 가진다. 1. 루트 노드가 하나 존재한다.2. 부모 노드는 하나밖에 존재하지 않는다.3. 노드는 0개 이상의 자식을 가지고 있다.4. 자식이 0개인 경우 단말노드(Leaf Node)라고 한다.5.. 위 특성을 지키는 .. 2024. 7. 7.

백준 - [BOJ 1865] 웜홀 문제때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.입력첫 번째 줄에는.. 2024. 7. 6.

[최단경로] Bellman-Ford Algorithm 최단경로 알고리즘package com.study.datastructrue.mst;import java.util.ArrayList;import java.util.Arrays;class Pair { T node; V cost; public Pair(T node, V cost) { this.node = node; this.cost = cost; }}public class BellmanFord { static long[] dist = new long[6]; public static void main(String[] args) { // 집 1, 학교 2, 박물관 3, 영화관 4, 마트 5 ArrayList>> graph = inpu.. 2024. 7. 6.

백준 - [BOJ 3085] 사탕게임 백준 온라인 져지(BOJ)에서 제공 되는 3085번 문제는 브루트 포스(Brute-Froce, 완전 탐색) 유형이다. 해당 문제는 code.plus 기초 2/2, 브루트포스에 게시된 문제이다. 문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 보드의 크기 N이 .. 2024. 3. 1.

백준 - [BOJ 12094] A와 B 백준 온라인 져지(BOJ)에서 제공 되는 12094번 문제는 그리디(Greedy, 탐욕법) 유형이다. 해당 문제는 code.plus 중급 1/3, 그리디 알고리즘에 게시된 문제이다. 문제 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다. 문자열의 뒤에 A를 추가한다. 문자열을 뒤집고 뒤에 B를 추가한다. 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 .. 2024. 2. 29.

백준 - [BOJ 2109] 순회강연 백준 온라인 져지(BOJ)에서 제공 되는 2019번 문제는 그리디(Greedy, 탐욕법) 유형이다. 해당 문제는 code.plus 중급 1/3, 그리디 알고리즘에 게시된 문제이다. 문제 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다. 예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 .. 2024. 2. 29.

6. STL 사용하기 - std::list STL 이란? C++ 에서 제공하는 STandard Library를 STL이라고 한다. 자바에서는 자바에서 제공하는 API라고 볼 수 있다. 지금까지 list에 대해 직접 설계해보았고 list에 대한 설명이 충분했다. 이번에는 STL을 직접 사용하면서 어떤 기능이 있고 언제, 어떻게 사용할 지 생각해보도록 하자. ※ 시간이 오래 걸리는 Method는 제외한다. (효율적 사용) std::list Construct Method Description (constuctor) 리스트 생성시 입력 값 operator= = 기호에 대한 연산 방법 Iterators Method Description begin() 리스트 Head에 속한 데이터 위치 end() 리스트 마지막 위치 != Tail, null 값 rbegin.. 2024. 2. 11.

5. 원형 연결 리스트 (Circular Linked List) 원형 연결 리스트란? 단순 연결 리스트에서 끝이 처음과 연결되어 있는 형태를 원형 연결 리스트라고 합니다. STL에도 구현되어있지 않고 아직 학생 수준이지만, 실제로 사용되는 경우도 본 적이 많이 없습니다. 그래서 단순하게만 만들어보도록 할 것인데, 이중 연결 리스트 형태로 만들려고 합니다. (실제로 순환적인 요소는 큐 또는 재귀를 많이 사용하는듯) 원형 연결 리스트(Circular Linked List) 구현하기 많은 기능을 추가하지는 않겠습니다. 노드 #pragma once template class Node { public: Node(T data); T getData() const; Node* getNext() const; Node* getPrev() const; void setNext(Node* .. 2024. 2. 10.

4. STL 따라잡기 - 이중 연결 리스트 (Doubly Linked List) 구현 이중 연결 리스트란 ? 여기서 연결 리스트에 대한 개념을 알게 되었고 여기서 단순 연결 리스트를 구현해보았다. 또, 앞선 포스팅에서 연결에 대한 방법을 말했는데 '이중 연결 리스트' 는 양방향(이중)으로 구성된 자료구조이다. 즉, 싱글 연결 리스트는 코스 여행이라면 이중 연결 리스트는 자유 여행이다. 이에 대해선 내가 생각한 예시이기 때문에 한 번 생각해보고 비슷한 예시를 찾아서 본인만의 개념으로 이해하길.. 이번 STL 따라잡기 포스트는 standard library인 list를 만들어보겠다. 먼저, list에 어떤 기능이 있는지 한 번 알아보자. 우리는 STL list에 어떤 기능이 구현되어있는지 파악한 뒤에 이를 정리할 것이다. 깃허브 이슈에 구현할 내용을 작성하고 이를 바탕으로 레파지토리에 저장할.. 2024. 2. 7.

이전 1 2 3 다음

티스토리툴바