DJ's Blog

https://softeer.ai/practice/7369 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai위 문제는 레벨3인데 정답률이 조금 낮아서 긴장하고 문제를 읽었다.. 그런데 백준에서 풀었던 문제와 매~우 유사해서, 장애물 없이 바로 풀 수 있었다. 백준 어떤 문제랑 비슷했더라.. 찾아봤는데https://www.acmicpc.net/problem/11048[11048번 이동하기] 문제와 매우 유사하다. 소프티어에서 다른점은,중간에 한 구역에서만 value*2 한 값을 했을 때의 최대값을 구하는 것이다. 백준에서는 d[n][m] 값으로 다이나믹한 값을 정하는 변수를 지정했다면,소프티어에서는 d[n][m][2] 로 배열값을 하나 더 추가하여,지나간 자리에 value*2 를 한 값..

알고리즘 2024. 10. 21. 22:55

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 이 문제에서는 배열 크기를 잘못 설정해줘서 런타임에러(ArrayIndexOutOfBounds)가 났다. 반례를 생각해내서 풀긴 했지만, 바로 생각해내지 못해서 글로 남겨본다. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System...

알고리즘 2022. 11. 21. 20:35

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 글을 쓰는 목적은 BFS 알고리즘을 한번 더 정리하고, 뱀과 사다리 게임 문제를 풀면서 놓쳤던 경우의 수를 기록해서 내 생각을 정리하고, 비슷한 실수를 반복하지 않기 위함이다. 위 문제는 그래프 탐색 알고리즘 중에서 BFS, Breadth-First Search 알고리즘에 해당하는 문제이다. 그래프란, 정점과 간선으로 이루어진 자료구조이다. 어떠한..

알고리즘 2022. 11. 11. 00:05

https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 이 글을 기재하는 이유는 그래프 탐색 알고리즘인 DFS와 BFS 개념에 대해 스스로 정리하기 위해서 이며, 알고리즘 로직을 잘못 짰을때 찾았던 반례와 잘못 생각했던 부분을 기록하여 나중에 잊어버리더라도 다시 생각하기 위해서이다. 우선, DFS란 그래프를 탐색하는 알고리즘 중에 하나이며 Depth First Search, 깊이 우선 탐색이다. 루트노드 또는 임의의..

알고리즘 2022. 11. 9. 23:54

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net DP를 이용해서 푸는 문제이다. 풀면서 한번 틀리고, 찾았던 반례에 대해서 적어보려고 한다. 배열 d는 인덱스값을 무게로 하고, 그 무게에서 가질 수 있는 최대값을 최대 가치 값(원하는 답)으로 둔 변수이다. 최대로 가질 수 있는 무게(K)가 7이라고 해보자. 무게(W)가 4이고 가치(V)가 8이라고 하면, d[4]에서 가질수 있는..

알고리즘 2022. 5. 5. 17:55

https://www.acmicpc.net/problem/1201 1201번: NMK 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 이 문제는 nmk 공식에 맞는 수열을 만드는 로직을 생각하고, 풀면서 생각하지 못한 여러가지 예외가 많이 나와서 애먹었다. 먼저, m값(길이가 가장 긴 증가하는 부분 수열)과 k값(길이가 가장 긴 감소하는 부분 수열)에 따라서 가능한 n값의 범위가 있다. (13~16번 줄) m 과 k 가 모두 3이라고 가정하면, n이 최소로 될 수 있는 값은 {3, 2, 1, 4, 5} → 5값(m+k-1)을 가질 수 있고 n이 최대로 될 수 있는 값은 {3, 2, 1, 6, 5, 4, 9, 8, 7} → 9값(m*k)을 가질 수 있다. n 안에서 증가하는 수열..

알고리즘 2022. 5. 2. 12:54

https://www.acmicpc.net/problem/1767 1767번: N-Rook II N * M 크기의 체스판에 K개의 룩을 놓을 때, 각 룩이 최대 1개의 룩에만 공격받는 경우의 수를 1,000,001로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 풀이를 보고 한참을 이해하지 못했는데, 내가 애초에 문제를 잘못 이해했기 때문이라는 것을 알았다.. 원래도 어려웠지만 그래서 더더욱 어려웠다.... [각 룩이 최대 1개의 룩에만 공격받는 경우의 수] 라는 것은 각 룩이 공격을 받지 않을 수도 있고, 받는다면 1개의 룩에게만 공격을 받는다. 이것은 모든 각각의 룩에게 적용이 되는 룰이다. 룩을 어느 자리에 하나 놓으면 그 룩이 속한 행이나 열에는 다른 하나의 룩만 놓거나 놓지 않..

알고리즘 2022. 4. 16. 00:10

https://www.acmicpc.net/problem/1557 1557번: 제곱 ㄴㄴ 어떤수 N이 1이 아닌 제곱수로 나누어지지 않을 때, 이 수를 제곱ㄴㄴ수라고 한다. 제곱수는 4, 9, 16, 25와 같은 것이고, 제곱ㄴㄴ수는 1, 2, 3, 5, 6, 7, 10, 11, 13, ...과 같은 수이다. K가 주어졌을 때, K www.acmicpc.net 이전 백준 문제는 화면을 캡쳐하고 몇번째 줄은 어떤 의미인지 설명했는데, 이 문제는 다시 풀 때 캡쳐해서 줄별로 설명하지 않고 의식의 흐름대로 주석으로 정리하면서 풀어보았다. import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { ..

알고리즘 2022. 4. 14. 14:14