JAVA 알고리즘

스택 큐 기본 함수

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.사용하는 경우: 두

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

백트래킹(Backtracking)해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아갑니다.즉, 코딩에서는 반복문의 횟수까지 줄일 수 있으므로 효율적입니다.이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로

부분 반복 문제 (Overlapping Subproblem)최적 부분 구조 (Optimal Substructure)▶ 부분 반복 문제 (Overlapping Subproblem)동적계획법의 등장은 피보나치 수열이라고 한다. 피보나치 수열은 대표적인 재귀함수로, 아래와

그리디(Greedy) 알고리즘탐욕법이라고도 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.루트 노드부터 시작해서 거쳐 가는 노드 값

💡 이분 탐색(Binary Search)이란?‘정렬된 배열’에서 ‘특정 값’을 찾는 알고리즘을 의미합니다.이진탐색은 탐색 범위를 절반씩 줄여나가기 때문에 선형탐색에 비해 빠른 속도를 보장합니다. 하지만 배열이 정렬되어 있어야 한다는 조건이 필요하기 때문에 배열이 정렬

투포인터 알고리즘에 대해 알아봅시다. 리스트에 순차적으로 접근하여 두 개의 위치를 기록하며 처리부분 연속 수열 문제에 사용시간 복잡도 O(N)으로 처리 가능

선순위 큐의 경우 들어가는 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조입니다.

다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점 방문)해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면

완전 탐색이라는 이름에서도 알 수 있듯이 하나부터 열까지 모든 경우를 다 탐색하는 알고리즘이다.전체 탐색에는 기본적으로 3가지 방법이 존재합니다.순차 탐색 - 선형 구조를 순차적으로 탐색DFS(깊이 우선 탐색) - 비선형구조를 점점 더 깊게 깊이를 우선적으로 탐색하는

완전탐색(exhaustive search)① 완전탐색이란?▷ '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 뜻한다.▷ 완전 탐

