ImJay

[CodeTree/Java] 나무박멸 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai문제 해석이 문제에서는 n*n 격자 위에서 나무가 번식하고 제초제를 통해 그 성장을 억제하는 시뮬레이션을 진행한다. 주어진 입력은 격자의 크기 n, 시뮬레이션을 진행할 년 수 m, 제초제의 확산 범위 k, 제초제의 지속 시간 c로 구성된다. 각 격자 칸은 나무의 수, 빈 칸, 또는 벽으로 표시된다. 나무는 인접한 칸으로 성장하고 번식할 수 있으며, 제초제는 대각선 방향으로 k칸 만큼 확산되어 나무를 박멸한다. 제초제는 벽을 만나면 확산이 중단된다.풀이 과정성장: 모든 나무..

[BOJ/Java] 2531. 회전 초밥https://www.acmicpc.net/problem/2531문제 해석회전 초밥 문제는 주어진 회전 초밥 벨트에서 연속된 K개의 초밥을 선택했을 때, 이때의 다양한 초밥의 종류를 최대화하는 문제이다. 또한, 초밥의 선택은 하나의 쿠폰을 이용하여 원하는 초밥 한 종류를 추가할 수 있어, 이를 고려한 최적의 초밥 선택 전략을 요구한다.풀이 과정 초기 설정: 입력을 받아 전역 변수로 N(총 초밥의 개수), D(초밥의 종류 수), K(연속해서 먹을 초밥의 개수), C(쿠폰으로 먹을 수 있는 초밥 번호)를 설정하고, 초밥의 번호를 저장할 배열 arr을 선언한다.슬라이딩 윈도우 및 초밥 종류 카운팅: 첫 K개의 초밥을 선택하여 종류를 카운팅한다. 이를 기반으로 슬라이딩 윈..

[BOJ/Java] 2565. 전깃줄https://www.acmicpc.net/problem/2565문제 해석문제는 주어진 전깃줄이 교차하지 않도록 최소 몇 개의 전깃줄을 제거해야 하는지를 묻고 있다. 이 문제는 동적 계획법을 이용한 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 문제의 변형으로 볼 수 있다. A와 B 두 전봇대에 연결된 전깃줄의 위치가 주어지며, 각 전깃줄은 A전봇대의 특정 위치에서 B전봇대의 특정 위치로 연결된다.풀이 과정주어진 입력으로부터 전깃줄 정보를 배열에 저장하고, A 전봇대에 대해 오름차순 정렬을 실시한다. 이후, B 전봇대의 위치를 기준으로 LIS를 계산하여, 교차하지 않는 최대 전깃줄 수를 찾는다. LIS의 길이가 교차하지 않는 최..

[Softeer/Java] 6248. 출퇴근길 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai문제 해석동환이는 자동차로 출퇴근을 하면서 가끔 길을 바꾸어 다니며 새로운 동네를 발견하는 것을 즐긴다. 이 문제에서는 동환이의 출퇴근길을 단방향 그래프로 나타내어, S에서 T로의 출근길과 T에서 S로의 퇴근길에 모두 방문할 수 있는 동네(정점)의 개수를 찾는다. 각 정점은 동네를, 간선은 도로를 의미하며, 각 도로는 일방통행이다. 문제는 출퇴근길에서 공통적으로 방문 가능한 정점을 찾는 것에 초점을 맞추어 있다.풀이 과정그래프 구성: n개의 정점과 m개의 일방통행 간선 정보를 입력받아 그래프를 구성한다. 또한, 각 정점에서 출발하는 간선 리스트와 각 정점으로 도착하는 간선 리스트를 각각 관리..

