Algorithm (17) 썸네일형 리스트형 [탐욕법,LIS] 반도체 설계(최장증가수열) 문제 TIP 위와 같이 다음 수가 이전 수보다 커야 하는 증가하는 수열을 풀기위해 LIS 알고리즘이라는 것이 따로 있다. LIS 알고리즘 일반적으로 DP로 풀어야 할 문제이다. DP 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include #include using namespace std; int arr[1001]; int dp[1001]; int ans; int N; int main() { cin >> N; for(int i = 1; i > arr[i]; int here = 0; for(int j = 1; j arr[j]) here = max(here, dp[j]); } dp[i] = here + 1; ans = max(ans, dp[.. [탐욕법] DNA (특정 요소의 개수 세기) 문제 TIP 1. 알파벳과 같이 어떠한 값이 나올지 이미 예측되는 경우에는 배열의 인덱스에 각각 그 값을 부여할 수 있다. 예를 들어 해당 문제의 배열 dnaCounter[4]는 A C G T 순으로 임의로 부여하였다. 이를 새로운 값이 나올때마다 객체의 새로운 인자로 추가하는 식은 문제를 어렵게 한다. 2. Hamming Distance의 합은 차이를 모두 더할 수도 있지만, 모든 문자열에서 같은 문자열을 빼는 것으로 쉽게 얻을 수도 있다. 꼭 합이라고 덧셈만을 고집하지 말자. 3. for문과 if문이 어떤 결과를 가져올지 눈으로 확인하기 전에 머리로 이해하자 CODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 .. [탐욕법 - 문자열 다루기] 문제 TIP 1. 두 단어를 비교하여 같이 만들어주어야 할 때, 실제로 같이 만들어 줄 필요가 없다. 2. 두 단어를 비교할 때 단어를 실제로 줄이고 늘리고 할 필요 없이 단어 길이의 차이만큼 반복하거나 인덱스를 이동하므로써 해결 할 수 있는 경우가 많다. CODE 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include #include using namespace std; int main() { int answer = 9999; string a; string b; cin >> a; cin >> b; int diffLength = b.size() - a.size(); for(int i=0; i 탐욕법 탐욕법은 DP처럼 최적해를 구하는데 사용되지만. DP 처럼 모든 경우가 아닌 어떤 상황의 최대값을 규칙을 찾아 구한다. 그렇기 때문에 효율적이나, 그 만큼 정확하진 못하다. 탐욕법은 DP와 달리 배열을 순회하며, 그 배열을 직접 조절하여 답을 찾는 경우가 많다. 조건에 맞는 배열을 만든 후 답을 출력 하는 패턴을 가지는게 일반적이다. 패턴을 찾기 위해서 배열 정렬을 자주 사용한다. 체육복 맨 앞과 맨 뒤의 학생의 경우에 index를 벗어나는 경우만 신경 써주자. 나머지는 lost가 reserve를 만날때, 값을 수정해주며 답을 찾으면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34.. [DFS/BFS] 여행경로 문제의 핵심은 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. 이다. 예를 들어 [["ICN", "ATL"], ["ICN", "SEO"], ["SEO", "ICN"]] 와 같은 경우 알파벳 순서대로라면 ICN -> ATL 이후에 연결될 수 없으므로 ICN-SEO-ICN-ATL와 같이 연결되어야 한다. DFS로 해결하기 위해서 모든 경로의 답을 담아두는 dfsArray를 만들어두고 모든 경로를 돈 경우에만 answer에 더해 마지막에 정렬을 통해 정렬된 답을 도출했다. 주의할 점은 splice를 통하여 타겟이 된 티켓을 배열에서 제거하였다는 점이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 var answer = []; f.. [스택/큐2] 기능개발, 주식가격, 계산기 기능개발 조건에 맞는 값들을 queue에 쌓아두고 while문을 이용하여 모두 제거하는 식의 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 function solution(progresses, speeds) { var answer = []; let counter = 0; while(progresses.length) { for(let i = 0; i= 100){ progresses.shift(); speeds.shift(); counter++ } if(counter) { answer.push(counter); counter=0; } } return answer; } 주식가격 설명 없음 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1.. [스택/큐] 프린터, 탑, 쇠막대기, 다리를 지나는 트럭 스택 큐 문제는 어떤 패턴을 가지고 있느냐에 따라 결정된다. 그런 만큼 많이 풀어보고 다양한 상황에 대처 할 수 있는 수 밖에 없을 것 같다. 프린터 차분하게 조건에 따라 입력하자 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 function solution(priorities, location) { const map = priorities.map((value,index)=>{ return { id : index, priorities : value } }) let count = 0; while(true){ let target = map.shift(); let moreUpper = map.find((value)=>{ return value... [DP] 가장 큰 정사각형 찾기/ 땅따먹기 dp처럼 배열에서 조건에 맞는 값들을 이전값과 비교하여 하나씩 처리해가지만, dp배열을 추가적으로 필요로는 하지 않는 문제. 그림처럼 현 인덱스의 좌, 상, 좌상의 값이 모두 1이상이면 정사각형이라고 판단되어 진다. 이 때, 좌, 상, 좌상값중 가장 작은 값에 +1 한 값을 현 index에 더해준다. (변이 하나 늘었음을 의미한다.) 인덱스의 값의 제곱한 값이 곧 정사각형의 넓이가 된다. 예시는 최대값 3인 넓이 9의 정사각형을 리턴한다. 그리고 넓이가 1인 경우에는 하나라도 1이 있다면 1을 리턴해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 function solution(board) { var .. 이전 1 2 3 다음
