'알고리즘' 태그의 글 목록

[코딩테스트] Java 첫 코딩 테스트 시작 시 문법 정리

2023.12.18 Updated 자바 코딩 테스트를 준비하면서 필수적으로 알아야할 문법을 정리하고 있습니다. 최대한 간략하게 예시와 함께 설명하는 형태로 정리중이며, 속도 등 같은 기능을 수행하는 기술 간 차이점에 대한 증명 자료는 따로 첨부하지 않았습니다. 참고문헌 https://devdocs.programmers.co.kr/references/java/docs/api/index.html Overview (Java SE 11 & JDK 11 ) This document is divided into two sections: Java SE The Java Platform, Standard Edition (Java SE) APIs define the core Java platform for general-..

개인 공부/코딩 테스트^ 2023. 12. 20. 08:42

[알고리즘] 최장 공통 문자열(LCS : Longest Common Substring) 알고리즘

LCS(Longest Common Substring)란 최장 공통 부분 문자열은 두 문자열이 주어졌을 때, 두 문자열에 포함된 가장 긴 공통 부분 문자열을 찾는 문제입니다. 유사한 문제로 최장 공통 부분 수열(LCS: Longest Common Subsequence) 있고, 오늘은 최장 공통 부분 문자열에 대해서 알아보도록 하겠습니다. 예를 들어 ABCDE, BCCAR 와 같은 두 개의 문자열이 주어졌다고 가정해봅시다. ABCDE는 A, AB, ABC, .., B, BC, .., ABCDE등 다양한 부분 문자열로 나타낼 수 있습니다. 이 때, ABCDE 와 BCCARD 각각이 가지는 부분 문자열 중 동일하게 포함하는 가장 긴 부분 문자열을 찾는 문제입니다. 풀이 일반적인 최장 공통 부분 문자열은 2차원 ..

개인 공부/코딩 테스트^ 2023. 10. 30. 09:12

[Baekjoon] 백준 3055 탈출 (G4 / BFS, 던전) - Java

링크 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 해석 맵 크기 : R * C 비어있는 곳 : . 물이 차있는 곳 : * 돌 : X 비버 : D 고슴도치 : S 고슴도치가 비버에게로 도착해야 함 매턴 물은 인접한 빈칸을 채움 고슴도치는 물이 있는 곳을 건널 수 없음 물은 돌이나 비버의 집을 채울 수 없음 - 입력 첫 번째 줄 : R C # 세로 가로 나머지 줄 : 던전 정보 - 출력 건널 수 있다면 숫자 건널 수 없다면 KAKTUS 풀이 & 코드 ..

개인 공부/코딩 테스트^ 2023. 4. 10. 17:36

[알고리즘] 이항 계수, 파스칼의 삼각형

문제를 풀기 위한 개념 정리 이항 정리 각 항의 계수 값을 구하는 정리를 의미 이항 계수 다항식을 전개했을 때 각 항의 계수를 의미 $(a+b)^{n}$를 전개 했을 때 나오는 임의의 항 $Sx^{n-a}y^{n-b}$ 에서 $S$가 계수 이항 계수 구하기 이항 계수를 구하는 방법은 1) 경우의 수(조합)을 이용한 방법 2) 파스칼의 정리(삼각형)을 이용한 방법 등이 있음 조합을 이용한 풀이 조합을 이용한 풀이 $_{n}C_{r}$는 $_{n-1}C_{r-1} + _{n-1}C_{r}$로 분해할 수 있음 -> 중복이 발생함 -> 12!을 넘어가면 오버플로우가 일어날 수 있음 - 연산 횟수 10! == 360만 11! == 4000만 12! == 1억 이상 - 조합 개념 https://angelplayer..

개인 공부/알고리즘 2023. 4. 7. 16:36

[SWEA] 활주로건설 (D0 / 구현, 완전탐색) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 N * N 크기의 활주로 건설 셀의 숫자는 지형의 높이를 의미 가로 또는 세로로 활주로 건설이 가능한지를 확인하는 문제 활주로는 높이가 같은 경우에만 건설이 가능하며, 높이 다른 경우 경사로를 설치하여 건설이 가능함 경사로는 높이가 1이고 길이가 X임 경사로는 겹쳐서 만들 수 없고, 눕힐 수 없음 - 입력 첫 번째 줄 : N X # N=활주로 크기, X=경사로 길이 나머지 줄 : 지..

