본문 바로가기
728x90
반응형

Algorithms160

[프로그래머스] level 4 가사 검색(자바스크립트) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻 문제 정답 코드 답안 1(Map 활용) 답안 2 문제 풀이 트라이(trie) 자료 구조를 활용하여 풀 수 있는 문제이다. 트라이는 '문자열을 찾거나 일치 여부를 판별하는 데' 유용한 자료 구조이다. 트라이는 중첩된 객체 구조로 되어 있다. 트라이의 삽입 메서드를 실행하면 문자열을 순회하며 탐색하는 문자가 root에 존재하지 않을 시 해당 문자를 key로 갖는 객체를 생성한다. 이러한 객체가 줄줄이 달려 트리를 형성하는 것이다. 'kang'과 'kim'이라는 문자열을 입력했을 시 아래와 같은 트라이 자료.. 2023. 1. 30.
[Baekjoon] 2110 공유기 설치(자바스크립트/NodeJs) 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 👨‍💻 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가.. 2023. 1. 30.
[이코테] 이진 탐색_고정점 찾기(자바스크립트) 이번 글은 '이것이 취업을 위한 코딩테스트다' 내의 문제를 풀고 정답 코드를 정리한 것입니다. 이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고 이것이 취업을 위한 코딩 테스트다 with 파이썬 | IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인! 취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 product.kyobobook.co.kr 👨‍💻 문제 정답 코드 문제 풀이 문제에서 요구하는 시간 복잡도는 O(logN)이므로 선형 탐색으로는 풀 수 없다. 이미 정렬된 배열이 주어지므로 이진 탐색을 통해 해결할 수 있다. 찾고자 하는 값과 중간점(mid)이 동일하다 가정하고 탐색을 수행한다. 탐색을 수행하다 중간점에 있는 값(arr[mid])보다 .. 2023. 1. 29.
[이코테] 이진 탐색_정렬된 배열에서 특정 수의 개수 구하기(자바스크립트) 이번 글은 '이것이 취업을 위한 코딩테스트다' 내의 문제를 풀고 정답 코드를 정리한 것입니다. 이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고 이것이 취업을 위한 코딩 테스트다 with 파이썬 | IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인! 취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 product.kyobobook.co.kr 👨‍💻 문제 정답 코드 문제 풀이 문제에서 요구하는 시간 복잡도는 O(logN)이므로 선형 탐색으로 문제를 해결할 수 없다. 따라서 이진 탐색을 통해 문제를 풀어야 한다. 배열은 정렬된 채로 주어지기 때문에 수열 내에 x가 존재한다면 연속해서 나열되어 있음을 예상할 수 있다. 따라서 x가 처음 등장하는 인덱스.. 2023. 1. 29.
[이코테] 이진 탐색_떡볶이 떡 만들기(자바스크립트) 이번 글은 '이것이 취업을 위한 코딩테스트다' 내의 문제를 풀고 정답 코드를 정리한 것입니다. 이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고 이것이 취업을 위한 코딩 테스트다 with 파이썬 | IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인! 취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 product.kyobobook.co.kr 👨‍💻 문제 정답 코드 문제 풀이 이진 탐색으로 풀 수 있는 문제다. 먼저 시작점(start)과 끝점(end)을 설정한다. 그런 다음 시작점이 끝점보다 커질 때까지 반복문을 돌면서 중간값(mid)을 도출하고, 주어진 떡의 길이를 탐색하며 중간값보다 큰 값이라면 해당 값에서 중간값을 뺀 값을 총합에 누적한다. .. 2023. 1. 28.
[이코테] 이진 탐색_부품 찾기(자바스크립트) 이번 글은 '이것이 취업을 위한 코딩테스트다' 내의 문제를 풀고 정답 코드를 정리한 것입니다. 이것이 취업을 위한 코딩 테스트다 with 파이썬 | 나동빈 - 교보문고 이것이 취업을 위한 코딩 테스트다 with 파이썬 | IT 취준생이라면 누구나 입사하고 싶은 카카오ㆍ삼성전자ㆍ네이버ㆍ라인! 취업의 성공 열쇠는 알고리즘 인터뷰에 있다!IT 취준생이라면 누구나 product.kyobobook.co.kr 👨‍💻 문제 정답 코드 답안 1(이진 탐색) 답안 2(계수 정렬) 답안 3(includes 메서드) 정답 풀이 다양한 방법으로 풀 수 있는 문제이다. 풀이 방법이 어찌됐든 손님이 요구하는 부품이 가게의 부품에 포함되어 있다면 yes, 아니라면 no를 출력하면 된다. 이진 탐색으로 풀려면 배열을 정렬해야 한다는.. 2023. 1. 28.
[프로그래머스] level 1 실패율(자바스크립트) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👨‍💻 문제 정답 코드 문제 풀이 문제를 풀 때 필요한 값은 분모가 될 '도전자 수', 분자가 될 '아직 클리어 못 한 사람 수', 마지막으로 둘을 나눈 '실패율'이다. 도전자 수는 처음에는 stages의 길이를 대입해뒀다가 for 반복문을 돌면서 매 작업마다 아직 클리어 못 한 사람 수를 누적해서 뺀다. N이 5이고, stages가 [2, 1, 2, 6, 2, 4, 3, 3]이라면 아직 클리어 못 한 사람 수는 다음과 같을 것이다. [1, 2, 2, 2, 3, 3, 4, 6] 총 스테이지 1 ~ 5 1 스테.. 2023. 1. 27.
[Baekjoon] 18310 안테나(자바스크립트/NodeJs) 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 👨‍💻 문제 일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다. 집들의 위치 값이 주어질 때, 안테나를 설치할 위치를 선택하는 프로그램을 작성하시오. 예를 들어 N=4이고, 각 위치가 1, 5, 7, 9일 때를.. 2023. 1. 26.
[Baekjoon] 10825 국영수(자바스크립트/NodeJs) 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 👨‍💻 문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.) 입력 첫째 줄에 도.. 2023. 1. 26.
728x90
반응형