Algorithm(22)
-
[프로그래머스] 소수 찾기
소수는 1과 자기자신 외의 약수를 갖지 않는 수이다. 소수를 판별하기 위해 2부터 자기자신-1 까지 나누어지는지 확인해야 한다. 아래 두가지 방법을 통해 효율성을 높일 수 있다! 1. 약수는 짝을 가진다는 특징을 활용 10 = (1, 10), (2, 5), (5, 2), (10,1) 16 = (1,16), (2, 8), (4, 4), (8, 2), (16, 1) 이 짝은 자신의 양의 제곱근을 기준으로 지어진다. (10 -> 3.162.. 16 -> 4 ) 따라서, 2부터 자신의 양의 제곱근 까지 나누어지는지 확인하면 된다! 2. 모든 짝수는 소수가 아니다라는 특징을 활용 모든 짝수는 2로 나누어지기 때문이다. 따라서, 짝수의 소수 여부를 확인하지 않아도 되고(소수가 아니기 때문) 나머지 값들을 2의 배수..
2023.03.16 -
[프로그래머스] 뉴스 클러스터링
자카드 유사도는 원소의 중복을 허용하는 다중집합에 대해서 확장한 문제이다. 1. 대소문자를 구분하지 않으므로 대문자로 통일(toUpperCase()) 2. str1, str2의 부분 집합 구함: 부분 집합에 문자 이외의 값이 없을 경우만 추가 3. str1, str2의 모든 부분 집합을 중복없이 구함 4. 모든 부분 집합이 str1, str2에서 몇 번 나오는지 구함 5. 모든 부분 집합의 교집합, 합집합 수를 구함 5-1. 교집합의 개수: str1, str2의 등장 최소값 5-2. 합집합의 개수: str1, str2의 등장 최대값 6. (교집합/합집합) * 65536 , 소수점 버리고 return 자세히 주석 달아두었으니 확인 !! function solution(str1, str2) { // 대소문자..
2023.03.15 -
[프로그래머스] 캐시
프로그래머스의 캐시 문제 풀면서 캐시에 대한 개념이 부족하여 문제자체를 이해하는데 시간이 걸렸다. 문제를 풀기 위해 필요한 기본 개념을 정리해 보았다. 캐시 히트(Cache Hit)란? : 참조하려는 메모리가 캐시에 존재하고 있을 때 (실행시간 1) 캐시 미스(Cache Miss)란? : 참조하려는 메모리가 캐시에 존재하지 않을 때 (실행시간 5) 캐시 크기(Cache Size)란? : 데이터를 저장하는 메모리 공간 LRU(Least Recently Used)란? : 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식 새로운 데이터가 들어온 경우 캐시에 넣어준다. 캐시가 가득차있다면, 가장 오래된 데이터를 제거하고 넣어준다. 존재하는 데이터가 들어온 경우 해당 데이터를 꺼낸 뒤 가장 최근 데이터 위치로 ..
2023.03.13 -
[프로그래머스] 타겟 넘버
주어진 리스트 값을 하나씩 접근하며 -, +부호를 달아주는 문제이다. DFS/BFS를 활용한 문제라고 한다. 이 문제를 풀면서 DFS/BFS와 완전탐색의 차이가 무엇인지 궁금해졌다. * 완전탐색을 베이스로 한 그래프 탐색 기법이다..! [1,1,1] 리스트와 [+, -]를 사용해 숫자 1을 만들 수 있는 경우의 수를 구하려면, 모든 방법을 확인해보아야 한다. 1. list의 idx 0의 값에 - 또는 + 부호를 할당하고, 합계를 나타내는 sum에 저장한다. 2. -1 / +1 을 각각 저장한 sum이 2개가 된다. * 이게 cache에 저장한다고 하는건가? 3. 두 sum에 각각 idx 1의 값에 -또는 + 부호를 할당 한 값을 저장한다. 따라서 sum이 4개가 된다. 4. 이를 idx가 끝에 도달할 때..
2023.03.10 -
동적 계획법(Dynamic Programming)
동적 계획법: 하나의 문제를 여러 작은 문제로 나누고, 작은 문제의 결과를 저장하여 큰 문제를 해결한다. 하나의 문제를 여러 개의 하위 문제로 나눈 다음, 결합하여 답을 도출한다. 하위 문제들의 결과를 저장한다.(Memoization, 메모이제이션) -> 동일한 문제가 나왔을 때 저장해둔 결과를 가져다 쓰며, 실행속도 빠르게 한다. 겹치는 부분 존재 DP는 작은 문제의 결과를 저장하고 재사용하여 문제를 푼다. 따라서, 동일한 작은 문제가 있을 때 사용한다. 최적 부분 구조 작은 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 의미한다. 작은 문제에서 구한 최적의 결과가 큰 문제에서도 동일하게 최적으로 적용되는 경우이다. 동적계획법의 가장 대표적인 피보나치 수를 구현해보자! 피보..
2023.03.10 -
[프로그래머스] N으로 표현
동적계획법(Dynamic Programming)을 사용한 문제이다. 모든 값을 연산해봐야 한다는 것은 이해를 했다. 근데, 도대체 어떻게 구현해야 하는지 완전탐색과 다른것은 무엇인지... * 동적계획법을 공부하면서 완전탐색과는 완전히 다르다는 것을 알았다. 헷갈린다면, https://chyunlog.tistory.com/34 참고! 따라서 다른 분의 풀이를 해석해보기로 했다. 완전탐색처럼 도대체 컴퓨터 안에서 어떻게 돌아가는지 헷갈리지만... 주석을 꼼꼼히 달아놨으니 이해하는데 도움이 되길! function solution(N, number) { // 최솟값이 8보다 크면 -1을 return 합니다.라는 제한사항이 있기에 // 1~8까지의 경우의 수를 저장할 길이 8인 배열을 만든다. // 배열의 각 값..
2023.03.09 -
JavaScript 템플릿 리터럴(백틱``, 달러${})
템플릿 리터럴은 자바스크립트에서 문자열을 입력하는 방식이다. 아래와 같이 ""따옴를 사용하여 문자열을 표기했다면 const str = "따옴표로 정의한 문자열"; 템플릿 리터럴은 ``백틱(backtick)을 사용한다. const strBack = `백틱으로 정의한 문자열`; 백틱은 아래와 같은 특징이 있다. 1. 이스케이프 시퀀스(\n, \t 등) 없이 공백을 작성할 수 있다. // 따옴표ver console.log("오늘은 3월 9일\n최고기온은 22도이다."); // 오늘은 3월 9일 // 최고기온은 22도이다. // 백틱ver console.log(`오늘은 3월 9일 최고기온은 22도이다.`); // 오늘은 3월 9일 // 최고기온은 22도이다. 2. + 또는 , 연산자를 사용하지 않아도 문자열을 ..
2023.03.09 -
[프로그래머스] 피로도
완전탐색문제에 도전했다! 1.현재 피로도 2.탐험전: 각 던전의 최소 필요 피로도 3.탐험후: 각 던전의 소모 피로도 위 세 값이 주어지고, 이 때 유저가 탐험할 수 있는 최대 던전 수를 return 던전을 1->2->3 , 2->1->3 처럼 순서없이 돌 수 있다. 모든 던전탐방 경우의 수를 해보고, 가장 많은 던전을 돌 수 있는 경우의 수를 뽑으면 됨 ! function solution(k, dungeons) { let tired =[] // 방문한 던전 수 const n = dungeons.length // 던전의 총 개수 //각 던전 방문여부(방문: 1, 아직: 0) let ch = Array.from({ length: n }, () => 0); function dfs(now, game){ for..
2023.03.03 -
스택과 큐
자료구조 중 스택과 큐는 많이 들어보았지만, 항상 뭐가 뭔지 헷갈렸다. 이번 기회에 제대로 확실히 정리해보고자 한다! 일단 자료구조란 배열처럼 데이터를 저장하고 관리할 수 있는 것이다. 스택과 큐는 데이터를 어떻게 저장하고 관리하는지 알아보자 ! 스택은 후입선출 js에서 push()는 삽입, pop()은 삭제 함수이다. ex) 인터넷의 뒤로가기(그동안 쌓였던 것들의 뒷부분 부터 차례로 뒤로가기 됨) 큐는 선입선출 queue에 삽입하는 것은 enqueue라 하고, 삭제하는 것은 dequeue라고 한다. 마찬가지로 push()는 삽입, shift()는 가장 앞의 것 삭제 함수이다. ex) 은행창구 번호표(들어온 순서대로 나감) 시간복잡도에 대해 이야기 하자면 push()와 pop()은 O(1)의 시간복잡도를..
2023.03.02 -
[프로그래머스] 프린터
ㅊ맨 앞에 있는 파일이 가장 높은 중요도여야 출력할 수 있음 가장 높지 않다면, 맨 뒤로 이동 => 프린터 순서를 하나의 통로로 생각하면 편하다. 한 칸씩 앞으로 이동하고, 더 이상 이동할 곳이 없다면 가장 뒤로 이동! 배열 형태로 저장된 파일들을 앞에서 빼고, 뒤에 이어 붙이는 것은 이 두 함수를 사용하면 된다 앞에서 빼기: shift() 뒤에 이어붙이기: push(붙일 파일) 1. 원하는 값이 인쇄될 때까지 반복 2. 현재 가장 큰 중요도 max값 찾기 3. 가장 앞의 값 빼기 4. max와 가장 앞의 값이 같으면 4-1. 인쇄횟수 num +=1 4-2. 방금 인쇄된 것이 원했던 인쇄물이면 끝 5. max와 가장 앞의 값이 다르면 5-1. 맨 뒤에 다시 붙임 5-2. 맨 뒤로 이동한 것이 원했던 인쇄..
2023.03.02