꾸물꾸물 졔의 개발공부

https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net [알고리즘] '서로 다른 수 두개의 합'으로 나타낼 수 있다면 그 수는 좋은 수 수의 위치가 다르면 값이 같아도 다른 수 투 포인터 알고리즘을 사용하여 접근 [설계] 기본적으로 주어진 배열을 정렬해야 한다. (투 포인터 사용하기 위해) 배열의 값들을 하나씩 선택 ▷ (arr[0] ~ arr[N-1]) 선택한 값을 제외한 배열의 수들을 투 포인터로 탐색하며 선택한 수가 좋은 수 인지 판별. 선택한 두 수를 더하며(=sum) 조..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 🌟1261 알고스팟 문제와 거의 유사하다. [알고리즘] 검은 방을 최소한으로 흰방으로 바꾸고 이동하기 위해 최소비용 BFS 알고리즘 적용 [설계] 2차원 배열의 (0,0) 부터 이동 1. 검은 방: 흰방으로 바꾸고 (map[x][y] = 1) , 바꾼 방 갯수+1 후 이동 2. 흰 방: 그냥 이동 우선순위큐에 의해 가장 먼저 (n-1, n-1) 나왔을 때, 바꾼 방의 갯수가 최소값 (=답) Roo..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net [알고리즘] 벽을 최소한의 갯수로 부수고 목적지까지 다다르기 위해서 최소비용 BFS 알고리즘 적용 [설계] (1,1) 지점부터 시작하여 이동 1. 벽이 나올경우 : 벽 갯수+, 벽 부수기(0으로 변환) 후 이동 2. 빈 방이 나올경우 : 그냥 이동 탐색 중 (N,M) 위치가 나올 경우, 벽 갯수 반환 Point 클래스 1. 현재 위치, 현재까지 부순 벽의 총 갯수 저장 2. ..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net [알고리즘] 출발지에서 목적지까지의 최단 경로를 구하는 다익스트라 Dijkstra 1 → v1 → v2 → N / 1 → v2 → v1 → N 의 경로 중 최솟값 반환 경로가 존재하는지 확인하기 위한 flag값(isfirst, issecond)을 사용하여, 만약 둘다 경로가 없다면 -1 반환 [설계] (1 → v1 → v2 → N) / (1 → v1 →..

https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net [알고리즘] 가중치가 있는 그래프에서 목적지까지의 최단거리를 구하기 위한 다익스트라 Dijkstra 주어진 M개의 양방향 길을 리스트에 저장, 연결리스트로 그래프 구현 [설계] 우선순위큐를 사용하여 다익스트라 구현 min_cost 배열에 출발지로부터 각 지점까지의 최소비용를 저장한다. 만약 이동하며 더 작은 비용이 나올 경우, 최소비용을 갱신 Node 클래스 1. 헛간, 이동비용 저장 2. Comparab..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net [알고리즘] DP 다음 줄로 이동하면서 각 위치에서의 최대 점수, 최소 점수를 저장한다. 최종적으로 N개의 줄을 모두 이동했을 때, 마지막 줄에 저장되어 있는 최대 최소값 반환 두개의 DP 2차원 배열을 생성하여 최댓값/ 최솟값 따로 저장 dp[i][j] = (i,j) 위치에서 얻을 수 있는 최대 or 최소 점수 [설계] 한줄에 숫자가 3개씩만 있기 때문에 각 위치에 대해 조건을 나누어 dp 값을 구한다. 1...

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 : 입력..