개인 공부/코딩 테스트 2023. 4. 6. 10:37

[Baekjoon] 백준 1520 내리막길 (G3 / DP) - Java

링크 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제 해석 왼쪽 위 (0, 0)에서 시작하여, 오른쪽 아래(N-1, M-1)에 도착해야한다. 이때 이동하는 경로는 현재 있는 위치보다 낮은(숫자가 작은) 곳만 가능하다. 갈 수 있는 경로의 개수를 구하시오. 아이디어 갈 수 있는 모든 길을 찾아야하므로 dfs를 사용해야 합니다. 단 map의 크기가 500*500이므로 단순 dfs를 사용해서 탐색하기에는 시간초과가 날 가능성이 높습니다. 따라..

개인 공부/코딩 테스트^ 2023. 3. 30. 14:33

[알고리즘] 이분(이진)탐색

이분 탐색 배열 등 자료를 두 부분으로 쪼개어 탐색하는 방법 특정 값 또는 자료가 존재하는지를 탐색할 때 사용함 이분 탐색을 위한 배열은 정렬되어 있어야 함 - 로직 1) 탐색 배열의 내 중간 인덱스( (시작 인덱스 + 끝 인덱스) / 2 )를 구함 2) 배열[중간 인덱스]에 위치한 값과 찾으려는 값 비교 3) 비교 결과를 통해 반복 여부 결정 3-1) 배열 값과 같으면 중간 인덱스 반환 3-2) 배열 값이 작으면 "중간 인덱스 + 1"를 시작 인덱스로 지정 3-3) 배열 값이 크면 "중간 인덱스 - 1"를 끝 인덱스로 지정 4) 인덱스 범위가 하나가 될 때까지 1) 2) 3)을 반복 -> 만약 인덱스 범위가 1인데 값이 다르다면 해당 값은 존재하지 않는 값 코드 public class 이분탐색_기본 {..

개인 공부/알고리즘 2023. 3. 11. 09:00

[SWEA] 3289 서로소집합 (D4 / 서로소) - Java

링크 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 해석 - 문제 해석 서로소 테스트 결과로 1연산을 띄워쓰기 없이 출력 - 각 테스트 케이스 별 입력 첫 번째 줄 : N M # N : 자연수의 최대 값 / M : 연산의 개수 나머지 줄 : M번의 연산 연산이 0로 시작하면 합집합 연산이 1로 시작하면 확인 연산 코드 import java.io.*; import java.util.*; public class Solution { static..

개인 공부/코딩 테스트 2023. 3. 7. 09:09

[알고리즘] 최소 신장 트리 (크루스칼, 프림 알고리즘)

최소 신장 트리 (MST) ※ 일반적으로 그래프의 모든 정점이 연결되어 있다고 가정 - 신장 트리 : 모든 정점이 연결되는 트리 - 최소 신장 트리 : 신장 트리 중 사용된 간선들의 가중치가 가장 작은 간선으로만 연결된 트리 - V : 정점 - E : 간선 - 최소 신장 트리의 조건 무방향 가중치 합이 최소 간선의 개수는 $V-1$개 사이클이 없어야 함 - 활용 도시간 비용을 최소화 하는 문제 등에서 사용함 최소 신장 트리를 만드는 방법은 크루스칼과 프림 알고리즘이 있음 크루스칼 알고리즘 (Kruskal Algorithm) - 특징 간선 리스트를 사용 간선을 가중치 기준으로 정렬이 먼저 이뤄저야 함 (간선이 적으면 유리) 순환 여부는 서로소를 통하여 검사함 (매 간선 선택마다 정점의 대표를 확인) 그리디..

개인 공부/알고리즘 2023. 3. 1. 15:00

[알고리즘] 서로소 집합

서로소 서로소 집합 서로 중복된 원소가 없는 집합을 의미 == 교집합이 없는 집합 집합에 속한 특정 멤버(대표자)를 통해 집합을 구분 대표자는 어떤 데이터가 되든 상관이 없음 하나의 집합에는 오로지 하나의 대표자만 가질 수 있음 서로소 집합 연산 1) init : 초기화 2) union : 두 개의 집합을 하나의 집합으로 결합 3) find : 집합 내의 대표자를 찾음 서로소의 최적화 - Rank 사용 기본 서로소 함수에서는 부모를 찾을 때 find의 재귀가 여러 번 발생함 -> 두 서로소를 결합할 때 더 낮은 트리를 더 높은 트리의 자식으로 결합하면 효율성을 높일 수 있음 (데이터에 따라서 사용하지 않을 때 더 빠른 경우가 있음) - Path 사용 find함수의 재귀가 발생하여 부모의 결과를 찾으면, ..

