문제https://www.acmicpc.net/problem/14461 풀이2차원 배열에서 최단 거리를 구하는 문제이며 추가적으로 가중치를 고려해야 하는 문제입니다. 3칸마다 본인의 위치에 있는 풀을 뜯어먹어야 하고(가중치) 그리고 한 칸 이동시 T초의 시간이 걸리는 점을 바탕으로 1. bfs 탐색으로 해결합니다. 2. 3차원 전역 방문 배열 → 현재까지 얼만큼 이동했는지(0, 1, 2) 3. 다음 칸의 방문 여부 확인 해야합니다. 4. 다음 칸으로 이동 시 현재 2번 이동했을 경우 → 이동횟수 0번으로 초기화 및 curr.d = curr.d + map[nr][nc] + T; 이외의 경우(현재 0, 1번 이동) → 이동횟수 증가 및 curr.d += T; 코드import java.io.*;..
문제12834번: 주간 미팅 풀이집에서 목적지(KIST, 씨알푸드) 2곳에 모두 도달하는지 여부와, 도달 한다면 모든 사람의 최단 거리의 합을 출력하는 문제입니다.한 사람의 최단 거리는 (집-KIST의 최단 거리) + (집-씨알푸드의 최단 거리)도달하지 못하면 최단 거리는 -1 따라서, 집 기준으로 다익스트라를 이용해서 도달 여부 및 최단 거리를 구해주면 됩니다. 코드import java.io.*;import java.util.*;class Main { static final int INF = 1 [] list; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRe..
문제https://www.acmicpc.net/problem/4811 풀이 및 코드병 안에 있는 N개의 알약을 하나 꺼내서부서지지 않은 알약을 쪼개고 먹을지, 부서진 알약을 먹을지에 포인트를 두고 풀면 되는 문제입니다.완전 탐색으로 해당 문제를 접근하게 되면 N이 최대 30이므로 시간초과가 발생합니다.따라서 해당 문제는 DP 메모이제이션을 해주어야 합니다. 두 가지 방법으로 풀어보았습니다. 1) 배열에 기록 및 map을 활용한 방법choice 배열을 두고 매 depth마다 W / S를 기록해두고depth가 2*N이 될 때 choice 배열을 바탕으로 문자열로 만들어줍니다.해당 문자열이 map에 포함되어 있지 않다면, map에 넣어주고 return 1포함되어 있다면 return 0을 해주는 방식으로 해결..
문제https://www.acmicpc.net/problem/1182 풀이주어진 수열의 부분집합(수열)의 합이 S를 만족하는 개수를 구하는 문제부분집합을 구하는 공식을 활용하면 쉽게 풀 수 있는 문제주의해야 할 점은 공집합일 때의 케이스를 제거해주어야 함 공집합 케이스를 제거해주기 위해서N개를 뽑고나서 방문 배열이 모두 false일 경우는 카운팅을 해주지 않았음 코드import java.io.*;import java.util.*;class Main { static int N, S, ans; static int[] arr; static boolean[] v; public static void main(String[] args) throws IOException { Buff..
N과 M (1)문제https://www.acmicpc.net/problem/15649풀이N개 중 M개를 순서대로 중복없이 뽑는 경우의 수 출력하는 문제일반 순열 문제이며 백트래킹으로 구현코드import java.io.*;import java.util.*;class Main { static int N, M; static int[] arr; static boolean[] v; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReade..
문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 코드1. 2중 for문을 이용한 풀이class Solution { public int[] solution(int[] prices) { int N = prices.length; int[] ans = new int[N]; for (int i = 0; i prices[j]) break; } } return ans; }}2. stack 자료구조를 이용한 풀이import java.util.*;class Solution { public..
문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이턴제 형식의 시뮬레이션 문제입니다.해당 문제에서는 트럭이 다리를 건너는 것을 직관적으로 구현하기 위해 큐 자료구조를 사용했습니다. 다리(큐)를 다리 길이만큼 빈 공간(0)으로 채워줍니다.모든 트럭이 다리를 건널 때까지 반복문을 돌며 매 턴마다 실행되야 할 부분은 1. 시간 증가2. 다리의 맨 앞에 위치한 트럭 or 빈공간 추출(트럭이 이동하는 것을 직관적으로 표현하기 위해)3. 다리에 트럭이 올라갈 수 있는지 여부를 판단하고 올라갈 수 있다면 트럭 삽입 or 빈공간 삽입코드import java.util.*..
문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이문제대로 큐를 사용하며 타겟 인덱스가 몇 번째로 나오는지를 찾는 문제입니다. 문제 그대로 큐를 사용해서 순차적으로 빼서 우선순위가 높은 것을 찾고다시 넣고를 반복해서 해결할 수는 있지만 시간이 오래걸립니다. 다양한 방법이 있겠지만우선순위 큐를 하나 더 사용해서 해결했습니다.인덱스와 우선순위를 담았고, 우선순위를 기준으로 내림차순 정렬하는 최대 힙을 이용했습니다. i) 큐에서 하나를 뺀 값의 우선순위가, 우선순위 큐의 맨 앞에있는 값의 우선순위와 동일하다면가장 우선순위가 높기 때문에 프로세스를 실행하고이때의..
