baekjoon

입력으로 주어지는 간선은 양방향이다. -> 인접행렬 사용인접행렬배열의 인덱스 i,j에서 i와 j가 서로 바뀌어도 값이 동일한 행렬

가장 간단한 방법으로 Array.sort() 메소드 사용Array.sort() : 자바에서 기본적으로 제공되는 메소드, 자동으로 ()에 들어가는 해당 배열이 정렬시간복잡도는 평균 O(nlogn)이며, 최악의 경우 O(n2)임입력 방식 2가지로 풀이 => Scanner,

시간초과로 실패dual-pivot Quicksort 알고리즘을 사용하는 Array.sort()를 사용했지만, 평균 시간복잡도가 O(nlogn)이고 최악 시간복잡도는 O(n2)이기 때문에 퀵정렬이라고 무조건 좋은 게 아니였다.=> O(n^2)이면 시간초과가 되는 문제다.

커서를 기준으로 두 개의 stack을 사용커서 기준 왼쪽: stack, 커서 기준 오른쪽: tmp

()(((()())(())()))(())에서 '('가 나온 후 ')'가 나오면 한 번 잘린 것이기 때문에 layer를 -1, result에 layer를 더하기'('이 나오면 layer를 +1')'이 나온 후 ')'가 나오면 가장 상위층의 막대기가 끝나는 것이기 때문에

처음엔 이 문제를 꼭 스택을 써서 풀어야하나 생각이 들었지만, 코드로 직접 모두 구현하기에는 복잡한 부분이 많고 예제처럼 수열 A가 9 5 4 8과 같이 큰 수가 가장 앞에 온다면 시간초과가 발생하게 된다.이 부분을 해결하기 위해 stack을 임시 저장 공간으로 사용했

유클리드 호제법을 사용하여 풀이최대공약수(Greatest Common Divisor): a를 b로 나눈 나머지(단, a>b) = ra와 b의 최대공약수 = b와 r의 최대공약수b를 r로 나눈 나머지 r1을 구하고, 다시 r을 r1로 나눈 나머지를 구하는 과정을 반복해

유클리드 호제법 사용설명은 다음 링크 참고유클리드 호제법

소수 판별법: N이 주어졌을 때 N을 2부터 N-1까지의 모든 수로 나누어봐 나누어떨어지는 수가 하나라도 존재하면 소수 아님=> 시간복잡도가 O(N)이기에 비효율적알고리즘 개선: 제곱근까지만 확인하면 됨=> 시간복잡도가 O(N의 2분의 1승)에라토스테네스의 체여러 개의

이 문제는 M부터 N까지의 숫자 사이의 소수들을 모두 출력해야하기 때문에 에라토스테네스의 체를 사용해 N보다 작은 소수들을 구한 다음, M보다 큰 소수들만 출력하는 방법으로 풀었다.

이 문제의 정수 n의 크기는 최대 1000000이기 때문에 많은 양의 소수를 구하게 될 것을 예상되어, 에라토스테네스의 체 알고리즘을 이용했다.처음엔 입력받은 정수 n의 소수를 잘 구해놓고, 소수 두 개를 더해 정수 n이 되는 가장 작은 소수와 가장 큰 소수를 출력하는

바로 전 포스팅의 '팩토리얼 0의 개수' 문제와 유사하다.조합 공식은 팩토리얼 값으로 이루어져 있기 때문에 팩토리얼 0의 개수 문제를 이용하면 쉽게 풀 수 있다. 조합 공식을 아래와 같다.즉, n!, (n-m)!, m!의 2와 5의 승수를 구하면 0의 개수를 구할 수

큐를 사용해 1부터 N까지의 수를 add 한 후poll해서 K의 배수가 아닌 값은 다시 add하고,K의 배수를 뽑은 값만 sb에 추가한다.

