꾸물꾸물 졔의 개발공부

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net [알고리즘] DFS + DP 출발지에서 도착지까지의 경로를 찾기위해 그래프 탐색 방법 중 DFS 구현 (최단거리 구하기 x) 🌟고려해야 할 부분 1. 그래프의 최대 크기 : 500 x 500 2. 모든 지점에서 4방향으로 이동이 가능할 경우, 스택에 엄청난 재귀함수가 쌓이면서 메모리초과가 발생 할 수 있다. 3. DP를 사용하여 이미 탐색한 경로에 대해서는 중복 연산을 제거한다. dp[x][y] = 해..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 🌟 String 클래스의 replace 함수를 사용해서 반복했더니, 메모리 초과 발생 알고리즘 Stack으로 접근 주어진 문자열을 문자로 쪼개어 push 스택의 크기가 폭발문자열의 길이 이상이 될 경우, 폭발문자열이 스택에 포함되어있는지 확인 만약 포함되어 있다면 pop 구현 과정 Stack stack : 주어진 문자열을 문자로 쪼개어 저장할 스택 String s, bomb : 입력..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net ⏰ 친구관계를 행렬로 구현했더니 시간초과가 났다. > 인접리스트로 알고리즘 최소 4개의 친구관계(A→B→C→D→E)가 연결되어 있는지 확인하기 위해 깊이우선탐색인 DFS로 구현 백트래킹 주어진 친구관계는 인접리스트로 구현 ( 인접행렬시 시간초과 ) 사람의 수가 5명보다 많더라도, 만족하는 친구관계는 주어진 4개만 만족하면 된다. (=DFS에서 탐색 깊이가 4이상이면 친구 관계 존재) 구현 과정 ArrayList list : 주어진 친구관계를 저장하기 위한 인접리스트 checked[] : DFS 탐색에서..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net ⏰ 모든 육지에 대해 시작 육지와 도착 육지를 정해놓고 이중 포문으로 bfs를 탐색을 반복했더니 시간초과 알고리즘 육지-육지간의 최단거리로 이동하는 경로 중, 서로 가장 먼 거리 찾기 최단거리는 BFS로 접근 모든 육지에 대해 다른 육지로의 최단거리 중 가장 먼 거리 찾기 → 완전탐색 구현 과정 List list : 육지의 위치(x,y)를 저장한 배열리스트 bfs(int i) : list의 i번째 인..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net https://www.acmicpc.net/problem/15656 ..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net https://www.acmicpc.net/problem/15651 15651번: ..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 알고리즘 BFS + 시뮬레이션 빙산이 있다면, 사방의 바다 수 만큼 빙산 녹인다. 녹인 후, 빙산이 몇 덩어리로 분리되어있는지 확인, BFS로 탐색 구현 과정 map[][] : 북극을 표현한 2차원 배열 ice_list : 빙산이 있는 곳의 위치를 저장한 리스트 melt : 시간 당 각 빙산이 줄어들 높이를 저장한 큐 1️⃣ 북극 정보를 입력받아 map에 저장한다. 만약 map의 값이 0보다..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 알고리즘 BFS / 다익스트라 가중치가 0-1 이어서, 다익스트라로만 풀릴 줄 알았는데 BFS 로도 풀렸다. BFS visited[] : 방문체크 boolean형 배열 PriorityQueue : bfs를 위한 우선순위큐, 각 위치에 도달하는 시간이 짧을수록 우선순위가 높다. 1. { +1, -1, *2 } 의 경우에 대해서 0~100,000의 범위를 벗어나거..