양수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상 단에서 시작하여 우하단까지 이동한다• 이동 방법 (제약조건)– 오른쪽이나 아래쪽으로만 이동할 수 있다– 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다• 목표: 행렬의 좌상단(1, 1)에서 시작하여 우하단(n,

최장 공통부분 수열은(LCS, Longest Common Subsequence) 여러 개의 수열이 주어졌을 때 두 수열의 부분 수열이 되는 수열 중 가장 긴 수열을 찾는 방법이다.구하는 방법은 하나의 수열을 순서대로 다른 수열의 모든 문자와 비교하여 같은지 비교하는데,

본래 수열에서 일부 숫자를 지워 만들 수 있는 수열 오름차순으로 증가하는 부분 수열 중에서 가장 긴(원소의 개수가 많은) 수열dp를 이용한 방법은 수열의 값을 하나씩 비교하기 때문에 시간 복잡도가 O(n^2)이다. dp를 이용하여 최장 증가 부분 수열의 길이를 찾는

수열 An에 대해서, 구간 1, 1의 합, 구간 1, 2의 합, 구간 1, 3의 합, ..., 1, n의 합을 누적 합이라고 한다.

HashSet이란?HashSet set = new HashSet<>();//초기값 지정 가능HashSet set = new HashSet<>(Arrays.asList("tiger", "lion", "fox")); 요소 추가set.add("rabit")크기se

자주 사용하는 코딩테스트 문법 정리

[Gold IV]1976번:여행 가자 - 유니온 파인드(Union-Find)를 이용하여 풀 수 있습니다.이 개념을 이해하고 부모 값(대푯값)을 찾아야합니다.

🔗 링크https://www.acmicpc.net/problem/1904📖 문제📕풀이 방법Dynamic Programming 은 특성상 2가지의 방법으로 해결할 수 있다.Top DownBottom Up✅점화식문제요약수열을 만들기 위해서 주어지는 수가 2가

이 문제를 만족시키기 위해서 어떻게 해야할지부터 생각해보자. 다솜이가 처음 얻은 듣표수를 a라고 하겠다. 그럼 그 나머지 득표수들을 -시키면서, a를 +시켜나갈 때 나머지 득표수 중 가장 큰 득표수보다 a가 커지면 된다. 그렇다면 중요한 요소는 나머지 득표수 중 가

나중에 들를 도시중에 현재 도시보다 싼 곳을 찾기1-1. 그런 도시가 있다면, 해당 도시까지 필요한 연료만 구매1-2. 그런 도시가 없다면, 현재 도시에서 목적지까지 필요한 모든 연료 구매

분모 값과 분자 값의 합을 T 라고 할 때 다음과 같은 규칙이 생긴다.그리고 대각선 칸의 개수는 T - 1 개다.파란색 ( T 가 짝수, 또는 대각선 칸의 개수가 홀수 ) 일 때는 왼쪽 아래에서 오른쪽 위 방향 ( ↗︎ ) 으로 진행되고,빨간색 ( T 가 홀수, 또는

각 칸이 흰색 또는 검은색으로 칠해진 커다란 판에서 임의의 위치부터 8x8크기로 잘라 체스판을 만든다. 그 중 가장 적은 칸을 칠하여 체스판을 만들고자 할 때, 칠해야하는 최소값을 구하는 문제. 하나하나 비교해서 풀이위 처럼 NxM의 배열에서 무작위 8x8크기의 배열을

https://www.acmicpc.net/problem/10591059번: 좋은 구간유형수학, 배열해설 좋은 구간이란 4 8 13 24 30이 주어지고 n이 10일 때 8과 13 사이에 10이 있으므로 10을 포함하는 모든 구간을 말한다. 이때 8과 13은

백준의 N과 M (1) 문제다.간단하게 문제를 정리하자면, 자연수 N과 M이 주어지는데, 숫자 1부터 N까지 중복 없는 M개의 요소를 가진 수열을 구하는 문제다. N은 4이고, M은 3라는 가정 하에, 코드를 작성하기 이전 머릿속으로 한 번 어떻게 백트래킹으로 이 문제

dp배열: 각 계단의 최댓값을 표현하는 배열arr배열: 입력값 if문으로 dp 2를 해준 이유는 어떠한 값이더라도 계단이 2개 이상이라면 2번째 계단의 최댓값은 첫 번째 계단과 2번째 계단을 더한 값과 같기 때문입니다.

www.acmicpc.net/problem/1003DP 재귀 풀이법재귀호출을 할 때 이미 한 번 탐색(연산)했던 값이 있다면 또다시 연산하는 것이 아니라 이미 계산된 값을 재사용하여 반복적인 연산과정을 줄이는 방법이 DP풀이의 기초다.이전 글에서는 피보나치 수를 배열에

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.2의 경우엔 2 2→1 1번 만에 만들 수 있다.10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수

https://www.acmicpc.net/problem/1541알고리즘 접근 방법 '덧셈 부분을 먼저 계산 하는 것' 뺄셈기호(-)를 중심으로 먼저 문자열을 분리해준 뒤, 각 분리된 문자열안에 있는 정수끼리 더해준다. 그 다음 분리된 문자열들을 뺄셈을 해주면

상 하 좌 우는 기존에 쓰던 배열과 똑같고,뒤에오는 4개가 대각선을 탐색한다.arrx 기준 대각선은 순서대로상좌(위쪽 왼쪽 대각선) arr1상우(위쪽 오른쪽 대각선) arr1하좌(아래쪽 왼쪽 대각선) arr-1하우(아래쪽 오른쪽 대각선) arr-1

<문제 분석>1\. 정점은 집이다. 상하좌우로 탐색해서 1이면 다시 탐색을 계속한다.2\. 총 단지 수와 각 단지마다 집의 개수를 출력한다.<문제 풀이>1\. 메인함수에서 for문으로 dfs 함수를 호출한다.2\. 방문처리 된 곳이면 스킵하다가 새로운 1을

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또

난이도실버 1문제https://www.acmicpc.net/problem/1149풀이테이블 정의하기dpi = i번째 집일 때 집을 칠하는 최소 비용점화식 찾기i번째 집이 빨강일 때(0),i-1번째 집이 초록집이거나 파랑인 경우에 최솟값과 빨강일 때의 값을 더해

DP를 이용하여 최댓값을 구한다.이전까지의 연속합+현재 값과 현재의 값을 비교하여, 둘 중 큰 값을 dp에 저장한다.dp에 저장된 최댓값을 리턴한다.더할 때 연속으로 포도주를 마시면 안 된다는 조건이 추가된다면, 현재 위치에서의 최대값을 구할 때 고려해야 합니다. 연속

✏️ 문제풀이1\. 테이블 정의하기점화식길이가 i이고 끝자리가 0이거나 9인 경우에는 길이가 i-1이고 각각 끝자리가 1, 끝자리가 8인 경우만 가능하므로 예외로 반복문에서 빼서 계산해줍니다.전체코드

124KB 300ms메모리 제한 : 128 MB 메모리초과 오류✅String.valueOf(i).contains("666") ❎String.valueOf(i).matches(".666.”)

https://www.acmicpc.net/problem/15650 14156KM 124MB백트래킹의 두 번째 문제현재 arr 배열에 i가 담김과 동시에 다음 재귀에서는 i값보다 1이 큰 수부터 탐색하도록 함과 동시에 depth 또한 1 증가시키면서 재귀호출을

날짜의 끝 부터 첫 날 까지 거꾸로 DP 배열을 구해나간다.배열 DP[i]는 날짜i부터 상담을 했을 때 벌 수 있는 돈의 최댓값이다.

백준 1629번 곱셈은 실버 1 난이도의 수학 및 분할 정복 문제이다. 이 문제에서는 자연수 A, B, C가 주어진다. 0.5초 시간제한 내에 (A^B) % C를 구하면 된다.

https://www.acmicpc.net/problem/10942펠린드롬이란 앞에서 읽든, 뒤에서 읽든 같은 단어를 말한다.반복문을 돌면서 직접 비교할 수도 있지만 질문의 개수를 보면 1,000,000 으로 시간초과를 피해 다이나믹 프로그래밍으로 풀어야 한다

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

스도쿠 - 같은 행과 열에 겹치지 않으면서 3×3 행렬 안에서도 겹치면 안된다. 즉, 이 규칙을 토대로 조건문가로에 겹치는 숫자가 있는지, 세로에 겹치는 숫자가 있는지, 3X3크기의 박스에 겹치는 숫자가 있는지를 검사

백준 1025 자바 java 제곱수 찾기2022.01.12 11:52Alogorithm/Brute Force문제 링크: https://www.acmicpc.net/problem/10251025번: 제곱수 찾기첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의

Brute : 무식한Force : 힘완전 탐색이라는 이름에서도 알 수 있듯이 하나부터 열까지 모든 경우를 다 탐색하는 알고리즘이다.완전탐색 알고리즘을 사용하여 모든 케이스들을 생각해내야 한다.조건 1. 100이면 count 0조건 2. 리모콘이 고장 나지 않았으면, 배

등차수열에 대한 이해 : 1,3,5,7,9,⋯처럼 연속한 두 항의 차가 일정한 수열을 등차수열이라고 한다. 

이항계수란 주어진 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 개수를 의미한다.

더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.가장 처음아기 상어의 크기는 2이다.아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고

2669\_숫자고르기 - 바로가기첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다.사이클 발생 여부는 DFS를 사용하여 출발 숫자 -> arr\[출발 숫자] -> arr\[

22251번: 빌런 호석 📢 1부터 N까지의 수 중 변경할 숫자를 하나 정하고, 변경할 수 있는 갯수 P 안에 변경할 수 있다면, count를 증가시킨다.

[Gold IV]1987번:알파벳 - 백트래킹을 이용한 DFS탐색 문제이다.

[Gold V]7490번:0 만들기:알파벳 - 모든 경우의 수를 생성하고 검사하는 브루트 포스(Brute Force) 방식

[Gold IV]1863번:스카이라인 쉬운거 - 고도가 같다면 그대로 가면되고, 고도가 낮다면 건물의 개수가 추가되어야 한다.

[Bronze V]1676번:팩토리얼 0의 개수 - 팩토리얼에서 0의 개수는 5의 차수

[Bronze V]10951번:A+B - 4 -EoF(End of File)

[Bronze I]3226번:전화 요금 - 7:00부터 19:00까지는 1분에 10원,19:00부터 7:00까지는 1분에 5원입니다.

[Gold IV]5710번:전기 요금

[Silver IV]1331번:나이트 투어 - 나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며 나이트는 체스판에서 L자 모양으로 이동할 수 있으며, 이동 거리가 (2,1) 또는 (1,2)인 경우에만 이동이 가능합니다.

[Gold IV]백준 1027번:고층 건물 - 브루트포스 알고리즘

[Gold IV]백준 4197번:불!

[Gold IV]백준 13144번:List of Unique Numbers

[Gold IV]백준 2179번:비슷한 단어

[Gold III][JAVA]백준 1238번:파티

5를 예시로 들어보자.5를 1번 사용55를 2번 사용55, (5 \* 5), (5 / 5), (5 - 5), (5 + 5)55, 25, 1, 0, 105를 3번 사용555, (55 \* 5), (55 / 5), (55 - 5), (55 + 5)((5 5) 5), ((5

메모리를 사용해서 중복 연산을 줄이고 중복 연산을 줄여서 수행 속도를 개선한다.DFS/BFS로 풀 수 있지만 경우의 수가 너무 많은 문제5줄짜리 삼각형이라면 DFS로 풀어도 괜찮지만 500줄 삼각형이라면 경우의 수가 많이 지장이 생긴다.최적의 조합을 dp배열에 넣기 찾

이차원 배열 정렬 Lambda 사용 - Java 8이상 Comparator.comparing() 사용