jujucode

https://school.programmers.co.kr/learn/courses/30/lessons/468373 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약n개의 배양체가 트리 형태로 연결되어 있고, 각 파이프는 A/B/C 세 종류 중 하나다. 하나의 배양체가 바이러스에 감염된 상태에서 시작하며, 같은 종류의 파이프를 한꺼번에 열었다가 닫는 행동을 최대 k번 반복해 감염을 최대한 퍼뜨려야 한다. 한 종류를 열면 그 종류로 연결된 경로를 타고 감염이 쭉 퍼진다. 최종적으로 감염될 수 있는 배양체 수의 최댓값을 구하면 된다.n ≤ 100, k ≤ 10이라는 제약이 핵심 힌트다. 처음엔 그래프 문제니..

https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약집들이 원형으로 배치돼 있고, 인접한 두 집을 동시에 털면 경보 울림. 각 집에 있는 돈이 담긴 배열이 주어질 때 훔칠 수 있는 최댓값 구하는 문제. 일반적인 "집 도둑" DP 문제인데 원형이라는 게 함정.핵심 아이디어일렬로 늘어선 집이면 그냥 기본 DP로 풀림: dp[i] = max(dp[i-1], money[i] + dp[i-2]) i번째 집을 털거나 안 털거나 둘 중 큰 값 택하는 거.근데 이 문제는 원형이라 첫 집이랑 마지막 집이 서로..

https://school.programmers.co.kr/learn/courses/30/lessons/1843 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약숫자랑 +, -가 섞인 배열이 주어지는데, 괄호를 어떻게 치느냐에 따라 계산 결과가 달라짐.. 가능한 모든 괄호 경우의 수 중에서 최댓값을 구하는 문제다.예를 들면 1 - 3 + 5 - 8 이거 괄호 위치 바꾸면 -15부터 1까지 결과가 막 달라짐. 이 중에 제일 큰 값 찾으면 됨. 핵심 아이디어포인트는 최댓값이랑 최솟값을 둘 다 저장해야 한다는 거.왜냐면 A - B 형태를 최대로 만들려면 A는 최대, B는 최소여야 하는데, B가 최소가 되려면 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약집에서 학교까지 가는 길이 m x n 격자로 되어있고, 오른쪽/아래쪽으로만 움직여서 집(1,1)에서 학교(m,n)까지 가는 최단경로의 개수를 구하는 문제다. 중간에 물에 잠긴 칸(puddles)은 지나갈 수 없음. 답은 1,000,000,007로 나눈 나머지.딱 보고 "어 이거 격자 탐색이네" 하면서 반사적으로 BFS 코드부터 짰다 (dp 카테고리인데 그래도 bfs도 되지 않을까 했음 ;;)시행착오 1 - BFSfrom collections ..

https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약삼각형 모양으로 숫자가 배치되어 있고, 꼭대기에서 바닥까지 내려가면서 거쳐간 숫자의 합이 최대가 되는 경로를 찾는 문제다. 이동은 바로 아래 칸이 아니라 대각선으로 한 칸만 가능하다 (왼쪽 아래 또는 오른쪽 아래). 7 3 8 8 1 0 2 7 4 44 5 2 6 5이 예시에서 정답은 30이다.알고리즘 / 핵심 아이디어딱 봐도 완전탐색으로 풀면 경로 수가 지수적으로 늘어나서 큰 입력에서는 못 버틴다. 삼각형 높이가 최대 500이라 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42895# 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약숫자 N을 여러 번 쓰고 사칙연산(+, -, *, /)이랑 괄호만 써서 목표 숫자 number를 만드는 문제다. N을 최소 몇 번 써야 number를 만들 수 있는지 구하면 됨. 8번 넘게 써야 한다면 -1을 리턴.예를 들면 5로 12를 만드는 방법 중에5 + 5 + (5/5) + (5/5) → 5를 6번55 / 5 + 5 / 5 → 5를 5번(55 + 5) / 5 → 5를 4번이렇게 여러 방법이 있는..

https://school.programmers.co.kr/learn/courses/30/lessons/12979 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약N개의 아파트가 일렬로 늘어서 있고, 일부 아파트에는 이미 4g 기지국이 설치되어 있다. 4g 기지국을 도달 거리 W인 5g 기지국으로 교체하면 전파가 닿지 않는 아파트가 생기는데, 모든 아파트에 전파가 닿도록 최소 몇 개의 5g 기지국을 추가로 설치해야 하는지 구하는 문제다. N은 최대 2억, stations 크기와 W는 각각 최대 10,000이다.알고리즘/핵심 아이디어단속카메라와 비슷하게 그리디로 풀 수 있지만, 방향이 반대다. 단속카메라..

https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약고속도로를 지나는 차량들의 진입/진출 구간이 주어진다. 모든 차량이 카메라를 최소 한 번은 만나도록 카메라를 설치할 때, 필요한 카메라의 최소 개수를 구하는 문제다. 진입/진출 지점에 카메라가 있어도 만난 것으로 친다.알고리즘/핵심 아이디어전형적인 그리디 구간 커버 문제다. 이런 유형은 끝나는 지점 기준 정렬 + 그리디로 푼다.차량의 경로(구간)를 진출 지점 기준으로 오름차순 정렬한다.카메라 위치를 아주 작은 값(-30001)으로 초기화해둔다...

https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약n개의 섬 사이에 다리를 건설하는 비용이 주어진다. 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 구하는 문제다. 다리를 여러 번 건너서라도 도달만 가능하면 통행 가능한 것으로 간주한다.섬의 개수 n: 1 이상 100 이하costs[i] = [섬 A, 섬 B, 두 섬을 잇는 다리 비용]같은 연결은 두 번 주어지지 않음알고리즘 / 핵심 아이디어이 문제는 그래프에서 모든 노드를 최소 비용으로 연결하는 문제이므로 최소 스패닝 트리(M..

https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약숫자 문자열 number에서 k개의 숫자를 제거했을 때 만들 수 있는 가장 큰 수를 구하는 문제다.예를 들어 "1924"에서 2개를 지우면 [19, 12, 14, 92, 94, 24]를 만들 수 있는데 이 중 가장 큰 건 94.이걸 완전탐색으로 풀려고 하면 자릿수가 백만 자리까지 가는 순간 답이 없다.. 그래서 그리디로 접근해야 한다.알고리즘 / 핵심 아이디어처음엔 "작은 수부터 앞에서부터 비교하면서 더 큰 수를 찾자"는 생각까지는 했는데, ..