[Softeer/Java] 6293. 징검다리 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai문제 해석남북으로 흐르는 개울에 서쪽에서 동쪽으로 높이가 다른 돌들이 일렬로 놓여 있다. 이때, 철수는 서쪽에서 시작하여 동쪽으로 갈 때, 높이가 점점 증가하는 순서로만 돌을 밟고 건너가려고 한다. 주어진 돌의 높이에 따라 철수가 밟을 수 있는 돌의 최대 개수를 구하는 문제이다.풀이 과정문제는 "가장 긴 증가하는 부분 수열(Longest Increasing Subsequence, LIS)" 문제의 일종이다. 주어진 수열에서 가능한 한 길게 증가하는 부분 수열을 찾아야 한다.이 문제를 해결하기 위해 동적 프로그래밍(Dynamic Programming)을 사용하였다. dp[i]는 i번째 돌까지 ..

[Softeer/Java] 6294. 평균 구하기 2178번: 미로 탐색첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.www.acmicpc.net문제 해석이 문제에서는 학생들의 점수 목록이 주어지고, 주어진 쿼리에 따라 특정 범위의 학생들 점수의 평균을 계산해야 한다. 각 쿼리는 시작 인덱스 𝑠s와 종료 인덱스 𝑒e를 포함하며, 이 범위에 포함된 학생들의 점수 평균을 출력한다. 문제에서 제공된 코드는 시작 인덱스를 1부터 계산하므로 입력 받을 때 인덱스 조정이 필요하다.풀이 과정제공된 코드는 입력 받은 점수 배열과 쿼리를 처리하여 평균을 계산하는 로직을 포함한다. 각 쿼리는 주어진 범위의..

[BOJ/Java] 12015. 가장 긴 증가하는 부분 수열 2 12015번: 가장 긴 증가하는 부분 수열 2첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)www.acmicpc.net문제 해석주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 고전적인 문제의 확장판이다. 이 문제는 수열의 길이가 매우 클 수 있기 때문에 𝑂(𝑁^2)의 시간 복잡도를 갖는 기본적인 동적 프로그래밍 방법으로는 효율적으로 해결할 수 없다. 대신, 이진 탐색을 활용한 𝑂(𝑁log⁡𝑁) 시간 복잡도의 풀이가 필요하다.풀이 과정입력 받기: 수열의 크기 N과 수열 A를 입력 받는다.DP 배열 초기화..

[BOJ/Java] 11055. 가장 큰 증가 부분 수열 11055번: 가장 큰 증가하는 부분 수열수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는www.acmicpc.net문제 해석주어진 수열에서 증가 부분 수열을 찾아 그 합이 최대가 되는 값을 구하는 문제이다. 이는 '가장 긴 증가하는 부분 수열' 문제의 변형으로, 길이가 아닌 수열의 합을 최대화하는 것이 목표이다.풀이 과정입력 받기: 수열의 크기 N과 수열 A를 입력 받는다.동적 프로그래밍(DP) 배열 초기화: DP 배열을 사용하여 각 위치에서 가능한 최대 합을 저장..

[BOJ/Java] 1786. 찾기 1786번: 찾기첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～mwww.acmicpc.net문제 해석문자열에서 특정 패턴을 찾는 문제로, 주어진 텍스트 문자열(T)에서 패턴 문자열(P)이 등장하는 모든 위치를 찾아 그 시작 위치들을 출력하는 것이다. 이 문제는 문자열 검색 알고리즘 중 하나인 KMP(Knuth-Morris-Pratt) 알고리즘을 사용하여 해결할 수 있다. KMP 알고리즘은 불필요한 문자 비교를 최소화하여 빠른 검색을 가능하게 한다.풀이 과정입력 받기: 문자열 T와 패턴 P를 입력 받는다.KMP 실행:..

[BOJ/Java] 9205. 맥주 마시면서 걸어가기 9205번: 맥주 마시면서 걸어가기송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다.www.acmicpc.net문제 해석이 문제는 페스티벌에 참여하기 위해 맥주를 마시면서 여러 장소를 거쳐가는 과정을 모델링한 그래프 탐색 문제이다. 주어진 장소들 사이의 거리를 기반으로 맥주 한 캔으로 갈 수 있는 최대 거리(1000미터)를 고려해, 출발지(집)에서 목적지(페스티벌)까지 도달 가능한지 판단해야 한다.풀이 과정주어진 모든 위치를 Vertex 객체로 저장하고, 각 위치 간의 거리를 계산해 연결 가능..