https://www.acmicpc.net/problem/14940 이 문제는 정석적인 BFS 문제라고 볼 수 있다.중요한 포인트는 BFS 시작점을 (0,0)으로 두지 말고 목표 좌표로 설정해야하는 것이다. 전체코드import java.io.*;import java.util.*;public class Main { private static int N,M; private static boolean[][] visited; private static int[][] map, result; private static int[] dirX = {1,0,-1,0}; private static int[] dirY = {0,1,0,-1}; public static void main(Stri..

https://softeer.ai/practice/7594 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai  처음에 DFS로 일반적인 4가지 방향 백트래킹을 구현했는데, 고민을 하다보니 전체를 탐색하면서 아래와 오른쪽으로만 이동하게 탐색하는 것 만으로도 충분히 쌍을 만들 수 있다는 것을 파악했다. 또한 기존에 내가 구현하던 DFS로는 모두 연결된 쌍만 구현이 된다고 생각했는데 DFS내에서 2차원 반복문으로 map전체를 탐색하게 하니 떨어져 있는 쌍도 만들어서 경우의 수를 계산할 수 있었다. 전체 코드import java.io.*;import java.util.*;public class Main { private static BufferedReader br; private ..

https://softeer.ai/practice/6273 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 이 문제는 레일의 순서를 임의로 변경 가능하기 때문에 각각의 경우의 수를 모두 찾아서 그 중 최소값을 찾는 문제라고 생각했고, 백트래킹을 사용하면 된다고 판단했다. 백트래킹을 사용하기 전 시간복잡도를 먼저 알아보자면레일의 개수는 최대 10개이고, 일의 시행 횟수는 최대 50이기 때문에 worst case 여도 10 x 50 = 500번 정도 이기 때문에 충분히 O(n^2) 작업도 가능하다. 1. 만들어질 수 있는 모든 레일의 경우의 수를 구한다.2. 각각의 경우 마다 광우가 들 수 있는 택배의 무게를 구한다.3. 각 경우의 수마다 구해진 택배 무게 중 최소값을 찾는다. 1. 레..

https://softeer.ai/practice/6248 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai  그래프 알고리즘에 DFS 알고리즘을 사용하면 될 것이라고 생각했고, 제약조건이 N  200,000 이기 때문에  시간복잡도 O(N + M)으로 충분히 효율적인 풀이 방법이라 생각했다. 하지만 그래프 구현까지만 가능했고, dfs를 통해 어떻게 방문을 했는지 헤매게 되어 결국 정답을 보았다. 검색한 코드import java.io.*;import java.util.*;public class Main { private static int N,M,S,T; private static List> graph = new ArrayList(); private static Lis..

https://softeer.ai/practice/6293 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 다음 문제는 처음에 이중 반복문으로 쉽게 풀 수 있다고 생각했지만 현재 밟고있는 돌을 기준으로 다음 돌을 건너뛸 수 있기에 복잡하다 생각하였다. 일단 문제의 제약조건을 보면 N이 최대 3 x 10^3 이기 때문에 시간복잡도 O(n^2) 이 가능하다는 것을 알았다.알고리즘으로는 어떤 것을 사용해야 할지 고민하다가 현재 밟고있는 돌과 다음 돌을 밟았을 때의 카운트 크기를 비교하기 위해 dp를 사용하기로 했다. 전체 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] ..

https://softeer.ai/practice/6294#pop_user Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai이번 문제는 어려운 알고리즘이 존재하진 않았다고 생각하고 배울만한 점은 StringTokenizer 선언하는 위치에 대해 확실하게 알게된 점이랑 소수점 반올림 방식 중 String.format("%.nf", 숫자) 을 사용하여 소수점 n의 자리까지 표현 가능한 것을 배웠다. 전체 코드import java.io.*;import java.util.*;public class Main { private static int[] grades; public static void main(String[] args) throws IOException { B..

https://softeer.ai/practice/11001 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai해당 문제는 정렬 문제로 쉽다고 생각할 수 있지만 특정 조건들 때문에 복잡하다고 느꼇고, 커스텀 정렬을 구현해야해서 시간이 걸렸다.문제일반적인 비내림차순 정렬일 경우 sort() 메서드 한 번이면 되겠지만 아래와 같은 조건들 때문에 커스텀 정렬을 구현함 [조건]1. 소수점을 기준으로 x,y로 나누어 x1과 x2의 값이 같을 경우, y1과 y2의 크기로 정렬한다.ex) 1.11 과 1.3 인 경우 1.11 > 1.3 이다. 2. 소수점이 없는 경우 x의 값이 같으면 소수점이 있는 수가 더 크다ex) 1 과 1.0 인 경우 1 정렬 코드// [커스텀 정렬 방식]// 반환값이 양수면..

https://www.acmicpc.net/problem/14501 해당 문제는 처음엔 백트래킹으로 풀려고 했지만 다시 확인해보니 최고 수익을 찾아야 하는 문제이기 때문에 DP로 진행하였다.  중요한 점은 범위를 넘지 않는 선에서 금액을 더해가야한다. if (i + workingTime[i] 예를 들어 i=0 일때, 0+workingTime[0]=7을 넘어가지 않기 때문에 이 코드가 실행되어 dp[3]=10이 된다. 그런데 이 코드만 계속 실행 되면 dp의 값이0 0 0 10 0 0 0 0  0 0 0 10 0 0 20 0  0 0 0 10 0 0 20 0  0 0 0 10 30 0 20 0  0 0 0 10 30 0 45 0  0 0 0 10 30 0 45 0  0 0 0 10 30 0 45 0 이렇게..