Hyun's Wonderwall

에지 리스트와 인접 리스트가 헷갈림: https://u-it.tistory.com/49109. 그래프그래프: 노드와 에지로 구성된 집합- 노드: 데이터를 표현하는 단위- 에지: 노드를 연결(트리도 그래프의 일종) 09-1. 그래프의 표현그래프를 구현하는 방법은 3가지. 1. 에지 리스트(edge list): "에지를 중심"으로 그래프를 표현.- 배열에 "출발 노드, 도착 노드"를 저장하여 에지를 표현- 또는 "출발 노드, 도착 노드, 가중치"를 저장하여 가중치가 있는 에지를 표현. 에지 리스트로 가중치 없는 그래프 표현하기- 가중치가 없는 그래프는 출발 노드와 도착 노드만 표현 -> 배열 열은 2개면 충분.노드는 여러 자료형을 사용할 수 있는데 다음의 경우 노드는 Integer형.방향 그래프: 1->2,..

07. 그리디그리디 알고리즘: '현재 상태에서 보는 선택지 중 최선의 선택지'가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 그리디 알고리즘의 핵심 이론:1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.[11047번: 동전 0] / 실4동전을 최소로 사용해 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.import java.util.Scanner;public class Main { public static void ..

06. 탐색탐색: 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘. 주어진 데이터의 성질(정렬/비정렬)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요, 직접 구현해 원리를 완벽하게 이해해야 한다.그래프를 자주 이용한다.( c.f. [알고리즘] 완전탐색 기법 https://velog.io/@717lumos/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89-%EA%B8%B0%EB%B2%95 ) 06-1. 깊이 우선 탐색DFS: 그래프 완전 탐색 기법 중 하나.- 특징: 재귀 함수로 구현, 스택 자료구조 이용- 시간 복잡도: O(V+E)- 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로우에 유의해야 한다.- D..

1655번: 가운데를 말해요https://www.acmicpc.net/problem/1655 문제백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.입력첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,00..

정렬 알고리즘들과 정의정렬 알고리즘정의버블데이터끼리 인접 요소끼리 비교하고, swap 연산을 수행하며 졍렬하는 방식선택대상에서 가장 크거나 작은 데이터를 찾아 선택하는 과정을 반복하면서 정렬하는 방식삽입대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식퀵pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식병합(합병)이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식힙최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방식 (내림차순 정렬-최소 힙 / 오름차순 정렬-최대 힙)기수데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 05-1. 버블 정렬버블 정렬: 두 인접한 데이터의 크기를 비교해 정렬. 시간 복잡도 O(n^2)으로 다른 알고리즘보다..

04-1. 배열과 리스트배열: 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조.- 값을 인덱스를 통해 참조(값에 바로 접근 가능. 새로운 값 삽입/삭제 어렵.)- 배열의 크기는 선언할 때 지정, 한 번 선언하면 크기를 늘리거나 줄일 수 X.- 선언한 자료형의 값만 저장 가능.리스트: 값과 포인터를 묶은 노드를 포인터로 연결한 자료구조- 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 (값에 접근하는 속도 느림)[11720번: 숫자의 합] / 브4import java.io.*;import java.util.*;public class Main{ public static void main(String[] args) throws IOException { BufferedRea..

1520번: 내리막 길https://www.acmicpc.net/problem/1520 문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점..

2240번: 자두나무 https://www.acmicpc.net/problem/2240 문제자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어지는 자두를 받아서 먹고는 한다. 자두를 잡을 때에는 자두가 허공에 있을 때 잡아야 하는데, 이는 자두가 말랑말랑하여 바닥에 떨어지면 못 먹을 정도로 뭉개지기 때문이다.매 초마다, 두 개의 나무 중 하나의 나무에서 열매가 떨어지게 된다. 만약 열매가 떨어지는 순간, 자두가 그 나무의 아래에 서 있으면 자두는 그 열매를 받아먹을 수 있다. 두 개의 나무는 그다지 멀리 떨어져 있지 않기 때문에, 자두는 하나의 나무 아래에 서 있다가 다..