알고리즘

Stack은 가장 먼저 입력된 데이터가 가장 아래쪽에 쌓이고, 나중에 입력된 데이터가 위쪽에 쌓인다.자료구조(Data Structure)의 한 종류로 후입선출(LIFO : List in First out)구조를 가지고 있다.따라서 가장 먼저 들어간 데이터가 가장 끝부분

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 다섯 가지이다.push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경

📖문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮...

✔우선순위 큐란?

key, value로 이루어져있고, key는 중복을 허용하지 않으며, value는 중복을 허용한다.Map에는 해시함수를 통해 key에 해당하는 value값이 어디 저장되어있는지를 매핑한다.시간복잡도는 O(1)이다.중복을 허용하지 않는다.순서가 없으므로, pop() 사용

장점:반드시 답을 찾을 수 있다.단점: 리소스를 많이 잡아먹는다.브루트 포스 (Brute-force) 무차별 대입 ex) 비밀번호 숫자 4자리 경우의 수 모두 대입가장 확실한 방법이므로, 많이 사용된다.

매 순간마다의 최선의 경우만 골라간다.다른 경우는 고려하지 않는다모든 경우를 탐색하지 않아서 탐색이 빠르다

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “(

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게

📖문제 평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다. 이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의

풀이방법 일단 톱니바퀴의 정보를 2차원 배열에 넣는다 회전할 톱니바퀴와 회전방향을 dfs에 전달 (이때 전달할때마다 visited변수를 새로 생성해서 전달한다. 이전 방문이 영향을 끼치지 않도록) 현재 톱니바퀴 오른쪽 확인해서 첫방문이고 1~4번째 안에 있고, 극성이

문자열을 for문을 통해 한글자씩 탐색한다.현재 <> 안에 문자인지를 판별하기위해 안에 있다면 bracket=true를 통해 구별한다.<> 밖에 문자라면 다 뒤집어야 하므로, FILO의 형태로 데이터가 입출력되는 stack을 사용한다.stack에는 <>

👉 인접한 문자끼리 전부 한번씩 바꿀경우 겹치는 경우의 수가 생긴다. 겹치는 수를 줄이려면 (0,0)부터시작해서 내 오른쪽의 있는문자와 바꾸거나 내 아래에 있는 문자와 바꾸고, (0,1)로 넘어간다. 이를 3중포문으로 나타낼 수있다. 맵을 탐색하는 2중포문, 그안에서

2부터 N까지 배열에 담는다.2부터 하나씩 소수인지 판별한다. 소수 인지는 자신보다 작은수로 다 나눠보는것으로 확인할 수 있다. 하나라도 나눠지는게 없다면 소수라고 판단한다.따라서 여기서 2중 포문을 사용하면 된다.소수일때 list에 자신의 배수에 해당하는 수를 다 지

크게 분류하면 초마다 확산하는 로직, 공기청정기로 순환하는 로직 2가지로 구분해서 푼다.매 초 맵을 탐색하며 미세먼지가 있는 칸을 확인하고 큐에 담는다.큐에 있는 값을 동서남북으로 탐색한다. bfs작업을 한번만한다 생각(bfs함수에서 큐에 다시 안담으면 됨).이때 주의

📢이 문제는 가로의 길과 세로의 길을 세는 문제이다. 이문장이 가로의 경사로와 세로의 경사로가 겹쳐도 상관없다는 뜻이라는데.. 좀 모호한거 같지만 이조건을 토대로 문제를 풀었다.📢 문제를 풀다 보니 map을 변형할 일이 생겨 가로용 map 세로용 map2 2개를 만

입력값에서 남학생인지, 여학생인지 구분해서 로직을 구성한다.남학생일때 번호의 배수에 해당하는 스위치값을 바꾼다.여학생일때, (내 번호 + i값)과 (내번호 - i값)이 같으면 두 값에 해당하는 스위치값을 바꾼다.(i를 0부터 설정하는것에 주의, 스위치의 범위 밖을 탐색

크게 분류하면 괄호가 열렸을때마다 스택에 넣고, 닫힐때마다 하나씩 뺀다.단, 스택이 비었을때 괄호를 닫거나, ), ( 일때, for문을 다 돌아도 stack에 괄호가 남아있는 경우를 제외시킨다.값을 세는것은 (일때 cnt x 2 \[ 일때 cnt x 3 해준다. 괄

테두리만 없애기 위해 bfs탐색시 현재 칸은 visited변수로 체크해주고, map에서 1인경우를 만나면 해당 칸을 2로 바꿔준다. 이때 1일경우 해당 칸은 큐에 넣지 않는다(내부탐색은 못하도록)map에 치즈가 없을때 까지 bfs를 반복한다.이때 bfs전 치즈갯수를 p

📢 이 풀이의 핵심은 3세대 드래곤 커브의 동작에서 규칙을 찾아내는게 핵심이다.전 세대의 커브를 시계방향 회전시켜서 이어 붙이면 다음 세대 드래곤 커브가 된다.※이때 커브자체는 시계방향 회전이지만, 각각의 선분 방향의 회전만 놓고 본다면 반시계방향으로 돌고 있다.다음

📢이 풀이의 핵심은 간선에 해당하는 수를 좌표형태로 체크하는 것이다.이렇게 해야 한 요소에 연결된 여러 간선을 표현할 수 있다.1\. 1번 요소부터 dfs 탐색을 시작하고, 연결된 요소를 따라 가며 전부 visited\[] = true; 표시 해준다.2\. 더이상 탐

📢 이 풀이의 핵심은 사다리하나를 왼쪽에서 지날때, 오른쪽에서 지날때 나누어서 체크하는 것이다.1\. 처음 주어지는 사다리의 위치를 좌표에 1로 표현한뒤 바로 한칸 오른쪽에는 2로 표현한다.(사다리가 1을 만나면 오른쪽으로 가고, 2를 만나면 왼쪽으로 구현하게 하기

큰틀에서 보자면 가장 긴 가로 변과 세로변을 곱해서 만든 사각형에서 작은 사각형을 빼는 방식으로 구현하였다.1\. 입력받을때 가장 킨 가로변, 세로변을 각각 x,y에 넣는다.2\. 📢작은 사각형을 구현하는 가로와 세로변은 각각 x,y의 인덱스와 두칸씩 떨어져 있었다.

크게보면 궁수의 위치를 N+1행에서 돌면서 조합하고(dfs) 궁수 3명의 위치를 지정했으면,적을 없애는 함수로 넘어간다.적을 없애는 함수는 궁수의 위치에서 왼쪽부터 방향을 확인하는 bfs를 구현하여 적을 없애고, 맵을 이동한다.dfs함수를 통해 궁수 3명의 위치에 따른

📢이풀이의 핵심은 컨베이어 내구도 체크하는 배열, 로보트 유무를 체크하는 배열을 따로만들어서 같이 회전시키는 것이 핵심이다.내구도 배열, 로봇배열을 같이 회전시킨다. 처음 pre는 항상 2N번째 칸의 값을 넣어준다.(로봇은 어차피 N번째에서 다 삭제되니 2N번째에서

📢 이풀이의 핵심은 행 하나를 탐색하며 벽과 벽 사이에 있는 칸을 세는것이 빗물이 고인지점을 세는 것과 같다는것을 파악하는 점이다.flag를 통해 지금 고인 지점을 세고 있는지 아닌지 체크한다.첫번째 벽을 만나면 flag = true를 통해 표시해준다.첫번째 벽을 만

📢문제를 보면 닿아있는 블럭은 연쇄가 일어나므로, bfs를 써야 한다는것을 떠올릴 수 있으며, bfs후 맵 이동, 이런방식으로 설계를 한다.입력을 넣고 맵을 처음부터 탐색하면서 문자를 만나면 해당문자와 연결된칸을 없애는 bfs를 시작한다.bfs함수 내에서는 해당하는

맵 전체를 완전탐색 하여 search함수로 좌표를 넘겨준다.넘겨준 좌표에서 오른쪽 방향으로 탐색하며 같은 수의 꼭지점을 가진 좌표를 찾고, 거기까지의 거리를 list에 넣는다.같은 수의 꼭지점이 없다면 search 함수를 빠져나간다.y축에서 list의 마지막에 담긴 거

주어진 순열을 저장하는 sb, 가장 처음 순열을 뜻하는 firstsb를 만들고 두개가 같다면 -1을 출력한다.숫자를 오름차순으로 하나씩 담아 dfs 재귀함수를 수행한다. list에 숫자가 N개가 되면 dfssb를 만들어준다.dfssb와 처음 입력받은 sb가 같다면 이

이 문제는 어떤 알고리즘을 쓴다기 보다는 문제에서 주는 조건에 따라 충실히 구현하는것이 핵심이다.처음 입력받으면서 총 인구수를 계산한다.4중포문을 통해 x,y,d1,d2를 완전 탐색하여 side함수에 넘겨준다.문제가 주는 조건의 범위 밖이라면 탐색하지 않는다.조건대로

🔉 주의할점 주는 순서가 달라도 결과적으로 플레이어가 받은카드의 결과가 같으면 되기 때문에, 순서를 상관하지 않는 hashSet을 사용한다.로직전, 어떤 플레이어에게 가야하는지를 나타내는 p와 init이 같다면, 섞을 필요가 없다는 뜻이므로 0을 출력후 함수를 빠져나

벽을 하나 부수고, bfs를 실행해서 최솟값을 출력하는 전형적인 bfs풀이였다.주의할 점이 있다면, 그냥 count를 증가시키는게 아닌 copymap\[nrow]\[ncol] = copymap\[crow]\[ccol]+1;로 칸의 이동을 카운트 하는정도,마지막에 도달하

📢이 풀이의 핵심은 내 좌표를 포함하는 원 + 목표 좌표를 포함하는 원을 구하는 것이다. (단, 내 좌표와 목표 좌표를 동시에 포함하는 것은 세지 않는다.)동시 포함 처리를 생각해야 하는점에 주의 하자.문제는 장황하게 어렵게 설명해놨는데 사실 핵심이 너무 별게 아니어

for문을 돌며, 왼쪽에 입력값만큼 나보다 큰사람을 세웠다고 가정하고 지나친다. 입력값이 2라면 나보다 큰사람 두명을 지나치고 그다음 인덱스에 내가 선다.앞에서 채워진 배열은 나보다 작은 사람이므로, count하지 않고,0이 들어간 배열만 입력값 만큼 count하고 (

📢크게 보면 1부터 N까지의 수 중 변경할 숫자를 하나 정하고, 변경할 수 있는 갯수 P 안에 변경할 수 있다면, count를 증가시킨다.우선 첫 번째로 세그먼트를 2차원 배열을 통해 전부 하드코딩한다.현재 층이 한자리수가 아닐수도 있으므로 각자리 수를 따로 num배

일단 문제풀이 자체의 핵심은, 팁이 최댓값이 되게 하려면, 팁이 마이너스가 되는값이 최대한 많을때 최댓값이 된다. 왜냐면 마이너스가 되면 어차피 팁은 다 0이므로. 그래서 팁을 내림차순 정렬하는것이 핵심이다.팁을 내림차순 정렬한다.tip에서 등수를 뺀값 -1 처리를 해

핵심은 단어를 돌면서 이전문자와 달라지는 순간에 그룹단어인지를 체크 하도록 설계하는 것이다.1\. 각 단어를 한 문자씩 돌며 이전문자와 달라지는 순간을 찾는다.2\. 이전문자와 달라졌을때, 전에 나왔던 문자라면 flag = true를 체크하고 반복을 빠져나온다. 그 단

문자를 두개씩 묶어서 크로아티아 단어인지 체크한다.(마지막 인덱스 제외)마지막 인덱스는 따로 빼서 체크해준다.크로아티아 단어라면 answer++하고 인덱스를 2개 증가시키고, 아니라면 answer++하고 인덱스를 1개 증가시킨다.이때 크로아티아 단어중 "dz="는 3개

크게 올라가는 방향, 내려가는 방향을 기점으로 설계한다.1\. 올라가다가 맨위에 도착하게 되면, 옆으로 한칸 이동한뒤, 내려가는 방향으로 방향을 변경한다.2\. 내려가다가 맨 왼쪽에 도착하게 되면, 밑으로 한칸 이동한뒤 올라가는 방향으로 방향을 변경한다.처음에 칸에 해

int\[]형 list에 키, 몸무게를 넣는다.나보다 덩치 큰 사람이 있는지 찾는다.덩치 큰사람이 k명이면 덩치등수 k+1을 출력한다.처음에 문제조건이 좀 말이 안된다생각 했었는데(사실 지금도 이해가 안된다)일단 명확하게 아래처럼 지정해 줘서 그것만 보고 풀었다.N명의

📢핵심은 보통사람의 dfs, 적록색약의 dfs2 이렇게 두번 수행하는것이다.방문하지 않은 노드를 시작으로 해당 노드에 색과 같은지 dfs를 수행하고, count를 센다.방문하지 않은 노드를 시작으로 dfs2를 시작하는데, 블루일때와, R과 G일때의 경우를 나눠서 df

📢이문제의 핵심은 뽑은 숫자들이 싸이클을 돌 경우만 고를수 있다.즉, 마지막에 뽑은 숫자가 결국 처음에 뽑은 숫자와 같은 경우를 뜻한다.또한, 이때 해당하는 싸이클 전체를 저장하는것이 아니라, 처음 뽑은 그 숫자만 저장하고 다음탐색을 시작한다.숫자를 하나씩 dfs탐색

입력값에서 최대 높이를 구한다.0부터 최대 높이까지 물에 잠기는것을 가정한다. 잠긴 칸은 visited=true로 체크한다.물에 잠기지 않은 칸을 dfs()탐색하고, 영역의 갯수를 센다.높이에 따라 영역의 갯수가 최대일때를 구하고 출력한다.과정이 나눠져서 그렇지 차례로

각 맵의 인덱스에서 갈수있는 노드를 완전탐색한다.방문하지 않은 노드면서, 입력값에서 1을 표시한 노드라면, 방문체크하고 탐색을 계속한다.목표한 노드에 도착한다면 flag = true 처리를하여 도착 표시를 한다.count는 시작 노드와 목표노드가 경로를 거치지 않고 곧

쓰레기가 들어있고, 방문하지 않은 map을 시작으로 dfs탐색한다.한 칸 탐색시마다 count를 증가시켜준다.count의 최대값을 answer에 저장한다.평이한 dfs문제였다. count를 넘기는 것이 아니라 칸마다 세주는것이 특징인 문제였다.

우선 입력값에 따라 map에 사각형에 해당하는 부분을 1표시한다.(x축y축과 행,열은 다르다 주의하자)방문하지 않은 칸이고, 사각형이 아닌부분이라면 dfs를 탐색한다.한칸 탐색할때마다 size를 증가시키고 dfs탐색이 끝나면 size를 list에 담는다.list를 오름

📢이 문제의 요구사항은 1. 빈도수기준 내림차순 2. 빈도수 같을때, 먼저온 순서대로 정렬이다.1번 요구사항을 인덱스, 빈도수를 키,값으로 하여 내림차순 정렬하고2번 요구사항을 개별처리 하는 것으로 설계하는 것이 핵심이다.해시맵, getOrDefault 메서드를 사용

이 문제는 dp문제로 dfs로 모든 경우의수를 탐색하면 안된다.이런 구조를 떠올린 후, 배열의 맨 아래부터 재귀함수를 호출해서 맨위까지 올라가는 설계를 해야한다.첫번째 배열에 색깔별 초깃값을 넣어준다.맨마지막 배열을 색깔별로 dfs호출한다.재귀함수를 처음 도는 배열이라

1부터 N까지의 숫자를 노드로 하고, 각 노드마다 + , - , 3가지 연산을 하는 dfs를 설계한다.N까지 dfs를 통해 탐색하는데 탐색시 노드마다 배열에 연산을 담는다.연산 배열을 result 함수에 넘기고, 배열 순서대로 stringbuilder를 통해 문자열을

시간관련 문제다. string으로 변환해서 풀경우 풀이가 매우 복잡해지므로, 초단위로 변환해서 계산해야 한다.골넣은 팀이 1번팀이면 chk = true를 해주고 s += 1 을 해준다.2번팀이면 chk = false를 해주고 s-=1을 해준다.ntime에 입력값을 전부

이 문제를 풀때는 N<3보다 작아서 1,2,3,4번 방법을 모두 사용하는것은 불가능 할때를 기준으로 놓고 푼다.N이 3보다 작을때, 3보다 크거나 같을때를 기준으로 나누고, N이 1일때는 아예 움직일 수 없으므로 첫째칸 1칸만 탐색할 수 있다.N이 2일때는 첫째칸

풀이방법 달팽이는 위,오,아,왼 순으로 움직인다. 해당 순서대로 방향을 바꿔주며, 언제 방향을 유지할지, 언제 방향을 다음방향으로 바꿀지를 기준으로 설계한다. 달팽이의 시작좌표 (N / 2 + 1,N / 2 + 1) 부터 출발한다. 해당 좌표에 count값을 넣어준

이문제는 리스트에서 하나씩 숫자를 제거해가며 푼다는 설계를 하는것이 핵심이다.또한 탐색을 원형으로 돌면서 하므로 % 연산 사용을 계획한다.while문을 반복하면서 index = (index+K-1)%list.size();해준다.list인덱스0에 1부터 담겨있으므로 처음

이문제는 특이하게 좌표의 정보를 주지 않고, 방향정보와 거리를 입력값으로 준다.이를 좌표로 바꾼뒤 접근하는방법을 사용했다.1\. 상점들의 방향정보,거리를 list에 저장한다.2\. 최단거리를 구해야하므로 bfs탐색을 사용한다.3\. 매 상점 탐색마다 bfs탐색을 하고,

서로 다른 자료형을 list에 담을때 class를 생성해서 그클래스를 list에 담아서 접근한다.Member클래스를 만들고 입력값을 담은 뒤, list에 담는다.Member에서 나올 수 있는 최대값, 최소값 Member를 생성해서 list와 비교한다.year비교, 같으

아기상어 초기 크기 = 2조건자기보다 큰 물고기 있는칸 지나갈 수 없다.자기랑 같은 크기는 지나갈 수 있다.자기보다 작은 크기는 지나가며 먹는다.이동 방법1\. 맵에 먹을 수 있는 물고기 더이상 없다면 끝2\. 맵에 먹을 수 있는 물고기 1마리라면 그 물고기 먹으러

배열탐색시 분기를 "."을 만났을때, "c"를 만났을때로 나눈다."c"를 만났을 경우 다음 c를 만날때까지 또는 행의 마지막까지 값을 1씩 증가 시켜준다.다음 c를 만나거나 행의 마지막에는 탐색을 종료한다.stringBuilder를 통해 출력한다.어렵지 않게 풀었는데

좋아하는 학생이 가장 많이 인접해있는 자리비어있는 칸이 가장 많이 인접해있는 자리그중에 제일 작은 행, 열이 문제는 크게 보면 조건에 따라 학생들의 자리를 배치하고, 자리별로 탐색하며 만족도를 구하는 문제이다.2차원 배열 studentLike에 인덱스 0에는 학생의 번

바이러스 종류가 1인것부터 K번 인것까지 순차적으로 전염.1초에 한칸씩 전염될때, x초에 해당하는 전염상태를 구하라처음 입력받을때 바이러스의 종류가 1번인것 부터 que에 순차적으로 넣어야 나중에 bfs수행했을때, 번호순으로 순차적으로 전염된다.따라서 처음que에 바이

비어있는 사진틀이 있다면 무조건 게시비어있는 사진틀이 없다면 추천받은 횟수가 가장 적은 학생의 사진틀 내리고, 그자리에 게시추천받은 횟수가 가장 적은 학생이 여러명일땐, 먼저 등록된 학생의 사진 내리고 그자리에 게시이미 게시된 학생을 추천하면 추천횟수만 증가사진틀에서

문자열대로 방향 움직임킹이 돌을 만나면, 돌이 킹과 같은 방향으로 움직임체스판 밖으로 나가면, 그 이동은 하지 않는다.move함수에 입력값으로 들어온 이동정보, 현재 킹의 위치, 돌의 위치를 넘겨준다.move 함수에서는 킹,돌의 이동전 위치값을 answer값에 저장해논

📢 이문제의 핵심은 초에 따라 일정 장면이 반복되서 출력된다는 점이다.첫번째 장면 : 초기 입력값 map두번째 장면 : 전부 O세번째 장면 : 초기 입력값에서 폭발한 map네번째 장면 : 세번째 장면에서 폭발한 map따라서 N이 1 일때를 제외하고, 2초마다 두번째

📢 이 풀이의 핵심은 한사람씩 호출하다가 K가 나오면 멈춰야 한다.K가 나오기 전에 이미 호출한사람을 부른다면 영원히 K가 나오지 않는다.이를 바탕으로 구현한다.0번 부터 지목한 사람을 인수로 재귀함수를 호출한다.호출한 사람을 visited 체크하고, 다음 사람을 인

수빈이가 100번 채널에서부터 +,-로 target으로 이동하는 횟수고장난 번호를 피해 번호를 입력하고, +,-로 target까지 이동하는 횟수1,2번 둘중 더 적은 횟수를 고른다.📢 target이 500,000까지 가능하지만, 리모컨이 9만 남고, target이 0

이문제는 가상의 수 N을 하나씩 증가시키면서 나열된숫자와 한자리씩 비교하는 방식으로 풀어야 한다.검정색이 지워진 수이고, N을 1부터 하나씩 증가시켜가며,N이 빨간색 숫자를 포함하고 있으면, 다음 빨간색 숫자를 비교한다.N을 1부터 하나씩 증가시키며 매 반복마다 문자열

시간을 1초씩 증가하며, 매초마다 현재 주차된 차량을 세고, 그에따른 요금을 sum에 더해준다.시간을 1초씩 증가하며, 초마다 각 차량이 주차되어 있는지 확인한다.시작시간이 지났으면, 해당 차량이 주차된것으로 간주한다. count증가끝 시간이 지나면 해당 차량이 빠져나

1.초기구름 생성반복2\. 구름 이동3\. 물의양 증가4\. 구름제거5\. 물복사6\. 맵 전체 범위 구름 생성7\. 물의 양 감소8.바구니에 물의 양 합 구하기initcloud를 호출해서 que에 초기구름을 생성해서 넣어준다.이후 magic함수에서 moveCloud를

이 문제는 치즈의 두 개의 변이 외부와 맞닿아 있으면, 지워지도록 설계해야 한다. 📢 핵심은 bfs 수행시, 치즈를 만나면 que에 넣지 않는것이 핵심이다. 이렇게 설계하면, 외부와 맞닿은 변이 있는 치즈만 없어진다. 즉, 내부의 치즈는 없어지지 않도록 설계할 수 있

맵을 bfs로 탐색하며, 누적합을 따로 저장, 비교하는 방식으로 설계한다.초기에 cost를 전부 MAX_VALUE로 초기화시킨다.cost0 = 0으로 하고, bfs탐색을 시작한다.누적합을 저장하며 탐색하고, 중복탐색이 허용되야 한다.📢단, 현재 탐색 방법이 기존에 저

이 문제는 특이하게 도착지점을 주고, 시작지점을 구하는 문제이다.구현 방법은 두가지를 생각해볼 수 있는데,1\. 모든 시작지점을 완전탐색 방식으로 넣어서 도착지점이 나오는 경우의 수를 찾기2\. 도착지점부터 거꾸로 올라가서 시작지점을 찾기👉 간단하게 2번 방식을 구현

📢 이 풀이의 핵심은 가장 작은 수가 나오는 경우의 수를 찾는것이다.값이 가장 작아지도록 괄호를 치려면, -값이 가장 커지도록 괄호를 해야한다.즉, -를 기준으로 문자열을 나눠줘야 한다는 것이 핵심이다.문자열을 - 를 기준으로 나눠서 저장한다.저장한 문자열은 + 연산

풀이방법

문제조건 중복된 문자열 제거 문자열 길이가 작은 순으로 정렬 그런 문자열이 많다면, 문자열 사전 순으로 정렬 풀이방법 - 주석 풀이 문자열을 하나씩 입력받고, list에 저장한다. list를 다시 돌며 해당 문자열이 있는지 확인하고 있다면 삭제한다(contains메서

메모리 초과 발생 코드 정답 코드 풀이방법 이 문제는 문자열을 폭탄 문자열과 비교해가며, 같다면 지우는것을 반복하는 어렵지 않은 문제이다. 하지만, substring, replace, split의 메서드 사용시 오류가 난다. 이유는 에 있다. 📢 자바의 Stri

문자열의 뒤에 A를 추가한다.문자열을 뒤집고 뒤에 B를 추가한다.이 문제는 완전탐색으로 접근하기 쉬운데, 사실 여러 경우의 수가 있는것이 아니라 문제 조건을 보면 다음 탐색이 고정되어 있다.문자열 T의 마지막 문자가 A일 경우2번조건은 불가능하게 된다. 2번 연산을 했

다음날부터의 매매가의 최대를 구한다.오늘이 미래의 매매가의 최대값보다 작다면, sum에 오늘 매매가를 저장하고, count를 증가시킨다.오늘이 미래의 매매가의 최대값보다 크다면, 물건을 판다.그 동안 저장해놓은 오늘 매매가 \* count값에서 그 동안 저장해놓은 su

map.put(str,map.getOrDefault(str,0)+1);이 코드가 풀이의 핵심이다.중복제거하면서, 몇번 입력되었는지 확인한다.리스트에 키를 담아서 정렬한다.리스트를 돌면서 조건에 따라 출력한다.

전체적인 풀이의 설계는 완전탐색을 바탕으로 첫번째 열부터 열을 하나씩 늘려가며 dfs탐색을 수행한다.마지막열에서는 행을 하나 늘려서 dfs탐색을 해주고, 마지막 행에 도착하면 스도쿠를 끝낸다.map에 숫자가 써있다면, 다음 열을 탐색한다.map이 0이라면, 그 자리에

두개를 바꾸는 모든 경우의 수를 찾고 경우의 수 중 최댓값을 찾는다dfs함수 안에 이중포문 안에 인덱스가 풀이의 핵심이다.첫번째 수 부터 한개씩 바꿔보고 count를 증가시켜 재귀함수를 호출한다.count값이 교환횟수랑 같다면 max값을 통해 최댓값을 비교한다.dfs탐

풀이 방법

이 문제는 X를 조건에 따라 지우고 조건에 따라 출력하는 문제이다.조건에 따라 지우는건 어렵지 않다.다만 출력시 1. X가 적어도 하나는 존재한다. 2.섬의 크기에 맞춰서 지도를 축소해서 출력해야 하는 점이 복잡하다.입력을 받고, bfs()함수를 통해 사방을 확인해서

입력받을때, chars에 문자열을 전부 입력받고,N1그룹 문자열,N2그룹 문자열은 hashset1,hashset2에 각각 추가로 입력받는다.chars를 하나씩 탐색하며 N1그룹을 기준으로, 현재 charsj가 N1그룹이고, 다음문자가 N2그룹 문자일때의 인덱스를 lis

지뢰가 없는 부분 누를시, 누른부분의 8방향 모두 지뢰가 없다면, 주변 8방향 모두 연쇄적으로 숫자가 나타난다.연쇄적으로 숫자가 나타날때, 0이 나타나면, 계속 연쇄가 일어나고, 0이 아니라면, 연쇄가 일어나지 않는다.📢 map을 탐색시, 8방향 모두 지뢰가 없는 좌

초기값 num을 map0에 넣어주고, while문을 통해 map을 탐색한다.map밖을 탐색하거나, 이미 채워진 수를 만나면, dir = index%4을 통해 방향을 전환한다.빈칸이라면 map에 num을 넣고, 해당 칸이 현재 칸이 된다.num이 N\*N보다 커지면 wh

풀이방법 현재 문자에서 상하좌우 6번 이동해서 지나간 칸을 문자열로 이어붙인다. 현재 좌표의 숫자를 문자열에 추가해주고, 현재 좌표를 dfs탐색한다. 다음 방향을 문자열에 추가해주고 재귀함수 호출한다. 문자열 길이가 7개가 되면 hashSet에 넣어서 중복체크를 해준

👉 7번째 수열을 찾으려면 여러개의 이전 순열의 조합을 통해 찾게 된다.이과정에서 fibo(1), fibo(0)의 함수처럼 가장 말단의 함수는 매우 많은 호출을 수행하게 된다.👉피보나치 수열 0 1 1 2 3 5 8 에서f(0) = 8번 호출f(1), f(2) =

📢 이풀이의 핵심은 dpn에 3과 5를 최소로 사용하여 n을 만들수 있는 값을 넣어주는 것이다.이때, dpn값이 dpn-3, dpn-5 중에 하나에서 1이 증가한 값이다.이 문제에서는 가장 적은 개수로 만들어야 하기때문에 Math.min을 사용하여 설계해준다.이때,

📢이 문제에서는 할 수 있는 연산이 세가지로 나와있다.3으로 나누어 떨어질 경우 3으로 나누기2로 나누어 떨어질 경우 2로 나누기1빼기이 연산들중에는 겹치는 연산이 있기 때문에 경우의 따라 해당 연산들 중에 나오는 최소값을 구해야한다.3으로 나누어 떨어질 경우에, 3

2가지 경우의 수중 더 큰값을 dp배열에 메모이제이션하면서 진행한다.이때 n-1은 메모이제이션 하지 않고, arrn-1을 그대로 더해준다.이유는 n-1을 메모이제이션 하면, dp5,dp4,dp3...등 이전 계단을 밟았는지를 알수가 없다.📢따라서 (recur(n-3)

map을 완전탐색으로 0,0부터 check 함수로 가로,세로, 대각선 4방향을 확인하고(범위설정 주의) 놓을 수 있다면 퀸을 자리에 놓는다. (mapi = 1;)자리에 놓았다면 다음 행으로 넘어가서 다시 탐색을 시작한다.퀸 8개를 놓았다면 answer을 증가시키고 끝낸

📢 arrn에 들어있는 수보다 이전에 더 작은 값의 길이가 dp배열에 담기게 된다.이때 arrn보다 작은 arri값들중 dp배열의 값중에 최대값+1로 현재 dp배열에 저장한다.주의할 점은 최소길이가 1이므로, 전부 1로 초기화 해줘야 한다는 점이다.또한 recur(N

📢이 풀이의 핵심은 dp배열에 처음 순열부터의 합, 현재값 둘중에 큰값을 메모이제이션 하는것이다.이후 dp배열의 최댓값을 구하면 된다.나는 dp배열에 이후 순열의 합을 저장하고 접근했는데, 이런식의 접근에는 반례가 생겨서 풀 수가 없다.dp배열에 어떤값을 메모이제이션

우선 dp배열에 어떤 점화식으로 통해 P값을 넣어야 할지 알아보기 위해 가능한 경우의 수를 하나씩 나열해본다.1 4 523 4 54 5500👉 나중에 상담한 값이 이전의 dp값에 영향을 미치는 것을 확인할 수 있다. 즉, dpi = dpi+1 + k; 이런식의 점화식

스택에 현재 인덱스를 담으며 진행하고,while문으로 스택을 탐색하며, 스택에 담긴 인덱스에 해당하는 arr값이 현재 arr값보다 작으면 그곳에 현재 arr값을 대입하며 진행한다.현재 arr값보다 크다면, while문을 탈출한다.처리되지 못하고 stack에 남아있는 인

\-5 000 ≤ r1, c1, r2, c2 ≤ 5,0000 ≤ r2 - r1 ≤ 490 ≤ c2 - c1 ≤ 4만약 수의 길이가 가장 길이가 긴 수보다 작다면, 왼쪽에서부터 공백을 삽입해 길이를 맞춘다.📢해당풀이의 전체적인 접근은, 입력값의 최대범위에 맞게 배열을

풀이 방법 전체 코드의 구조는 현재 위치의 건물에서 왼쪽에 위치한 건물, 오른쪽의 위치한 건물 중 조건에 해당하는 건물을 세고, 완전탐색 방식으로 탐색하여 조건에 맞는 건물 중 최댓값을 구한다. > 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나

풀이방법 이 문제는 완전탐색 방식으로 스위치를 K번 껐다켰다 하는 경우의 수 중 최댓값을 찾으면 시간초과가 난다. 따라서 적절한 규칙을 찾아서 그리디 방식으로 구현해야한다.

현재 위치x에서 갈 수 있는 방법은 총 세가지가 있다.x-1,x+1,2\*x 방문하지 않은 곳이라면 큐에 넣어준다.큐에 넣을때, 위치와 시간을 함께넣는데, 2\*x로 이동할때는 시간을 추가하지 않는다.현재 위치가 K라면 그때의 시간을 출력한다.📢간단한 bfs이지만 주

사다리와 뱀리스트를 만들어 입력받은 값을 넣어준다.bfs탐색시 다음 위치로 가능한 수는 현재 위치 + 주사위 1~6까지 수이다.이때 다음 위치에 해당하는 수가 사다리나 뱀 리스트에 있는 수라면, 추가적으로 이동한다.👉뱀을 거치는게 최소일 수도 있으므로, 뱀을 아예 제

📢전체적인 구조는 dfs탐색을 통해 @를 만나면 flag=true;를 통해 끝낼수 있음을 체크하고, 없다면 NO를 출력한다.이때, 무한반복 탈출조건은 같은 좌표에, 같은 메모리크기, 같은 방향이 온다면 탈출하도록 하여 끝낼 수 없음을 체크한다.check 함수에 좌표와

1번 코드(수학공식 사용) 풀이방법 nCr의 조합을 사용하면 된다까지는 확인할 수 있다. 다만 nCr을 어떻게 구현할 것인가가 문제이다. 이를 그대로 구현하면, long 자료형에 29!을 담을 수가 없다. 따라서 약분한 식을 구현해준다. 즉, 7C4 라면, 7x6x

1번 코드(수학공식 사용) 풀이방법 nCr의 조합을 사용하면 된다까지는 확인할 수 있다. 다만 nCr을 어떻게 구현할 것인가가 문제이다. 이를 그대로 구현하면, long 자료형에 29!을 담을 수가 없다. 따라서 약분한 식을 구현해준다. 즉, 7C4 라면, 7x6x

1번 코드(수학공식 사용) 풀이방법 nCr의 조합을 사용하면 된다까지는 확인할 수 있다. 다만 nCr을 어떻게 구현할 것인가가 문제이다. 이를 그대로 구현하면, long 자료형에 29!을 담을 수가 없다. 따라서 약분한 식을 구현해준다. 즉, 7C4 라면, 7x6x

1번 코드(수학공식 사용) 풀이방법 nCr의 조합을 사용하면 된다까지는 확인할 수 있다. 다만 nCr을 어떻게 구현할 것인가가 문제이다. 이를 그대로 구현하면, long 자료형에 29!을 담을 수가 없다. 따라서 약분한 식을 구현해준다. 즉, 7C4 라면, 7x6x

dp배열에 넣어야 할 값: 현재 값보다 작은 값 중에 증가하는 순열의 합이 가장 큰값1 100 5 3 50 일때, dp5가 가능한 증가하는 순열은 1 5 50, 1 3 50 두가지가 있다. 둘 중 큰값을 선택한다.이때 1 5, 1 3 은 각각 dp3, dp4이다.즉 d

dp배열에 들어갈 값은 제곱수의 갯수가 들어가면 된다. 11의 경우, $11=3^2+1^2+1^2$(3개 항) $11=2^2+2^2+1^2+1^2+1^2$(5개 항)이 가능하기 때문에 최솟값을 찾아야 한다.이때, 무조건 큰 제곱수를 기준으로 생각할 수 있는데,12를 살

전체적인 설계는 100x100 이차원 배열을 생성 후, R,C연산에 따라, 각 행 또는 열을 해쉬맵, 리스트를 통해 정렬을 반복하는 것이다.hashmap에 숫자와 빈도수를 세서 넣는다. 이때, 0은 세지 않는다.숫자와 빈도수를 list에 전달한다.📢 리스트를 숫자 기

📢이 문제의 핵심은 종료시점을 기준으로 정렬한 후, 가장 위에 있는 회의부터 고르면 된다는 것이다.단, 이때 종료시점이 같다면, 시작시점이 빠른것을 먼저 선택해야한다.알고나면 아무것도 아닌 규칙이지만, 알기전에는 잘 안보였던 규칙이었다.규칙만 안다면 구현은 크게 어렵

우선 dp배열에 들어가야할 값은, 물건의 인덱스별 무게별 가치합이 들어가야한다.그냥 무게별 가치합으로 일차원 배열로 설정한다면, 같은 무게인데 다른 물건으로 이루어졌을때, 관계정립을 할 수가 없다.따라서 물건의 인덱스별 무게별 가치합, 이차원 배열을 통해 dp를 설정한

우선 dp배열에 들어가야할 값은, 물건의 인덱스별 무게별 가치합이 들어가야한다.그냥 무게별 가치합으로 일차원 배열로 설정한다면, 같은 무게인데 다른 물건으로 이루어졌을때, 관계정립을 할 수가 없다.따라서 물건의 인덱스별 무게별 가치합, 이차원 배열을 통해 dp를 설정한

카드를 오름차순 정렬하고, 앞에 두 묶음을 더한다.더한 카드를 새로운 한 묶음으로 하여, 카드 묶음들을 재정렬한다.이를 계속 반복한다.👉즉, 앞에 두개 더하고, list 정렬, 앞에 두개 더하고, list 정렬을 반복한다.왜냐면, 가장 작은 카드 묶음들을 더해야 최소

📢이 문제의 핵심은 높은 자릿수에 알파벳에 높은 숫자를 배정해야 한다는 것이 핵심이다.alphabet 배열 26개를 만든다. (A-Z)GCF = 100G + 10C + 1FACDEB = 10000A + 1000C + 100D + 10E + 1B두개를 더하면, 1000

풀이방법 완전탐색으로 맵전체를 탐색한다. 해당 좌표에서 가로,세로로 분사하여 잡은 파리와 대각선으로 분사하여 잡은 파리를 계산하여 최댓값을 구하며 탐색한다. ddfs함수에 좌표와 방향, count를 넘겨주고, 각 방향의 파리값을 한칸씩 sum에 더해준다. count가 M이 되는 시점에 함수를 빠져나온다. 후기 특이하게 대각선 방향과 가로,세로 방향의 값...

L 이하의 값을 조합하여 점수가 최대가 되는 경우의 수를 찾는 문제이다.완전탐색, 백트래킹을 이용했다.보통 갯수를 초과했을때, return 하는 문제들이 많았는데, 이문제는 L을 초과했을때, return하는 방식으로 푼다면 이후 경우의수를 체크하지 못한다.즉, 1,2,

📢 a,b,c 조건으로 위해 3차원 dp배열을 만드는것이 핵심이다.숫자 3개 중에 음수가 있다면, 조건에 따라 무조건 1이 나온다.bottom up 방식으로 3차원 dp배열을 미리 채워넣는다.이후 재귀함수를 실행한다.이때, if(dp\[a]\[b]\[c]!=0) re

코드 1 풀이방법 진실을 아는 사람들을 knows hashset에 넣고, 진실을 아는사람이 있는 파티 check배열에 표시한다. 진실을 아는사람과 같은 파티 사람들을 전부 knows hashset에 넣는다. 다시 파티를 탐색하며, 1,2번을 반복한다. 더이상 진실을

JDK 다운로드 bellsoft에서 JDK 17 다운로드

https://www.acmicpc.net/problem/2133📢 이문제는 점화식을 찾는게 핵심이다. 점화식만 찾으면 풀이는 매우 쉽다.점화식을 찾기 위해선, 규칙이 보일때까지 노가다로 세주어야 한다.1\. N이 홀수일때는 가능한 경우의 수가 없다.N이 2

https://www.acmicpc.net/problem/11000우선 규칙자체를 찾는것은 그렇게 어렵지 않았다.시작시간이 빠른 순서대로 정렬 후, 처음부터 탐색하는데, 끝나는시간<=시작시간이 되면 연달아 강의를 하는 로직을 구현하면 된다.하지만 이렇게

우선접근 방법이 가장 중요한데, 동전이 1개만 있을때, 2개 있을때, 3개있을때, 이런식으로 경우의 수를 구해야 한다.하지만 그렇다고 2차원 배열을 쓰면 메모리 초과가 발생하므로, 이전 코인의 dp값을 토대로 다음 코인의 dp값을 구해야한다.👉여기서 살펴보면 코인이

import java.awt.Checkbox;import java.awt.BufferCapabilities.FlipContents;import java.io.BufferedReader;import java.io.IOException;import java.io.Input

https://www.acmicpc.net/problem/2212📢 이문제는 센서의 끝에서 끝 거리에서, 집중국을 세움으로써, 계산하지 않아도 되는 거리가 생긴다는 점이 핵심이다.<1 3> <6 6 7 9> 집중국이 두개 일때, 이렇게 묶인다.전체

📢 우선 이 문제는 제한무게(crane)과 박스 무게(box)를 둘다 정렬해줘야 한다는 것 까지는 쉽게 생각할 수 있다.이제 박스를 크레인과 하나씩 매칭시켜 주는데, 값이 큰것부터 순차적으로 crane\[i]>=list.get(boxIndex) 해준다.이조건에 안맞을

👉우선 처음 문제를 딱 봤을때 생각난 풀이는 백트래킹 방식이었다.입력값으로 들어온 문자열을N1에는 한자리수로 끊고, N2에는 두자리수로 끊었다.카드가 0일경우는 없으므로 N1==0일때 return하는 코드는 사실 없어도 무방하다.N2 > 34 일때는 두자리수로 끊을

👉우선 각각의 D,S,L,R의 동작은 어렵지 않게 구현할 수 있으므로 생략.L,R동작에서 각 자리수의 배열에 잘라서 추가하고, 다시 배열을 돌며 숫자로 합치는 로직을 사용하였다.시간복잡도는 조금더 나오겠지만, 0이들어갈때, 반례가 안나오게 하기위해 사용하였다.📢이문

풀이 방법 이러한 삼각형은 기본형인 아래 삼각형이 여러개 모여 만들어졌다. 또한 각 꼭지점을 기준으로 3영역으로 분할하면 같은 삼각형이 되는데 이를 계속 나누다 보면 기본형 삼각형이 될때까지 나눌 수 있다. 즉, 분할정복 방식으로 풀 수 있다. 각 삼각형의 가장

전체적인 설계는 우선, 처음부터 순차적으로 연산한 후, 끝지점에 도달하면, 다시 백트래킹하면서 괄호를 씌워준다. 이때, 괄호를 씌운 후 다시 dfs에 넣어준다.코드로 살펴보면이러한 구조가 된다.즉, 한 dfs싸이클에서1\. 해당 숫자를 순차적으로 계산 후 dfs()에