[백준 알고리즘, 자바] Q1699 제곱수의 합 - 동적계획법
1. Java 구현 (1) 처음 구현 - 완전 실패 import java.io.*; import java.util.ArrayList; import java.util.List; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine()); int cn..
[백준 알고리즘, 자료구조] Tree 정의 및 종류 및 백준 1920 수 찾기 풀이
오늘은 자료구조 Tree 에 대해 알아보려고 한다. Tree에 대해 최근 배웠고, 오늘 푼 알고리즘 문제가 트리와 관련이 있기 때문에 정리하려고 한다. 참고로 B Tree 내용이 많기 때문에 내일 다시 정리하려고 한다. 우선 트리에 대해 정리하고, 마지막에 알고리즘 풀이를 하겠다. 1. 트리의 특징 나무위키 가라사대, 트리는 부모 노드 밑에 자식 노드가 연결되 있고, 자식 노드 밑에 또 다른 자식 노드가 연결되 있는 재귀적 형태의 자료구조를 의미한다.트리는 그래프의 한 종류로서 각각의 노드들을 연결하는 간선은 하나뿐이며, 비순환형 그래프를 트리라고 부른다. 트리와 그래프를 비교해보자! 그래프 트리 각각의 노드들 사이에 2개 이상의 경로 가능, 양방향 경로 가능 두개의 노드 사이에 오직 한개의 경로만 가능..
2-1 스택(Stack), 큐(Queue), 큐(Deque)
1. Stack - LIFO (Last In First Out) 를 구현한 자료구조 (처음 삽입한 객체는 가장 마지막에, 가장 최근에 삽입한 객체는 가장 처음으로 꺼내는 방식) - 함수 내의 변수들이 임시로 저장되는 공간 2. Queue - FIFO (First In First Out) 를 구현한 자료구조 (처음 삽입한 객체를 먼저 꺼내는 방식) - 아래는 큐의 구현클래스인 우선순위큐(Priority Queue)를 활용한 예제이다. 우선순위큐는 정렬기준의 맞추어 순차적으로 출력이 되는 큐를 의미 아래에서 정렬의 우선순위를 학생의 학년으로 설정하였고, 우선순위에 맞게 출력이 될 수 있도록 설정했다. 그리고 Student 클래스에서 grade 로 정렬을 하기 위해 Comparable 인터페이스를 구현하여 C..
1-2. 재귀함수 - 픽셀수 구하기
1. 문제 설명 출발 좌표를 임의로 지정했을 때, 인접한 셀이 몇개인지 세는 문제이다. 좌, 우, 상, 하, 대각선 위치에 셀이 0이 아니면 인접한 셀로 정의한다. 백준 알고리즘의 Q2667 단지번호 붙이기와 비슷한 문제이다. 초록색 2번을 보면, 위쪽에 숫자가 있기 때문에 인접한 셀이다. 하지만, 좌측와 우측에는 숫자가 없기 때문에 인접하다고 할 수 없다. 2. Java구현 package recursive; package codeSquad.recursive; public class CountCellBlob { public static void main(String[] args) { int[][] image = { {1, 0, 0, 0, 0, 0, 0, 1}, {0, 1, 1, 0, 0, 1, 0, 1}..
1-1. 재귀함수 - 미로찾기
1. 문제 설명 출발 좌표를 임의로 지정해주었을 때, 탈출이 가능한지 확인하는 문제이다. 미로에는 검은색 벽이 존재한다. (입력 시, 1은 벽을 의미하고, 0은 이동이 가능한 길을 의미) 2. Java 구현 package recursive; public class FindMaze { public static void main(String[] args) { /* 1 : 벽, 0 : 이동 가능 통로 */ int[][] maze = { {0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 0, 1, 1, 0, 1}, {0, 0, 0, 1, 0, 0, 0, 1}, {0, 1, 0, 0, 1, 1, 0, 0}, {0, 1, 1, 1, 0, 0, 1, 1}, {0, 1, 0, 0, 0, 1, 0, 1},..