최대공약수(GCD)를 찾기 위해서 유클리드 호제법을 사용했다.이전 최대공약수 문제를 풀 땐 main 안에서 while문을 사용해 나머지가 0이 될 때 까지 작업을 반복했지만,이번 풀이에서는 최대공약수를 찾는 재귀 형태의 메소드를 작성했다.유클리드 호제법에 대한 설명은

수빈이의 위치 S에서 각 동생들의 위치까지 모두 도착할 수 있으려면 D값은 S-각 동생들의 모든 위치의 약수여야한다. 이처럼 공통되는 수 들의 최댓값을 구하는 문제는 최대공약수를 구하면 된다.최대공약수는 유클리드 호제법을 사용해 구하였다.유클리드 호제법에 대한 설명은

2진수 ➡️ 8진수2진수를 split("")을 사용해 String형 배열에 한 글자씩 삽입String형 배열을 int형 배열로 형변환하여 queue에 해당 배열 원소들 삽입입력받은 2진수를 3칸씩 나누었을 때 딱 나누어 떨어지지 않는다면, 가장 앞자리 1~2칸은 0을

처음엔 1373번 '2진수 8진수' 문제를 풀었을 때 처럼 진수변환하는 기능을 구현하여 변환하려 시도했다.👉 1373번 2진수 8진수 포스팅8진수 ➡️ 2진수 변환 과정위의 코드로 프로그램은 잘 돌아갔지만, 시간초과로 오답이 떴다.찾아보니 진수 변환을 구현하지 않아도

테이블 정의점화식 찾기초기값 정하기dpi = 2i 크기의 직사각형을 12, 2\*1 크기의 타일로 채우는 방법의 수dpi = dpi-1 + dpi-2dp1 = 1dp2 = 2

이 문제는 완전 탐색 문제로, 부르트 포스 기법을 이용해 풀었다.모든 경우의 수를 전부 다 체크해서 정답을 찾는 방법아래 5가지 방법으로 풀이 가능반복문 or 조건문을 활용해 모두 테스트n개의 원소 중에서 r개의 원소를 중복 허용 없이 나열하는 방법2진수 표현 기법을

이 문제는 완전 탐색 문제로, 부르트 포스 기법을 이용하여 풀었다.👉 완전탐색 문제 설명 포스팅구현 아이디어는 다음과 같다.이중배열로 입력받기모든 인접한 행과 열의 사탕끼리 색을 바꾸기(바꾼 후 원상복구)바꾼 것 중 가장 긴 수열을 찾아 반환

이 문제는 완전 탐색 문제로, 부르트 포스 기법을 이용하여 풀었다.👉 완전탐색 문제 설명 포스팅구현 아이디어는 다음과 같다.이중배열로 입력받기모든 인접한 행과 열의 사탕끼리 색을 바꾸기(바꾼 후 원상복구)바꾼 것 중 가장 긴 수열을 찾아 반환

이 문제는 완전 탐색 문제로, 예제 4번을 보면 알 수 있듯이, 15, 28, 19의 최대공배수가 엄청 큰 수는 아니기 때문에 1씩 더해가며 확인하는 브루트포스 기법을 이용하여 풀었다.👉 완전탐색 문제 설명 포스팅구현 아이디어는 다음과 같다.연도, e, s, m을 0

이 문제는 숫자를 전부 눌러서 N과 일치할 때 최소인 값을 찾는 문제이다.구현을 위해 다음의 세 가지 경우를 고려해야한다.N이 100일 때는 바로 0 출력\+, - 버튼만을 사용숫자 버튼을 사용해 근사치까지 누른 다음 +, - 사용2번은 N-100으로 구할 수 있으며,

그래프는 인접행렬로 구현DFS는 재귀, 스택 두 가지 방법 모두 구현BFS는 큐 사용 방법으로 구현

이 문제는 그래프의 연결 요소를 찾는 문제이므로 BFS로 풀었다.(DFS로도 풀기 가능)💡 연결 요소(Connected Component)그래프에서 어떤 정점으로부터 다른 정점으로 갈 수 있는 경로들의 집합연결 요소들은 그래프의 최대로 연결된 부분 그래프가 됨그래프에

