본문 바로가기

전체 글178

[프로그래머스 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.
substr와 substring의 차이 substr와 substring은 둘다 문자열에서 부분 문자열을 추출하는 메서드이다 하지만 알고리즘 문제를 풀면서 substring의 시간, 공간 효율성이 더 좋아서 이 둘의 차이점을 파헤쳐보았다. substr(시작 인덱스, 길이) 시작인덱스부터 길이만큼의 문자열을 반환한다. 길이가 양수이면 시작인덱스부터 해당 길이만큼의 문자열을 반환하고 (좌 -> 우) 길이가 음수이면 역으로 문자열 끝에서부터 길이만큼의 문자열을 반환한다 (좌 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.
캐시 메모리 속도가 빠른 장치와 느린 장치의 속도차이(병목현상)를 해결하는 메모리이다. CPU가 빠른 속도로 데이터를 주고 받을 수 있도록 캐시메모리는 CPU와 인접하게 위치한다. 참조지역성의 원리에 따라 주기억장치나 보조기억장치에서 자주 사용하는 해당 데이터 뿐만 아니라 옆 주소의 데이터를 미리 가져와 임시보관한다. 속도를 향상시키지만, 용량이 적고 비싸다. 참조 지역성의 원리 자주 사용되는 데이터에 대한 판단 기준이다. 시간 지역성 for나 while 같은 반복문에 사용하는 조건 변수처럼 한번 참조된 데이터는 잠시후 또 참조될 가능성이 높음 공간 지역성 A[0], A[1]과 같은 연속 접근 시, 참조된 데이터 근처에 있는 데이터가 잠시후 또 사용될 가능성이 높음 CPU안의 캐시메모리 CPU에는 캐시 메모리가 2~.. 2023. 12. 7.

티스토리툴바