icodesiuuuu 님의 블로그

[프로그래머스 / Java] 양과 늑대

문제https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 개요이 문제는 2진 트리 형태의 초원을 탐험하면서 가능한 많은 양을 모으는 문제다.트리의 각 노드에는 양 또는 늑대가 한 마리씩 배치되어 있고, 루트 노드(0번)에서 출발하여 노드를 방문할 때마다 그 노드에 있는 동물이 따라오게 된다.문제의 핵심 조건은 다음과 같다:양과 늑대가 함께 따라오며,늑대의 수가 양의 수 이상이 되는 순간, 모든 양이 잡아먹혀 탐색이 실패하게 된다.이 조건을 지키면서 가능한 많은 양을 수집하는 경로를 탐색해야 한다. ..

문제 개요주문서는 알파벳 소문자로 이루어진 모든 문자열을 특정 규칙에 따라 정렬한 리스트다.문자열 길이가 짧을수록 먼저 온다.길이가 같다면 사전 순으로 정렬된다.예를 들어 "a", "b", ..., "z", "aa", "ab", ..., "zz", "aaa", ... 순으로 이어진다.하지만 일부 문자열이 삭제된 상태이며, 삭제된 문자열들을 제외하고 남은 문자열 중에서 n번째에 위치한 문자열을 찾아야 한다. 접근 방법 이 문제는 문자열을 정렬 순서대로 하나씩 탐색하는 방식으로는 풀 수 없다. 최대 n이 10^15까지 가능하기 때문에 효율적인 방식이 필요하다. 따라서 문자열을 고유한 숫자에 매핑해서 계산하고, 삭제된 문자열이 영향을 주는 범위를 고려해 n을 보정한 후 다시 문자열로 변환하는 방식으로 해결했..

https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 개요이 문제는 N x M 크기의 게임 맵에서 건물들의 내구도를 관리하는 문제다. 각각의 칸에 건물이 존재하며, 적군은 직사각형 범위로 건물의 내구도를 감소시키는 공격을, 아군은 직사각형 범위로 내구도를 증가시키는 회복 스킬을 사용한다. 모든 공격과 회복이 끝난 후, 내구도가 1 이상인 건물의 개수를 계산하는 것이 목표다. 접근 방법이 문제는 누적합을 활용한 2차원 차이 배열 (2D Difference Array) 기법으로 해결해야 효율..

https://www.acmicpc.net/problem/2668 문제 개요 가로로 N개의 칸, 세로로 두 줄로 이루어진 표가 주어진다. 첫 번째 줄에는 1부터 N까지의 정수가 순서대로 들어 있으며, 두 번째 줄에는 각 칸마다 1 이상 N 이하의 정수가 하나씩 주어진다. 이때, 첫 번째 줄에서 일부 정수를 선택하되, 선택한 정수들의 집합과 각 정수 바로 아래 칸에 위치한 수들의 집합이 정확히 일치하도록 해야 한다. 접근 방법 이 문제는 "S와 T가 같아야 한다"는 조건이 정확히 '자기 자신으로 돌아오는 사이클'이라는 성질을 의미예를 들어 1 → 3 → 1이면 S={1,3}, T={3,1} → 동일하므로 조건 성립 코드 import java.io.*;import java.nio.Buffer;import ..

문제https://www.acmicpc.net/problem/11501 문제 개요홍준이는 미래의 주식 가격을 정확히 예측할 수 있지만, 언제 어떤 방식으로 매매를 해야 최대 이익을 얻을지는 모른다.매일 다음 세 가지 행동 중 하나를 할 수 있다.주식을 하나 산다가지고 있는 주식을 원하는 만큼 판다아무것도 하지 않는다주어진 날 별 주식 가격을 보고, 최대 이익을 계산하는 문제이다. 접근 방법이 문제는 뒤에서부터 탐색하는 것이 핵심이다.미래의 주가를 알기 때문에, "앞으로 가장 비싼 날"을 기준으로 현재 주가를 판단할 수 있다.뒤에서부터 탐색하면서, 지금까지 본 주가 중 가장 높은 가격(max)을 기록한다.현재 주가가 max보다 작으면, 지금 매수한 후 max 가격에 판매한다고 가정해 이익을 계산한다.주가..