💡 이분 그래프인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프이분 그래프인지 확인하는 방법BFS, DFS로 탐색하며 정점을 방문할 때마다 자신과 인접한 정점은 자신과 다른 색으로 칠함탐색을 진행할 때 자신과 인접한 정점의

모든 노드를 방문하여 조건에 맞는다면 탐색하는 알고리즘을 작성하여야 하기 때문에 DFS 사용구현 아이디어는 다음과 같다.1\. 지도를 띄어쓰기 없이 입력받기 처리 (인접행렬)2\. 인접행렬을 모두 돌며 1일 때 DFS 수행3\. DFS 메소드 실행될 때마다 단지 수 +

문제의 제목 그대로 미로 탐색이기 때문에 0,0에서 n, m까지의 최단거리를 구하면 되므로 각 정점마다의 최단거리를 구할 수 있는 BFS로 풀이했다.풀이과정은 다음과 같다.미로를 입력받을 때 띄어쓰기 없이 입력 받기상하좌우를 탐색해 갈수있는 위치를 큐에 삽입,방문 표시

해당 노드에서부터 상하좌우로 조건에 맞는 경우 계속해서 나아가는 경우로, BFS 알고리즘을 사용했다.구현 과정은 다음과 같다.토마토 상태를 나타내는 배열을 받으며 1의 위치는 큐에 삽입1이나 -1이 들어올 경우 익은 토마토의 개수 +1익은 토마토의 개수가 전체 토마토의

나이트가 최소 몇 번만에 이동하는지를 구하는 문제이므로 최단거리를 구할 때 사용하는 알고리즘인 BFS를 사용했다.나이트가 한 번에 이동할 수 있는 거리 상수는 다음과 같이 그래프에서 총 8개로 정의할 수 있다.구현 과정은 다음과 같다.보드판 위에서 나이트의 현 위치의

최단 시간을 구하는 문제이므로 BFS를 사용해 구현하였다.이 문제 풀이의 핵심은 수빈이가 갈 수 있는 위치 변수 구현이라고 생각한다.우선 수빈이의 현 위치에서 +1, -1 하는 것은 간단히 dx = {1, -1} 로 나타낼 수 있다.그렇지만, 수빈이의 현 위치에서 순간

이 문제는 브루트포스 문제로,<1, 1>에서 조건에 부합할 때 까지 result에 1씩 더해주어 result를 구하려고 다음과 같이 코드를 작성했다.틀린 풀이의 로직은 정답이지만 시간초과로 오답이었다.공통되는 수들의 최댓값을 구하면 for문을 40000번까지 돌리

브루트포스의 순열 알고리즘을 이용해 푸는 문제이다.c++의 경우 stl에 next_permutation 함수가 존재하지만, 자바에는 없으므로 직접 구현해야한다.👉 다음 순열 알고리즘 설명 포스팅

바로 전에 푼 다음 순열 문제와 같은 해결 방식인 다음 순열 알고리즘을 적용해 풀었다.👉 백준 10972 다음 순열 풀이👉 다음 순열 알고리즘 설명다음 순열 알고리즘에선 i와 j를 수열 중 가장 큰 수를 찾기 위해 반복문을 사용했다면, 이전 순열 문제를 풀 때는 i

이 문제와 비슷한 '이전 수열', '다음 수열' 알고리즘으로 풀었을 때 테스트케이스 4까진 정답이었는데, 5부턴 틀린 답이 반환되었다.따라서 swap을 이용한 순열 대신 visited로 순열의 방문을 체크하면 DFS 알고리즘을 사용하였다.

모든 정수의 인덱스를 바꾸어 모두 탐색한 후 가장 큰 결괏값을 반환하려고 브루트포스 순열 알고리즘으로 풀었다. 풀이 과정은 다음과 같다.arr 배열에 담긴 N개의 정수를 visited 변수를 사용해 DFS로 arr 배열의 모든 인덱스에 방문한다.아직 방문하지 않은 인덱

