코딩테스트

주의점왕복 거리를 구하는 것모든 경우 따져야 하는 것알고리즘 선택과 근거플로이드 워셜간선 최단 거리를 구해야하는 문제모든 정점을 따져야한다.다익스트라: 하나의 정점에서 모든 정점까지 최단거리음수 불가추후 탐색할 때 다익스트라 로직을 여러번 실행해야함벨만포드: 하나의 정점에서 모든 정점까지 최단거리음수 가능음수 탐지 가능문제는 두개의 정점(치킨집)을 구해야해서 여러번 계산해서 비효율적플로이드: 여러개의 정점에서 여러개의 정점까지 최단거리음수 가능But 음수 사이클은 불가그러나 문제는 음수 사이클이 없음접근 방법 (플로이드 워셜)플로이드 워셜 설명 (추후 링크로 변경)문제 예시 1번으로 설명 Node (도시) 는 5개 Edge (도로) 는 4개 있다.플로이드 워셜을 이용하기 위해 2차원 배열을 만들어준다.자..

링크https://www.acmicpc.net/problem/22251 주의점0층 제외 알고리즘 선택과 근거브루트포스모든 층을 다 봐야한다.구현디스플레이 구현 접근 방식 디스플레이 표현디스플레이를 이렇게 표현했다. 1번이 켜져있으면 0010010 이렇게 표현한다. 3이면 1011011 자릿수1. 최대 자릿수가 같을 때까지 현재 층이나 호석이 층이나 둘 다 0 계속 추가2. 체크할 때 자릿수마다 바뀐 LED 수 체크 하면 된다. 정답import java.io.*;import java.util.*;public class Main { static String[] num = {"1110111", "0010010", "1011101", "1011011"..

퇴사https://www.acmicpc.net/problem/14501 알고리즘 선택과 근거DP + 누적합단순 구현으로 풀 수 있을 듯하나, DP로 푸는 게 더 좋아보임 정답 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

링크https://www.acmicpc.net/problem/14889 알고리즘 선택과 근거브루트포스모든 경우의 수를 따져야한다.백트래킹경우의 수 중복 방지 정답 코드import java.util.*;import java.io.*;public class Main { static boolean[] visited; static int[][] arr; static int answer = Integer.MAX_VALUE; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

링크https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 주의점탐색할 때마다 MAX 값을 구하는 연산을 하면, 효율성 측면에서 매우 불리해진다. 알고리즘 선택과 근거DFS최단 거리를 구하는 문제가 아니다. 그래서 BFS 는 고려하지 않았음MAX 값을 구하는 게 중요하다.메모이제이션탐색 할 때마다 MAX 값을 구한다고 하면, 효율성 측면에서 매우 불리해진다.석유 탐색석유 덩어리를 하나의 Team 이라고 정의하고 DFS 돌릴 때 Team 배열에 해당 Team 석유 매장량을 저장한다.석유 시추팀 방문..

주소https://www.acmicpc.net/problem/2309 주의점아홉 난쟁이 중 일곱 난쟁이만 산출한다.일곱 난쟁이 키의 합은 100 이다.일곱 난쟁이를 찾을 수 없는 경우는 없다. 알고리즘 선택과 근거브루트포스 알고리즘- 문제의 달성 조건이 명확하다.- 정답이 여러개일 수 있으나 풀이의 수가 제한되어 있다. 풀이import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int sum = 0; int[] arr = new int[9]; // 스파이 난쟁이 초기값은 배열 ..