개인 공부/알고리즘 2023. 2. 28. 08:11

[알고리즘] DFS

DFS 개념 DFS : 깊이 우선 탐색 (==장자 우선 탐색) BFS : 너비 우선 탐색 완전 탐색 기법 중 하나 스택(재귀)를 사용함 재귀는 부를 때마다 함수를 시스템 스택에 쌓기 때문에 결국 스택을 사용한 것과 동일한 효과를 가져옴 시작지점에서부터 끝점까지 이동하면서 모든 경우의 수를 탐색 -> 저렴한 비용을 뽑는 문제에서 사용함 앞선 BFS 정리 자료에서 보셨겠지만, DFS는 BFS와 서로 상반되는 개념입니다. DFS는 탐색 시 같은 level에 위치한 노드들을 먼저 탐색하는 BFS와 달리, 한쪽 방향으로 깊이 탐색한 후, 거슬러 올라가면서 나머지를 탐색하는 알고리즘입니다. 그래서 이를 첫번째 자식을 가장 먼저 생각하는 장자 우선 탐색이라고 생각하셔도 좋을 것 같습니다. BFS : 2 -> 7 ->..

개인 공부/알고리즘 2023. 2. 24. 15:07

[알고리즘] BFS (너비 우선 탐색)

BFS 개념 BFS : 너비 우선 탐색 DFS : 깊이 우선 탐색 그래프를 탐색하는 기법 BFS 구현을 위해서는 Queue를 사용 BFS는 너비 우선 탐색 기법으로 깊이 우선 탐색인 DFS와 상반되는 개념입니다. DFS와 BFS는 모두 그래프를 탐색하는 기법입니다. 가령 위와 같은 트리가 존재한다면, BFS는 위에 위치한 노드부터 순차적(Level)으로 탐색을 진행합니다. BFS : 2 -> 7 -> 5 -> 2 -> 6 -> 9 -> 5 -> 11 -> 4 DFS : 2 -> 7 -> 2 -> 6 -> 5 -> 11 -> 5 -> 9 -> 4 너비 탐색을 수행은 위에 작성된 것 처럼 상위 Level에 위치한 노드 (Lv 0 : 0 | Lv 1 : 7, 5 | ...)들이 먼저 탐색되는 것을 볼 수 있습..

개인 공부/알고리즘 2023. 2. 15. 08:45

[알고리즘] 재귀