이 문제는 푸는 방법이 다음 두 가지가 있다.브루트포스 백트래킹(재귀) 탐색DP그 중 나는 브루트포스 백트래킹(재귀) 탐색 방법으로 풀었고, 풀이과정은 다음과 같다.i가 1부터 4까지 n-i를 하며 0이 될 때 까지 재귀 탐색 진행n이 0이 되면 정답 개수 1 추가업로

이 문제는 푸는 방법이 다음 두 가지가 있다.브루트포스 백트래킹(DFS) 탐색DP그 중 나는 브루트포스 백트래킹(DFS) 탐색 방법으로 풀었고, 풀이과정은 다음과 같다.날짜+상담을 완료하는데 걸리는 기간(T)이 N보다 작거나 같을 때 상담이 가능한 것이므로해당 날짜에

문제에서 Sij는 Sji와 다를 수도 있다고 했으므로 규칙이 없이 진행된다. 따라서 작은 문제로 큰 문제를 해결할 수 있는 DP로는 풀 수 없게 된다.그럼 모든 경우의 수를 검사하는 브루트포스의 DFS로 풀어본 풀이는 다음과 같다. N은 무조건 짝수이고, 언제나 두 팀

14889번 스타트와 링크 문제와 비슷한듯 다른 문제였다.👉 14889번 스타트와 링크 풀이이 문제 또한 모든 경우의 수를 검사하는 브루트포스의 DFS로 풀었다.num번째 사람을 스타트 팀에 넣어(visitednum = true) num+1을 인수로 넣어 재귀를 진행

브루트포스의 순열을 활용했다. 풀이과정은 다음과 같다.idx가 k+1이 될 때 까지 백트래킹을 통해 부등호에 따른 숫자가 맞는지 판별하여 sb에 문자열로 받기sb에서 0번째는 가장 작은 수, result.size()-1번째는 가장 큰 수로 출력

각 단계마다 최선의 선택을 하는 그리디 알고리즘을 사용했다.풀이과정은 다음과 같다.각 Ni를 돌며 Ni을 key, 각 Ni의 length-1을 value로 저장👉 같은 key에는 value 중 최댓값으로 저장G = 3, C = 2, F = 1A = 5, C = 4,

모든 경우를 다 계산 후 최대, 최솟값을 구하는 문제이므로 DFS를 사용했다.풀이과정은 다음과 같다.사칙연산 구호 배열이 0이 아닐 떄 백트래킹과 동시에 사칙연산 결과 넘겨줌0이 아닌 사칙연산 구호 배열의 순서에 따라 연산 바뀜가장 마지막 정수까지 계산이 완료 되었을

동전의 사용 최소 개수를 구하는 문제이므로 그리디 알고리즘을 사용해 각 단계마다 사용할 수 있는 가장 최대 금액의 동전을 선택하면 전체 답이 구해진다.풀이과정은 다음과 같다.K보다 작은 가치의 동전 중 가장 큰 금액을 K 이하로 사용1에서 사용된 금액을 K에서 뺌2에서

내 풀이 이 문제처럼 시간표를 최대한 많이 배정하거나 선택하는 문제를 활동 선택 문제라고 하며 대표적으로 그리디 알고리즘을 사용해 풀 수 있다. > 💡 활동 선택 문제 한 사람이 하나의 활동에 대해서만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를

문제에 나온 것 처럼 각 사람이 일 처리에 걸리는 시간이 짧을수록 모든 사람이 일을 처리 완료 하는 데 걸리는 시간이 가장 짧아진다.이는 활동 선택 문제로, 그리디 알고리즘으로 풀 수 있다.풀이과정은 다음과 같다.각 사람마다 돈 인출에 걸리는 시간을 배열로 입력받아 오

