![]()
📖 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 풀이 방식• DP[점화식]dp[i] = Math.max(dp[i-1], dp[i-2] + sticker[i]) 0번째 스티커를 뗐느냐/안 뗐느냐 여부에 따라 숫자의 합을 다르게 구한다. 1) 0번째 스티커를 뗀 경우, 1번째와 마지막 스티커는 뗄 수 없다.// dp 배열 초기값dp1[0] = sticker[0];dp1[1] = sticker[0]; 2) 0번째 스티커를 떼지 않은 경우, 마지막을 뜯을 수 있다.// dp 배열 초기값dp2[0] = 0;dp2[1] = sticker[..
![]()
📖 문제 https://www.acmicpc.net/problem/15723 💡 풀이 방식• 플로이드-워셜 i는 k고, k는 j면, i는 j다. - N개의 전제를 입력받으며 a는 b라고 처리한다. → connected[a][b] = true- 플로이드-워셜로 i는 k고, k는 j면, i는 j 가 되도록 처리한다.- M개의 결론이 맞는지 확인하며 a는 b라면(= connected[a][b] == true) T를, 아니라면 F를 출력한다. 🔺 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748import java.util.*;import java.io.*; public class Mai..
![]()
📖 문제 https://www.acmicpc.net/problem/1504 💡 풀이 방식• 다익스트라필요 자료구조- 인접 배열 리스트- 시작점에서 각 정점까지 가는 최단 거리 저장용 int형 배열- N개의 각 정점에 대한 boolean형 방문 표시 배열- (목적지, 거리) 정보를 저장하는 객체 1. E개의 입력을 받으며 두 정점 간 거리 정보를 양방향으로 저장한다.2. 꼭 지나쳐야 하는 두 정점 v1, v2를 입력받는다.3. ① 경로 1 > v1 > v2 > N을 지날 때의 최단 거리와, ② 경로 1 > v2 > v1 > N을 지날 때의 최단거리를 계산한다. (다익스트라)4. 두 최단 거리가 모두 최댓값인 INF보다 크거나 같으면, 경로가 없는 것이므로 -1을 출력하고, 그게 아니라면 경로 1..
![]()
📖 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 풀이 방식• BFS + DP4가지 방향에서 오는 방향 별 최소 비용을 저장하기 위해 방향까지 합친 3차원 배열을 사용하는 것이 포인트!이 때, 단순 bfs로만 탐색하면 각 방향마다 달라지는 최소 비용을 지나칠 수 있으므로 dp (메모이제이션)을 사용한다. - 4방향 탐색을 할 때, 처음 실행하거나 방향이 바뀌지 않은 경우에는 현재 비용에서 +100원만큼, 방향이 바뀐 경우에는 +600원만큼 이동하도록 한다. (방향 전환하느라 +500, 직진하느라 +100 한 번 더 하므로)int next..
![]()
📖 문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 💡 풀이 방식• DFS필요 자료구조- 해당 응모 사용자 ID를 사용할지 판별 용 1차원 boolean형 배열- 현재까지 선택된 응모한 사용자 ID의 조합 집합 Set> result🔥 [제재 ID 목록 만드는 메소드 dfs(선택된 응모 사용자 ID 갯수, 현재까지 선택된 사용자 ID의 집합)]. 종료 조건 : 불량 사용자 갯수만큼 뽑았을 때, 여태 구한 제재 ID 경우를 집합에 넣는다.. 그만큼 뽑지 않았다면, 응모한 사용자 ID 배열을 돌면서 해당 사용자 ID와 현재 탐색 중인 불량 사용자..
![]()
📖 문제 https://www.acmicpc.net/problem/17142 💡 풀이 방식• 조합 + BFS[필요 자료구조]- 바이러스 객체 ⇒ (행,열, 거리 값) 저장- 인접한 4방향 탐색할 dx/dy 배열- 바이러스 위치 저장용 객체 리스트- 초기 빈 칸 개수 저장하는 int형 변수 zeroCnt 연구소의 상태를 입력받는다.빈 칸(0)인 경우, zeroCnt에 +1 한다.바이러스(2)인 경우, 해당 위치와 0을 리스트에 저장한다.빈 칸의 갯수가 0이라면, 0을 출력하고 종료한다. / 그게 아니라면, 바이러스 위치 중 M개를 뽑아 바이러스를 심고 퍼뜨리는 데 걸리는 최소 시간을 계산한다.M개 바이러스 뽑기 > 조합 (백트래킹)바이러스 퍼뜨리기 > BFS- M개 바이러스를 뽑았으면, 해당 위..
![]()
📖 문제 https://www.acmicpc.net/problem/16956 💡 풀이 방식• BFS 늑대 주변만 울타리로 감싸면 된다. 1. 늑대의 위치를 큐에 저장한다.2. 각 늑대의 위치들을 돌며 인접한 칸을 방문하며 이동할 다음 칸이 ① 빈 칸(.)인 경우에는 울타리를 설치하고, ② 양(S)이라면 함수를 종료한다.3. 만약 늑대가 양이 있는 칸으로 이동할 수 있다면 0을 출력하고 종료한다. / 이동할 수 없다면 1을 출력하고, 격자를 출력하낟. 🔺 코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970im..
![]()
📖 문제 https://www.acmicpc.net/problem/9944 💡 풀이 방식• 백트래킹1. 값을 입력받으면서 격자 안의 값이 장애물(*)인 경우, 방문 처리하고 방문한 칸의 갯수(cnt)를 1 증가시킨다.2. 한 칸만 빈 칸인 경우, 해당 케이스의 이동 경로 수는 0이다.if(cnt == N*M) answer = 0; // 한 칸만 빈 칸인 경우 3. 모든 칸을 탐색하며 방문한 적 없는 점에서,4방향 탐색을 통해 1) 격자 범위 내에 있고, 2) 방문하지 않은 칸을이동 처리했다가 안 했다가 하며 이동 경로 수를 구한다. (백트래킹)for(int i = 0 ; i [백트래킹 함수]- 인자 : x좌표, y좌표, 이동 횟수(result), 방향 번호(dir), 방문 갯수(cnt)s..
![]()
📖 문제 https://www.acmicpc.net/problem/16938 💡 풀이 방식• 백트래킹+ 브루트포스1. 문제들을 배열에 입력받고, 이 배열을 난이도 기준 오름차순 정렬한다.2. 2~N개까지 캠프에 사용할 문제들을 고른다. (백트래킹)for(int i = 2 ; i [백트래킹 함수] - (종료 조건) 목표 갯수만큼 뽑았다면, 문제에서 제시한 2가지 조건을 만족하는지 확인하고 방법 수를 갱신한다.(여기서 리스트를 오름차순 정렬하지 않는 이유는, 이미 배열을 입력받고 오름차순 정렬해두어서 리스트에 저장할 때 이미 오름차순으로 난이도를 저장해 두기 때문이다.)if(cnt == target) { int sum = 0; List list = new ArrayList(); ..
