알고리즘

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 📌 - 문제 해결 방법 구해야 하는 횟수가 10만이기 때문에 시간초과가 날 수 있기 때문에 DP로 문제를 해결해야한다. 먼저 해당하는 전체 구간의 합들을 DP배열에 갱신을 한다. 해당하는 구간의 합을 구하는 방법은 해당하는 칸의 구간합 -> dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + arr[i][j] 구한..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 📌 - 처음 접근한 방법 내리막이 나올때마다 그 칸의 값을 다음 내리막 칸의 값에 더해준다 모든 경로를 전부 탐색해서 마지막 칸의 값을 출력 이렇게 브루트포스로 풀었었는데, 바로 메모리 초과가 났다 📌 - 두번째 접근 방법 시간초과와 메모리초과를 동시에 해결하려면 DFS만으로는 풀 수가 없다. DFS나 BFS를 사용하면서 DP개념을 활용해야 이 문제를 해결 할 수 있다. DFS로 경로의 끝까지 ..

https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📌 - 무인도 여행 - 접근 이 문제는 map의 크기도 100으로 제한되어 있고, 상,하,좌,우를 이용하면서 해당하는 경로의 숫자를 전부 더해주는 방식이라 DFS, BFS 문제라고 생각했고 백준의 안전 영역이나 빙산 문제와 비슷하다고 생각해서 BFS로 풀었다. 0,0부터 N,M까지 전부 탐색하면서 방문체크 방문하지 않은 섬일때 BFS를 이용해서 인접한 섬들의 수를 더해주고 다시 방문체크 인접한 ..

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 해당 문제는 전에 푼 토마토 문제와 매우 유사하다. 본인이 푼 해결 방식은 이러하다 - 이 문제는 결국 낮은 숫자의 바이러스들부터 큰 숫자의 바이러스들까지 순서대로 퍼지게 만드는 것이 요점인데 순서를 정렬하기 위해 힙큐를 써서 해결을 했다. for 문으로 전체 배열을 돌면서 0이 아닌 바이러스들을 힙큐에 넣는다. 1초마다 BFS로 힙큐를 비우면서 인접한 배열의 정보를..

📌 - 중복되는 연산을 줄이자 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제가 있다. 컴퓨터 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. ❗️- 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야한다. 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는 방법이 바로 다이나믹 프로그래밍이다. 👉 대표적인 예시 - 피보나치 수열 - n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수 - 단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1 피보나치 수열을 재귀함수로 만들 수..

🗒️ 위상 정렬이란? 위상정렬이란 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 이해하기 쉽게 예를 들자면 위상 정렬을 수행하게 되는 예시로는 여러 게임들의 직업 시스템을 들 수 있다. 예를 들어 직업 시스템에는 '모험가'로 시작해서 '마법사'가 될 수 있다. 이때 '모험가' 및 '마법사'를 각각의 노드로 표현하고, '모험가'에서 '마법사'로 이어질 수 있도록 방향성을 갖는 간선을 그린다. 그래프에서 선후 관계가 있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 전체 순서를 계산할 수 있다. 다시 예를 들면 직업의 단계가, '마법사'가 되기 위해선 '모험가'여야 하고, '대마법사'가 되기 위해서는 '마법사'여야 한다고 가정하자. 이 경우에서 '대마법사'가 되기 위해서..