요구사항을 하나하나 조건문으로 쳐내며 전부 구현했다.다음 칸보다 이전 칸이 더 높을 때, 다음 칸의 개수를 세는 메소드를 구현했는데 그 부분에서 탐색 인덱스 오류를 방지하기 위해 y + 1 < N도 조건으로 걸어 탐색을 진행했다.그 결과 채점 진행도 85%에서 멈

구현 문제로, 그래프 탐색을 할 때는 DFS를 이용했다풀이과정은 다음과 같다.dx, dy를 시계방향으로 90도씩 설정(방향 바꿀 때 사용)이동방향인 d 방향으로 주사위의 현위치 이동👉 이동하는 곳이 지도를 벗어나면 반대 방향으로 d를 설정해 이동DFS를 사용해 현재

각 구간의 최댓값을 결정해나가며 최적해를 찾기 위해 이분 탐색을 사용한다.예를 들어, 이 문제를 모든 가능한 구간을 확인하는 브루트 포스로 푼다면 문제에서 주어진 (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N)의 범위를 고려해 최대로 가능한 구간의 개수는 5000개로

내 풀이 이분 탐색을 통해 나올 수 있는 최댓값과 최솟값의 차이값을 탐색하고, 그 차이값으로 n,n칸까지 갈 수 있는 경로가 있는지 BFS로 탐색한다. 풀이과정은 다음과 같다. 주어지는 배열에서 최댓값과 최솟값 구하기 차이값을 0부터 배열 값의 평균((최댓값+최

내 풀이 어린이의 수인 N의 범위가 (1 ≤ N ≤ 2,000,000,000)으로 최댓값이 굉장히 큰 수이다. 시간 제한은 2초이므로, 실행 시간의 효율을 위해서 모든 어린이의 놀이기구가 시작되는 시간을 기준으로 이분 탐색을 수행하여 탐색 시간을 로그 단위로 줄여나가

울타리의 최소 갯수를 구하는 문제가 아니므로, 늑대의 상하좌우 칸을 탐색해 울타리를 친다.만일, 늑대와 양이 붙어있다면 어떻게 해도 늑대와 양은 만나기 때문에 바로 0을 출력하고, 그게 아니라면 해당 칸에는 울타리를 친다.이 때, 늑대와 늑대도 붙어있을 수 있으므로 탐

최단거리를 찾아야 하므로 BFS를 사용했다.처음엔 말이 움직일 수 있는 거리를 사용해 nx, ny를 정한다면 cnt에서 +1을 해, 만일 cnt와 k가 같아지면 그 뒤부턴 원숭이가 움직일 수 있는 거리로만 움직이도록 구현했다.그랬더니 BFS를 사용할 때 말이 움직일 수

내 풀이 오답 풀이 인접한 칸 중 더러운 칸을 우선순위(가중치)로 두고 이동하지 않아도 되므로 BFS로 가구가 없는 칸으로의 탐색을 계속 진행하면서 더러운 칸을 만나면 청소 후 남은 더러운 칸 수를 -1 해준 후, 남은 더러운 칸이 0이 되었을 때의 거리값을 반환해주

고슴도치와 비버 사이의 최단거리를 구해야하므로 BFS를 사용했다.물이 찬 지역이 여러개여서 티떱숲을 입력받을 때 \* 을 입력 받으면 물의 큐에 해당 위치 좌표 저장해 입력이 끝난 후 해당 큐로 BFS로 탐색한다.풀이과정은 다음과 같다.티떱숲 입력받으며 물이 찬 지역과

두 구역 사이의 최단거리를 구하므로 BFS를 사용했다.지나온 거리의 개수를 저장하는 배열 dis를 생성해 최종 목적지에 도착하면 해당 위치의 dis를 반환하여 반환하는 방식으로 풀었다.

빈 칸인 0에 벽을 반드시 3개를 세워야하는 조건이 있다.빈 칸에 3개의 벽을 세우는 모든 경우를 구하기 위해 DFS를 이용해 빈 칸에 3개의 벽을 세울 수 있는 모든 경우를 탐색한다.3개의 벽이 세워진 각 경우마다 BFS로 바이러스를 퍼지게 하고, 빈 칸의 수를 세어

상근이가 건물을 탈출할 때 최단 시간을 구하는 것이 목표이므로, 최단 경로를 찾을 수 있는 BFS를 사용해서 풀이했다.그리고 불이 퍼지는 것과 상근이가 이동하는 것을 동시에 관리해야하기 때문에 여러 출발 지점을 동시에 탐색하는 데 유리한 BFS를 사용했다.풀이과정은 다

최단 경로로 이동하므로 BFS를 사용한다.이 문제의 핵심은 모든 위치를 방문할 때, 벽을 부순 적이 있는지 여부를 함께 고려해 탐색해야 한다는 것이다.따라서 객체를 활용해 벽을 부순 여부와 최단거리를 저장한다.BFS 탐색 과정은 다음과 같다.이동할 위치가 벽이 아닌 경

우선 삼각형의 꼭대기부터 시작해 갈 수 있는 아래 두 수 중, 더 큰 수로 계속 가다보면 끝까지 도착했을 때 합이 최대가 되는 수가 될 것이라 예상했다. 이 방법으로 예제를 풀어보니 오답이었다.위 쪽에선 가장 큰 수만을 따라갔어도, 다른 경로에서 같은 레벨의 수 중 크

100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해야했으므로, 최단경로를 구할 수 있는 BFS 알고리즘을 떠올렸다.먼저, 10\*10칸이라고 하길래 board의 2중 배열 형태를 생각하였지만, 이중배열로는 잘 구현이 되지 않았고 뱀과 사다리가 있는

일정한 규칙을 가지고 연쇄적으로 연산이 진행되는 형태라서 다이나믹 프로그래밍으로 풀었다.두 번째 집 부터 n번째 집까지의 최소 비용을 계산해 저장하며 연산을 진행해, 마지막인 n번째 집에서 각 색깔 중 최솟값을 찾아 반환한다.풀이과정은 다음과 같다.두 번째 집부터 n번

해당 문제는 배열에서 특정 조건을 만족하는 부분 배열을 찾아내야하므로 투포인터를 사용하였다.이분탐색은 배열 내의 특정한 값을 찾는 방법이기 때문에 이분탐색보다 투포인터가 적합하다고 생각했다.풀이과정은 다음과 같다.두 수의 차를 기준으로 포인터를 움직여야하므로 a배열을

LCS 문제는 여러 부분 문제로 나눌 수 있으며, 이러한 부분 문제들이 여러 번 중복되어 나타난다.따라서 2차원 배열에 부분 문제들의 해결 결과를 저장하고 재사용하기 위해 다이나믹 프로그래밍으로 풀었다.풀이과정은 다음과 같다.두 문자열의 길이 + 1 크기의 2차원 배열

해당 문제는 그래프의 모든 간선의 가중치가 양의 정수인 방향 그래프이고, 시작 정점으로부터 다른 정점까지의 최단 경로를 구하는 문제이기 때문에 다익스트라 알고리즘을 사용하였다.Dijkstra 알고리즘 시간복잡도O((V + E) log V)Bellman-Ford 알고리즘

다익스트라로 최소경로 탐색에 경로를 추적하는 기능을 추가한 문제다.최소경로의 경로 추적을 위해서는 prev 배열을 사용해 각 노드에 도달하기 전의 노드를 저장한다.previ는 노드 i로 오는 최단 경로에서 이전 노드를 저장하며, i노드에 도달하기 직전에 어떤 노드를 거

Deque를 사용하여 0-1 BFS를 구현하는 문제이다.BFS의 탐색 과정 중 mironx의 값에 따라, 빈 방인 0은 덱의 앞에 삽입하고, 벽인 1은 덱의 뒤에 삽입한다.그렇게 되면 0을 지나온 경로가 dq에서 먼저 꺼내지게 되어 벽을 적게 부순 경로가 우선탐색 된다