전체 글

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 사용한 알고리즘 : 다익스트라 풀이전략 이동할 때마다 드는 비용이 순간이동시에 0, 좌우 이동시에 1이 든다. 이동할 때 드는 비용이 모두 같은 경우에는 너비우선탐색(BFS)를 사용하겠지만 해당 문제에서는 그렇지 않기 때문에 다익스트라를 사용하여 문제를 풀이한다. 다익스트라에서는 우선순위 큐를 사용하는데, 이 문제에서는 가장 적은 비용으로 특정 위치에 도..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 사용한 알고리즘 : 다익스트라 풀이전략 하나의 시작점에서 모든 노드를 가는데 필요한 최소값을 구하는 문제이다. 전형적인 다익스트라 사용 문제로, 자바를 사용한 경우 목표 지점과 목표 지점까지의 비용이 들어가는 클래스를 추가로 사용하면 된다. 동작 과정은 다음과 같다. 1. 출발 노드 설정 2. 최단 거리 테이블 초기화(모두 무한(1e9)으로 설정) 3. ..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 사용한 알고리즘 : DP 풀이전략 arr[i][j]는 i행 i열에 입력된 값을 의미한다. d[i][j]는 i행 i열에서 가질 수 있는 1행에서부터 덧셈된 합의 최대값을 의미한다. 먼저 삼각형의 크기를 나타내는 n의 범위가 1

목표 리액트로 작성된 프론트단에서 게시글을 작성한 뒤 등록 버튼을 누르면 작성한 데이터들을 서버인 스프링으로 전송한다. 기본설정 commons-fileupload commons-fileupload 1.4 commons-io commons-io 2.11.0 pom.xml에 추가한다. React 1) 입력 전 2) 입력 후 위처럼 게시판 종류, 제목, 내용, 파일들을 입력하고 등록버튼을 통해 스프링에 데이터를 전송할 것이다. React(프론트) 전체 코드 import FloatingLabel from 'react-bootstrap/FloatingLabel'; import Form from 'react-bootstrap/Form'; import React, {useState} from 'react'; impo..

Iterator란? ArrayList, HashSet과 같은 컬렉션을 반복하는 데 사용할 수 있는 인터페이스 객체 Iterator 인터페이스 public interface Iterator { boolean hasNext(); // 현재 위치에 객체가 존재하는지 확인해주는 메소드 Object next(); // 다음 객체를 가리키도록 하는 메소드 void remove(); // 현재 위치의 객체를 삭제하는 메소드 } 사용법 import java.util.ArrayList; import java.util.Iterator; public class Main { public static void main(String[] args) { // 컬렉션 생성 ArrayList problems = new ArrayList..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 사용한 알고리즘 : DFS 풀이전략 (0,0)에서 (N-1,N-1)까지의 인덱스에서 상하좌우 방향으로 dfs를 수행한다. dfs 탐색은 상하좌우 방향의 인덱스를 대상으로 방문하지 않았으면서 해당 위치의 값이 기존의 인덱스에서의 값과 일치할 때 탐색을 수행한다. 이 문제에서는 적록색약인 경우와 아닌 경우 두 가지 경우에서 나뉜 구역의 수를 구해야 하므로dfs를 구현한 함수의 매개변수에 ..

https://www.acmicpc.net/problem/1351 1351번: 무한 수열 첫째 줄에 3개의 정수 N, P, Q가 주어진다. www.acmicpc.net 풀이 사용한 알고리즘: DP 풀이전략 문제에서 주어진 식대로 d[i] = d[i/P] + d[i/Q] 를 사용하여 N에서의 An을 구한다. 단, Bottom-up 방식을 사용하면 i가 1~N까지 모든 경우의 수를 구하게 되는데 위 방식에서 Map에 많은 노드들이 삽입되어 메모리초과가 발생한다. 따라서 Top-down 방식을 사용하여 메모이제이션하는 수를 줄여야한다. Top-down 방식을 사용하면 i가 1~N까지의 모든 경우의 수를 구하지 않고, N에서 부터 정말 필요로하는 값들만을 저장해두므로 메모리초과가 발생하지 않는다. 또한 DP문제..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 사용한 알고리즘 : DP 풀이전략 문제에서 인접한 집들 간에 동일한 색이 칠해지지 않으면 된다고 했다. 즉, 첫번째 집이 빨간색으로 칠해졌다면 두번째 집은 빨간색이 아닌 초록색이라 파란색으로 칠해져야한다. 그리고 세번째집은 두번째 집이 칠해지지 않은 두 가지 색중 하나로 칠해져야한다. int d[][] = new int[N][3] 라는 2차원 배열은 특정 인덱스에서 각각..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 사용한 알고리즘 : DP(Dynamic Programming) 풀이전략 N=1일 때, 동물원에서 우리의 형태는 아래와 같다. 첫 행에 사자가 있을 경우는 (1) 없는 경우 ( =d[1][0]) (2) 1열에 하나 있는 경우 ( =d[1][1]) (3) 2열에 하나 있는 경우 ( =d[1][2]) 로 총 3가지 경우가 있다. N=2일 때, 동물원에서 우리의 형태는 아래와 같다. 두번째 행에서 사자가 있을 경우는 (1) 사자가 없는 경우 : 첫번째 행에서 사자가 어떤 형태로 있어도 상관없다. d[2][0] = d[1][0]+d[..

https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 풀이 사용한 알고리즘: BFS 풀이전략 1. 주어진 입력을 2차원 배열에 작성한다. 2. (0,0)에서 (N-1,M-1)까지 각각의 인덱스를 BFS 탐색한다. 3. 특정 인덱스에서 주변에 인접한 모든 방향 탐색 중, 작성한 2차열 배열 인덱스를 넘어서지않고, 방문하지 않았으며 그래프상 같은 수를 가진 경우 방문처리하고 해당 인덱스를 Inqueue한다. 4. BFS 탐..