알고리즘

문제 조건 분석입력: 두 개의 자연수출력: 최대 공약수, 최소 공배수설계최대 공약수 ⇒ 작은 수의 약수를 구하고 순회하며 더 큰 수의 약수인지 확인 ⇒ 그 중 가장 큰 값최소 공배수 ⇒ 큰 수*작은 수 이하까지 순회하며 주어진 수로 나눴을 때 나누어 떨어지는지 확인 ⇒ 그 중 가장 작은 값다른 풀이JS에서 최대공약수, 최소공배수를 구하는 더 깔끔한 풀이와 유클리드 호제법 이용한 방법들은 참고자료 아티클을 통해 확인할 수 있었다.참고자료JS로 GCD, LCM 구하기

문제 조건 분석입력: 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000), 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi. (-100,000 ≤ xi, yi ≤ 100,000)좌표는 항상 정수위치가 같은 두 점은 없다.출력: 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력설계이차 배열로 입력값 받아오기이후에 sort의 compareFn을 조건에 맞게 설계다른 풀이sort 비교함수 간단하면 분리 없이 이렇게 작성해도 괜찮을 것 같다.arr.sort(function (a, b) { if (a.x - b.x == 0) { return a.y - b.y; } else { return a.x - b.x; } });코드 개선forEach로 join하지 말고 sort 비교함수에서 구조 분해 할당으로 j..

문제 조건 분석입력: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000), 둘째 줄부터 N개의 줄에 수가 주어진다. 이 수는 절댓값이 1,000,000 이하인 정수이다. 수는 중복되지 않는다.출력: 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.설계sort 활용해서 정렬하기추가 공부join() 반환값Array.prototype.join()separator로 배열 원소들을 연결한 문자열 하나가 반환된다. 만약 빈 배열에 적용하면 빈 문자열이 반환된다.Number()new를 써서 생성자로 쓰면 Number 객체를 생성한다.함수로 사용하면 원시값을 Number 타입으로 변환해준다.반환값생성자로 쓸 때 : 강제변환 프로세스를 통해 Number 객체로 변환된 값을 반환한다. ..

문제 조건 분석입력: 첫째 줄에 명령의 수 N (1 ≤ N ≤ 10,000), 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.주어지는 정수는 1~100,000. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.출력: 한 줄에 하나씩 출력스택 구현하기설계push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.size: 스택에 들어있는 정수의 개수를 출력한다.empty: 스택이 비어있으면 1, 아니면 0을 출력한다.top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.⇒ 각각 함수로 분리해서 구현하기⇒ 출력은 pop, size, e..

문제 조건 분석입력:첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다.합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.출력3장의 카드의 합이 M 이하이면서 카드의 합을 최대한 크게 만드는 것각 카드에는 양의 정수가 적혀 있다.N장의 카드 중에서 3장의 카드를 골라야 한다.플레이어가 고른 카드의 합은 딜러가 외친 숫자 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.설계그리디로 풀 수 있나..?우선 내림차순으로 카드를 정렬합니다.순회하며 가장 큰 세 장을 더해 M을 넘는지 확인합니다.넘는다면 가장 큰 카드를 제외하고 다시 다음으로 ..

문제 조건 분석입력: 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000), 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi. (-100,000 ≤ xi, yi ≤ 100,000)좌표는 항상 정수위치가 같은 두 점은 없다.출력: 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력설계이차 배열로 입력값 받아오기이후에 sort의 compareFn을 조건에 맞게 설계다른 풀이sort 비교함수 간단하면 분리 없이 이렇게 작성해도 괜찮을 것 같다.arr.sort(function (a, b) { if (a.x - b.x == 0) { return a.y - b.y; } else { return a.x - b.x; } });코드 개선forEach로 join하지 말고 sort 비교함수에서 구조 분해 할당으로 j..

문제 분석입력값으로 받은 점수들 중 최댓값을 이용해 점수를 모두 변경해 새로운 평균을 반환하는 문제입력: 과목 개수 N, 점수들출력 : 첫째 줄에 새로운 평균 출력.실제 정답과 출력값의 절대오차 또는 상대오차가 10-2 이하이면 정답트러블슈팅소수점 표현(예제 참고)문제는 브론즈1에 기초적인 내용이라 금방 해결할 것으로 예상했으나, 예제를 꼼꼼히 보지 않아 여러 번 수정했습니다.조건 중에 첫째 줄에 새로운 평균을 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10-2 이하이면 정답이다. 라는 말이 있었는데, 상대오차를 부분을 간과하고 넘어가서 생긴 실수였습니다.이후 여러 예제들 중 10-2 이하의 오차를 허용한다는 말은 정확히 소수 2번째 자리까지 출력하라는 뜻이 아니다.라는 말과 함께 아래 예..

DP에는 크게 두 가지 문제풀이 방법이 있다.1) 재귀함수2) for문 1번의 경우 앞서 다른 포스팅에서 다뤘던 Memoization을 사용한다면,2번의 경우 순서대로 배열에 값을 채워가는 방식인 Tabulation을 사용한다. (이전에 작성한 Memozation, 재귀함수 방식) [알고리즘] DP 풀이에서의 메모이제이션 MemoizationDP 외에도 DFS/BFS 등등 여러 유형의 알고리즘에서 재귀함수를 사용할 때면 종종 마주쳤던 효율성 이슈,,그럴 수밖에 없는 것이, 재귀를 사용하면 하나의 해답을 얻기 위해 정말 많은 반복적인 연jimyu-s-record.tistory.com  set dp = [0, 0, 0, ...]dp[1] = 1dp[2] = 1for i = 3 ... i  이런 Tabulat..

DP 외에도 DFS/BFS 등등 여러 유형의 알고리즘에서 재귀함수를 사용할 때면 종종 마주쳤던 효율성 이슈,,그럴 수밖에 없는 것이, 재귀를 사용하면 하나의 해답을 얻기 위해 정말 많은 반복적인 연산이 필요하게 된다.이로 인한 시간 초과 문제를 해결할 수 있는 방법이 바로 메모이제이션! DP에서의 메모이제이션은 memo라는 배열을 만들어서 초기값은 답이 될 수 없는 값(-1도 많이 쓴다고 함)으로 설정하고, 계산이 이루어지면 memo 배열에 계산 값을 저장해주는 식으로 사용한다. 배열에 초기값이 들어있다면 계산을 진행하고, 아니라면 저장된 값을 가져와 사용하는 식이다. 이렇게 되면 중복 탐색을 예방할 수 있다. 아래는 피보나치 문제에 메모이제이션을 적용한 사례.memo = [-1, -1, -1, ...]..

이전에 스터디에서 작성한 DP 개념글을 업로드했지만, 이번 알고리즘 스터디에서 코드트리로 개념을 다시 보다 보니 문제풀이 부분이 더 깔끔한 것 같아서 풀이 방식 위주로 다시 정리해 본다. 1. for loop 이용(점화식)초기값 설정해 주고, 그 이후에 대해서는 점화식으로 표현하면 된다.F[1] = 1for i = 2 ... i  2. 재귀함수 이용종료조건으로 초기 조건 넣어주기, 이외에는 점화식 이용function f(n) if n == 1 return 1 else return f(n - 1) * nprint(f(n)) 결국 DP는 점화식 기반의 풀이 방법이라고 할 수 있다. 다만 그것을 for loop / 재귀 중 무엇으로 표현하느냐 차이.  유의사항DP 구현에 있..