[백준] 11060번 : 점프 점프 - JAVA [자바]
2024. 1. 3. 16:16
Algorism/백준
https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 문제 위 문제는 DP 풀이법으로 풀었다. 아래의 문제와 유사하다. https://bean-conding.tistory.com/16 [백준] 11048번 : 이동하기- JAVA [자바] https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다...
[백준] 11048번 : 이동하기- JAVA [자바]
2024. 1. 3. 15:38
Algorism/백준
https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 문제 이 문제는 DP의 Memonization을 이용하여 풀었다. 문제는 간단하다 (1, 1) 좌표에서 시작하여 (N, M) 좌표까지 이동하면서 사탕을 먹으면서 간다. 방향은 3가지로 아래, 오른쪽, 오른쪽 아래 대각선을 이동할 수 있다. DP의 기본적인 문제라고 생각한다. 왜냐하면 특별한 점화식이 필요없기 때문이다 나의 로직은 아래와 같다. (1, 1) 좌표에서 내가 갈 수 있는 ..
[백준] 5014번 : 스타트링크 - JAVA [자바]
2024. 1. 2. 19:57
Algorism/백준
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 이 문제는 BFS로 쉽게? 풀었다. 로직은 아래와 같다. 1. Route 클래스를 저장하는 Queue를 생성한다. 2. Queue에 초기값인 현재층수와 버튼을 누룬횟수인 0을 넣는다. 3. BFS을 돌면서 아래의 조건을 만족하면 Queue에 다음층을 넣는다. 다음 층이 F층 위에 있거나, 1층 밑이면 Continue 다음 층이 만약 방문한 층이면 Continue 다음 층이 만약 목적지에 도착한다면 Ret..
DB - 인덱스(Index)란?
2024. 1. 2. 18:44
CS/DB
대학생 강의와 유튜브에서 데이터베이스에서 인덱스가 중요하다... 풀스캔은 안좋기 때문에 인덱스처리를 해줘라... 라는 내용을 들었고, 대충 인덱스가 무엇인지 알지만 스스로 깊이 공부해보고 싶어서 포스팅해본다. 실제로 팀 프로젝트를 하면서 조회 쿼리문을 더 빠르기하기 위해서 사용한적 있다. 개발자가 되기위해선 사용할 줄만 알면 안된다! 일상 생활에서 인덱스 책에서 인덱스를 많이 접해보았다. 만약 책에서 인덱스가 없다면 어떻게 될까? 매일 내가 원하는 부분을 보기위해 책을 드르륵? 긁으면서 찾을 것이다. 인덱스가 있기에 우리가 원하는 내용을 찾을때 바로 볼 수 있다. 데이터 베이스의 인덱스도 같은 맥락이다. 공공데이터를 이용하여 데이터베이스에 저장하면, 수 만개의 데이터가 한 테이블에 저장된다. 만약 모든 ..
[백준] 14225번 : 부분수열의 합 - JAVA [자바]
2024. 1. 2. 14:12
Algorism/백준
https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 문제 아래 문제를 풀면서 부분집합을 비트마스킹으로 더 풀고 싶었고 부분집합 문제를 풀기위해 이 문제를 풀었다. https://bean-conding.tistory.com/12 [백준] 15661번 : 링크와 스타트 - JAVA [자바] https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트..
[백준] 15661번 : 링크와 스타트 - JAVA [자바]
2024. 1. 2. 11:27
Algorism/백준
https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 문제 이 문제는 실버1 스타트와 링크의 후속 문제이다. 아래의 글을 먼저 보고오면 편하다. https://bean-conding.tistory.com/10 [백준] 14889번 : 스타트와 링크 - JAVA [자바] https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2..
[백준] 2529번 : 부등호 - JAVA [자바]
2024. 1. 1. 18:18
Algorism/백준
https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 문제 문제를 본 순간 순열을 사용하면 풀릴것 같다는 생각이 들었다. K는 최대 9까지 나올 수 있으니 9! = 362880 임으로 1억이 안되는 걸로 보아 1초안에 테스트가 가능할 것이라고 생각했다. 또한 순열 로직안에서 1중 for문임으로 362880 x 9 = 3625920 널널하다! 내가 푼 로직은 이렇다. 1. K + 1 크기의 0~9까지의 수를 순열로 구한다. 2. 순열을 부등호와 비교..
[백준] 14889번 : 스타트와 링크 - JAVA [자바]
2024. 1. 1. 13:53
Algorism/백준
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 간단한 조합 문제이다. 하지만 알고리즘을 안푼지 2개월쯤 되니 조합 작성 코드를 까먹어서 자괴감이.... 그래서 단순히 Git에 기록을 남기는 것이 아니라 느낀점을 블로그에 남기기로 했다. 조합 코드는 아래와 같다. static void combi(int idx, int count) { if(count == 몇개뽑을건지 숫자 결) { System.out.println(Arrays.toString(visit)); ..
이진 탐색 트리 (Binary Search Tree)
2022. 9. 5. 21:37
CS/DataStructure
이진 탐색 트리(Binary Search Tree)란? 각 노드에 중복되지 않는 키(Key)가 있다. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 이진 탐색 트리의 특징 이진 탐색 트리는 기존 이진트리보다 탐색이 빠릅니다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 가집니다. 이진 탐색 트리의 탐색 과정을 한번 보시죠! 루트 노드의 키와 찾고자 하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료합니다. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 ..
Binary Tree(이진 트리)와 그종류
2022. 8. 31. 20:51
CS/DataStructure
Binary Tree 란? 모든 노드가 정확하게 두개의 서브트리를 가지고 있습니다. 서브트리는 공백이 될 수 있습니다. 노드의 유한 집합으로서 공백이거나 루트와 두 개의 분리된 이진트리인 경우 왼쪽 서브트리와 오른쪽 서브트리로 구성 root가 0이 아닌 1에서 시작할 때, i 번째 노드에 대해서 parent(i) = i/2 , left_child(i) = 2i , right_child(i) = 2i + 1 의 index 값을 갖습니다. 위의 그림을 보겠습니다! 두개의 서브 트리가 모두 공백인 리프 노드 - D, H, F, I 공백이 아닌 서브 트리를 하나씩 가지고있는 노드 - E, G 노드 E는 공백 왼쪽 서브트리와 오른쪽 서브트리 H를 가지고 있으며 노드 G는 왼쪽 서브트리I와 오른쪽 공백 서브트리를 ..