재귀는 알고리즘이 아님! -> 재귀는 for문과 같은 단순한 프로그래밍 작성 방법 재귀는 크게, 선형 재귀와 비선형 재귀로 나뉨 선형 재귀는 한 번 호출에 자신을 한 번 부름 -> Linear한 결과를 도출할 수 있음 비선형 재귀는 한 번의 호출에 자신을 여러 번 부름 재귀 기본 recursive() { // basis part if () { return }; // 재귀(가지)의 끝을 알림, 종료 조건 // inductive part recursive(); // 재귀 호출 } -> 함수 내에서 자기 자신을 한 번 호출하므로 선형 재귀라고 할 수 있음 비선형 재귀 횟수 구하기 - 출력 횟수 : 갈래(한 번 호출마다 자신을 부르는 횟수) ^ 반복 횟수 - 예제 코드 public class Recursive ..

개인 공부/알고리즘 2023. 2. 13. 10:16

[알고리즘] 순열, 조합, 부분 집합

개념 정리 순열 (P : Permutation) 순서가 있음 : 금고의 각 자리 비밀번호는 순서가 있다! keyword : 서로 다른, 나열하다 A와 B, B와 A는 서로 다른 것이다. (비밀번호 486과 468은 서로 다른 비밀번호이다.) 수학 공식 : $_nP_r = \frac{n!}{(n-r)!}$ $_4P_2 = \frac{4!}{(4-2)!} = \frac{4 * 3 * 2 * 1}{2* 1}=12$ 조합 (C : Combination) 순서가 없음 : 콤비네이션 피자는 여러 재료의 조합으로 된 피자이다! (재료의 순서가 없음) keyword : 동시에 꺼내다, 선택하다 A와 B, B와 A는 같은 것으로 취급함 수학 공식 : $_nC_r = \frac{_nP_r}{r!}=\frac{n!}{(n-..

개인 공부/알고리즘 2023. 2. 12. 12:28

[알고리즘] 구간 합 (부분 합)

구간 합 시간 복잡도를 더 줄이기 위해 사용하는 특수 알고리즘 S[i] = A[1] + .. + A[i] 합 배열 만드는 방법 합 배열 S[]를 만들기 위해서, 첫 번째 배열의 값은 0으로 만들고, 이후 값들은 이전 요소까지의 합 ( S[i -1] ) + 현재 요소 ( A[i] )를 더합니다. S[0] = A[0] S[i] = S[i-1] + A[i] i에서 j까지 구간 합 구하는 공식 3 ~ 4까지의 합은 3+4입니다. 이때, S[4]는 1+2+3+4이기 때문에 S[2] (1+2)을 뺀다면 동일한 결과를 얻을 수 있을 것입니다. 즉 i부터 j번째까지 합 구하는 방법은 S[j] - S[i -1] 이라고 볼 수 있습니다. 이렇게 구간 합을 사용한다면 시간 복잡도를 효율적으로 변경할 수 있습니다. 코드 //..

개인 공부/알고리즘 2023. 2. 10. 11:03

[알고리즘] 소수 (Prime)

소수 구하기 - 숫자 N의 소수 판정 방법 1 ~ $\sqrt{N}$까지 N을 나누어 떨어지게 하는 수가 있는지를 확인 - 에라토스테네스의 체 사용하기 각 수는 임의의 값 n * n 제곱하여 나오는 n보다 큰 값을 ( i * i 5의 경우 5*2 / 5*3 / 5*4 / 5*5 / ... 로 진행되며, -> 이때 2, 3, 4(2,2)는 앞선 값으로 인해서 소수가 아니라고 처리되기 때문에 10,000까지의 소수의 개수 : 1,229개 소수 구하는 코드 (Java) private static boolean isPrime(int num) { if..

개인 공부/알고리즘 2023. 1. 27. 11:25

[알고리즘] 2차원 배열의 회전

다음과 같은 N*N 크기의 2차원 배열을 시계방향(오른쪽)으로 90도 회전한다면 아래 그림과 같습니다. 혹시 위 사진에서 규칙성을 찾으셨나요? 해당 배열을 인덱스로 본다면 좀 더 쉽게 규칙성을 찾을 수 있습니다. 행의 규칙성 원본 배열과 회전 후 배열을 인덱스로 표현한다면 위와 같습니다. 잘 살펴보면 각각 기존의 열번호가 행번호로 적용되는 모습을 볼 수 있습니다. 행렬을 한 번 더 회전시킨다면 규칙성이 적용된다는 것을 더 쉽게 이해할 수 있는데요. 모든 요소들의 공통적인 열번호였던 4가 각각 행번호로 적용된 것을 확인할 수 있습니다. -> 회전된 행의 인덱스 == 기존의 열 인덱스 열의 규칙성 열은 행보다는 조금(?) 어렵습니다. 회전한 행이 기존의 열을 사용하였듯이, 회전한 열도 기존의 행을 사용합니다..

개인 공부/알고리즘 2023. 1. 10. 16:19

AngelPlayer`s Diary