문제https://www.acmicpc.net/problem/15683 문제 개요 이문제는 다양한 종류의 CCTV를 이용해 사무실 공간 내의 사각지대(감시되지 않는 영역)를 최소화하는 시뮬레이션 문제입니다.각 CCTV는 감시 가능한 방향이 정해져 있으며, 회전을 통해 방향을 설정할 수 있습니다. CCTV는 벽을 넘을 수 없지만 다른 CCTV는 통과할 수 있으며, 모든 CCTV의 방향을 적절히 정해 전체 사무실에서 감시되지 않는 빈 칸(0)의 개수를 최소화하는 것이 목표입니다. 접근 방법문제 분석 및 모델링사무실은 2차원 배열 map로 표현됩니다.CCTV는 종류(1~5번)에 따라 감시할 수 있는 방향이 다르며, 이에 따라 각각 가능한 방향 조합(monitor)을 미리 정의해 두었습니다.벽(6)은 감시를 막..

문제https://school.programmers.co.kr/learn/courses/30/lessons/389480 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  문제 개요A도둑과 B도둑은 협력하여 모든 물건을 훔치려 합니다. 하지만 물건을 훔칠 때마다 각 도둑에게 흔적이 남으며, 이 흔적이 기준 이상으로 누적되면 경찰에 붙잡히게 됩니다.A가 훔치면 info[i][0]만큼 A의 흔적이 쌓인다.B가 훔치면 info[i][1]만큼 B의 흔적이 쌓인다.목표는 모든 물건을 도둑질하되, A와 B 모두 경찰에 붙잡히지 않도록 하면서 A의 흔적 합계를 최소화하는 것입니다.  접근 방법이 문제는 각 물건마다 A..

문제https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  문제 개요민호는 다단계 방식으로 칫솔을 판매하는 조직을 운영하고 있습니다. 각 판매원이 칫솔을 판매하면, 발생한 이익이 추천인 관계를 따라 위로 분배되는 구조입니다. 이때 이익은 아래와 같은 규칙에 따라 분배됩니다.칫솔 한 개를 판매하면 100원의 이익이 발생합니다.이익의 10%는 추천인에게 전달되고, 나머지 90%는 본인이 가집니다.이 추천인은 다시 받은 금액의 10%를 자신의 추천인에게 전달합니다.이 과정은 분배 금액이 1원 미만이 될..

문제https://school.programmers.co.kr/learn/courses/30/lessons/132266?language=java 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  문제 개요 강철부대의 부대원들이 여러 지역에 흩어져 특수 임무를 수행하고 있으며, 각 부대원은 주어진 지도 정보를 활용해 부대로 복귀해야 합니다. 각 지역은 번호로 구분되며, 두 지역을 연결하는 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 하지만 임무가 끝난 후 일부 경로가 사라져 특정 지역에서는 부대로 돌아올 수 없는 경우도 발생할 수 있습니다. 주어진 지역 정보와 길 정보를 바탕으로, 각 부대원이 ..

https://school.programmers.co.kr/learn/courses/30/lessons/388352 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  문제 개요비밀 조직의 보안 시스템을 해독하기 위해, 1부터 nnn까지의 숫자 중 서로 다른 5개 숫자로 이루어진 비밀 코드를 찾아야 합니다. m번의 시도를 할 수 있으며, 각 시도마다 입력한 5개의 숫자와 비밀 코드 간의 일치하는 숫자의 개수를 확인할 수 있습니다. 주어진 m번의 시도 결과를 바탕으로, 가능한 비밀 코드 조합의 개수를 구하는 문제입니다.  문제 접근 방법모든 가능한 5개 숫자의 조합을 생성1부터 n까지의 숫자 중 5개를 선택..