본문 바로가기

알고리즘119

H-Index https://school.programmers.co.kr/learn/courses/30/lessons/42747# 발표논문 n개중, (h이상 인용된 논문이 h이상 + 나머지가 h이하)일때의 h => 즉 "h번 이상 인용된 논문이 h편 이상인 최대 h를 구하라" 가 문제의 요점인데 (아니 뭔 수수께끼나구요...) 설명과 예시 코드가 부족하고 표현이 애매해서 문제를 정확히 이해하지 못 했고 결국 다른 분의 해석을 보고 풀었다 핵심은 h의 최대값은 입력값 citations의 길이고, 인용된 횟수와 조건이 맞는 논문 갯수가 일치하는 최대값 구하기 문제이다 예를들어 citations = [ 9000,7000, 10000, 5000, 6000 ] 일때 1번 이상 인용된 논문 = 5편 >= 1편 이상 2번 이상 인.. 2023. 12. 8.
[프로그래머스 lv2] 숫자 카드 나누기 https://school.programmers.co.kr/learn/courses/30/lessons/135807 우선 두가지 경우가 있다 1. 철수는 모두 나눠지는데 영희는 모두 안 나눠지는 경우 2. 철수는 모두 안 나눠지는데 영희는 모두 나눠지는 경우 처음에는 철수, 영희 각각의 최대공약수를 구하고 그것이 상대방의 수를 모두 나눌 수 있는지를 확인하려고 했다 하지만 만약 상대방의 수가 하나라도 나눠진다면 다음 최대공약수를 찾아야하고 log(min(a, b))또 다시 상대방의 배열을 순회 log(n) 하며 확인해야한다. 하지만 이렇게 한다면 제한사항 케이스일때 시간초과가 날 것이다. 사실 문제가 원하는 조건을 잘 뜯어보면 a의 범위를 확 줄일 수 있다 위의 첫번째 경우에서 "철수배열의 수를 모두 나.. 2023. 12. 8.
줄 서는 방법 https://school.programmers.co.kr/learn/courses/30/lessons/12936 첫번째 풀이 (시간초과) 모든 경우를 구한 뒤 k번째 결과를 리턴했다. // 백트래킹 순열 function solution(n, k) { var answer = []; const arr = Array.from({length: n}, (_, i) => i+1); function bt(acc, remain) { if (!remain.length) { answer.push(acc); return; } for (const r of remain) { bt([...acc, r], remain.filter(e => e !== r)); } } bt([], arr); return answer[k-1]; } .. 2023. 12. 8.
롤케이크 자르기 https://school.programmers.co.kr/learn/courses/30/lessons/132265 풀이 topping 길이 1,000,000 => O( nlogn ) slice의 시간복잡도는 O(n) => 매번 잘라서 형과 동생의 토핑갯수를 구할 수 없다 처음에 형한테 모든 토핑을 준다 그 후 토핑을 순회하며 동생이 하나씩 가져가고 형과 동생의 토핑갯수를 비교한다. function solution(topping) { var answer = 0; const old = {}; // 토핑 종류별 갯수 const young = {}; let oldCount = 0; // 토핑 종류 갯수 let youngCount = 0; topping.forEach(t => { if (!old[t]) { ol.. 2023. 12. 7.
[프로그래머스 LV2] 마법의 엘리베이터 JS https://school.programmers.co.kr/learn/courses/30/lessons/148653 문제요점 절대값이 10^c인 버튼 누르면 현재 층 수 + 버튼 으로 이동 0보다 작으면 움직이지 않음 버튼 한번에 마법돌 1개 0층으로 가는데 필요한 최소버튼 생각 큰 수 => 규칙 => 자릿수마다 문제풀이 맨 밑의 자릿수부터 하나씩 제거해가며 층이 0이 될 때까지 순회하는데 각 자릿수마다 엘리베이터를 올릴지, 내릴지를 판단해야하는데 가능한 케이스는 두가지이다 해당 숫자만큼 버튼을 누르냐 10에서 해당 숫자를 뺀 만큼 누를 것이냐 (단 한 자릿수 위에 올림처리를 해야함) 예를 들어 43의 두가지 케이스는 이렇다 40 + 3 50 - 7 1의 자리부터 확인하면서 5미만이면 내린다 (자릿수 값.. 2023. 12. 7.
비트마스킹 비트마스킹은 컴퓨터 과학에서 비트 연산자를 사용하여 특정 위치의 비트를 설정하거나 조작하는 기술이다 데이터를 압축하는데에 유용하며 효율적으로 데이터를 다룰 수 있다. 비트마스크의 주요 연산 비트 설정 OR(|) 연산자를 사용하여 특정 위치의 비트를 1로 설정한다. let num = 5; // 5의 이진 표현은 '101' let mask = 1 2023. 12. 6.

티스토리툴바