https://www.acmicpc.net/problem/3015모노톤 스택모노톤 스택은 스택의 요소가 오름차순 또는 내림차순으로 유지되도록 설계된 특수한 스택입니다. 이는 특정 조건을 만족하는 요소를 효율적으로 처리하거나 빠르게 접근해야 할 때 사용됩니다.오름차순 스택: 스택에 쌓인 값이 항상 작아지지 않도록 유지.내림차순 스택: 스택에 쌓인 값이 항상 커지지 않도록 유지.모노톤 스택은 일반적으로 배열이나 리스트의 각 요소와 관련된 "가장 가까운 큰 값" 또는 "가장 가까운 작은 값"을 찾는 문제에 사용됩니다. O(N)의 시간 복잡도로 해결할 수 있어 효율적입니다.문제 접근이 문제 또한 모노톤 스택을 사용하여 해결할 수 있습니다.먼저 서로를 볼 수 있는 조건을 생각해 봅시다.두 사람이 서로 볼 수 있으..

https://www.acmicpc.net/problem/23057 문제 접근숫자의 조합으로 만들 수 없는 수의 합을 구해야한다.결국 만들 수 있는 모든 경우의 수를 구해야 하는데, N이 최대 20이면 최대 경우의 수는 2^20 이므로 DFS와 같은 방식은 시간 초과가 터진다.따라서 다른 방식을 선택해야 한다. 그게 비트마스킹 방식이다.비트마스킹으로 모든 경우의 수 찾기 HashSet sumSet = new HashSet(); int totalSubsets = 1  1 각 이진수 자리에 마스크를 넣어본다. mask 변수의 각 비트는 숫자를 포함할지 여부를 나타낸다. 비트 1이면 해당 숫자를 포함하고, 0이면 포함하지 않는다. 문제에서는 모두 자연수라는 조건 때문에 0을 제외해야 ..

https://www.codetree.ai/training-field/frequent-problems/problems/tree-tycoon/description?page=3&pageSize=10 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai문제 접근구현, 시뮬레이션 문제입니다.특수 영양제 규칙을 준수하여, 크게 특수 영양제 이동 -> 성장 -> 자르기로 로직을 분류합니다. 특수 영양제 규칙영양제는 매년 주어진 규칙에 따라 이동하며, 이동한 칸의 리브로수를 성장시킵니다.대각선 방향에 높이가 1 이상인 리브로수의 개수만큼 추가로 성장합니다.이미 영양제를 투..

코딩테스트 연습 - [PCCP 기출문제] 3번 / 충돌위험 찾기 | 프로그래머스 스쿨 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr처음 문제 풀이대충 중간에 하다가 영 아닌 것 같아서 포기한 코드import java.util.*;class Solution { public int solution(int[][] points, int[][] routes) { int answer = 0; Queue queue = new ArrayDeque(); for (int [] route : routes) { Point point = new Po..

1107번: 리모컨처음 문제 접근BFS인가? 하기엔 시도해야할 경우의 수가 너무 많은 것 같다. 사실상 브루트 포스로 하게 될 듯채널이 0 ≤ N ≤ 500,000니까 배열에 각 최소 횟수를 업데이트 해주는 식으로 해야할 것 같음고장이 안난 리모컨 배열에서 입력할 수 있는 모든 경우의 수를 만들어야 하나? 그럼 백트래킹인가?그럼 for문을 언제까지 돌리고 언제 끝내야하지?답지 보고 문제 접근1. 먼저 리모컨 배열을 만든다. 이 배열에 값이 -1이면 고장난 것을 의미한다. int n = Integer.parseInt(br.readLine()); if (n != 0) { StringTokenizer st = new StringTokenizer(br.readLine..

https://school.programmers.co.kr/learn/courses/30/lessons/340212?language=java 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr초기 문제 접근level 값을 때려 맞춰야할 것 같으니 이분 탐색을 떠올렸다.문제 시나리오 대로, diff diff가 더 높으면 i가 0 일 경우 total += (long) (diff - level) * timeCur + timeCur;i가 0보다 클 경우 total += (long) (diff - level) * (times[i - 1] + timeCur) + timeCu..

코딩테스트 연습 - 마법의 엘리베이터 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr초기 문제 접근처음엔 백트래킹? BFS? 등 완전 탐색을 생각했다.근데 그건 말이 안 된다. 너무나 많은 경우의 수가 존재한다.그리디인가? 동전 거스름돈처럼 큰 수부터 나누면 되는가?근데 음수도 존재해서 이것도 아니다.직접 if 문으로 조건을 따져야 하는 건가?  현재 자릿수가 6이면 10에서 빼는 거로 하고..그러면 올림의 경우, 앞자리에 1을 더해야 하는데.. 만약 더하는 게 더 많은 돌을 필요로 하면..? (머릿속이..

14940번: 쉬운 최단거리 (acmicpc.net)문제 접근전형적인 BFS 문제 같다.시작점부터 시작해서 BFS 시작그런데 자꾸 3%에서 틀렸다 나오길래 질문게시판을 찾아보았다.메모리 초과다시 같은 곳을 방문하지 않도록 방문 표시를 해주어야 한다. 안 그러면 Queue에 많은 좌표가 가득차게 된다.틀렸습니다도달할 수 없는 곳은 -1로 출력을 해야 한다. 이 처리를 안 해주면 3퍼에서 틀렸다고 나온다.따라서 필자는 방문 표시를 isVisited 배열을 만드는 대신 방문한 곳은 map 값을 -1로 바꾸어주었고, 도달하지 못한 곳은 이 값이 아직 1로 남아있기 때문에 이를 처리해주었다.코드import java.io.BufferedReader;import java.io.IOException;import jav..

18870번: 좌표 압축 (acmicpc.net)초기 문제 접근일단 문제 이해부터가 어려워서 질문 게시판을 찾아보니,그냥 이 배열 중 자기보다 낮은 원소의 개수를 출력하는 것 이었음근데 최대 N이 1,000,000 이니까 이중 for 문 쓰면 무조건 터질 것 같음정렬하고 하나하나 비교하나..?조금 찾아보니 이진 탐색을 사용하면 된다고 나와있음GPT의 문제 접근하지만 단순히 Map 사용으로 문제를 해결할 수 있었음각 순위를 표시할 rank = 0을 선언함정렬한 배열을 첫 번째 인덱스부터 순회함Map 안에 현재 순회하는 값이 없다면 새로 삽입 후 rank++결과적으로 숫자 별로 순위가 Map에 저장이 됨코드import java.io.BufferedReader;import java.io.IOException;..

11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net)처음 문제 접근DP 같이 생겼다.현재 값이 바이토닉 수열을 만족하면 dp = Math.max(dp[i - 1], dp[i]) + 1그런데 올라갔다가 내려오고, 다시 올라가려 하면 0부터 시작해야 하는데.. 이걸 어떻게..처음 대략 이렇게 코드를 짬 for (int i = 1; i arr[i]) { dp[i] = Math.max(dp[i - 1], dp[i]) + 1; } }문제 정답해결법은 올라갈 때와 내려갈 때를 따로 분리해서 DP 테이블을 만든다.근데 이게 왜 되는건지 몰랐는데, 123421 에서 가장 긴 부분은 1234 = 4이고 감소하는 부분은 421 3 이니까 결과적으로 답은 7 - 1(겹치는 부분인 4를 빼기 위함..