Algorithm

개요프로그래머스의 카카오 기출문제인 압축 문제를 자바스크립트로 풀어본다.문제다음 과정을 거치는 LZW 압축 알고리즘을 구현한다.길이가 1인 모든 단어(A-Z)를 포함하도록 사전을 초기화한다.사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.입력에서 처리되지 않은 다음 글자(c)가 남아있다면, w+c에 해당하는 단어를 사전에 등록한다.단계 2로 돌아간다.이 압축 알고리즘은 영문 대문자만 처리한다.따라서 처음에는 사전이 다음과 같이 정의되어 있다.만약 입력으로 KAKAO가 들어온다면 LZW 압축 단계는 다음과 같다.현재 사전에는 K는 들어있으나 KA는 들어있지 않다. 따라서 K에 해당하는 색인 번호 11을 출력하고, 27번에 KA를..

프로그래머스의 k진수에서 소수 개수 구하기 문제를 자바스크립트로 푼다.문제 설명양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.0P0처럼 소수 양쪽에 0이 있는 경우P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우P처럼 소수 양쪽에 아무것도 없는 경우단, P는 각 자릿수에 0을 포함하지 않는 소수입니다.예를 들어, 101은 P가 될 수 없습니다.예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (2..

[프로그래머스] 2018 KAKAO 뉴스 클러스터링 문제 자바스크립트 풀이2018 KAKAO 1차 뉴스 클러스터링 문제를 자바스크립트로 풀어본다.문제 설명여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 문제점을 개선하는 업무를 맡게 되었다. 개발의 방향을 잡기 위해 튜브는 우선 최근 화제가 되고 있는 "카카오 신입 개발자 공채" 관련 기사를 검색해 보았다. 카카오 첫 공채..'블라인드' 방식 채용 카카오, 합병 후 첫 공채.. 블라인드 전형으로 개발자 채용 카카오, 블라인드 전형으로 신입 개발자 공채 카카오 공채, 신입 개발자..

[프로그래머스] 2018 KAKAO 캐시 문제 자바스크립트 풀이개요프로그래머스의 KAKAO 기출문제인 캐시 문제를 자바스크립트로 풀어본다. 문제 설명지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다. 이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다. 어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이..

프로그래머스 Level3 - 단어 변환 python 풀이개요이 글은 프로그래머스 Level 3의 단어 변환 문제를 파이썬으로 풀이하는 과정을 담고 있다. 문제 이해한 번에 한 개의 알파벳만 바꿀 수 있음words 에 있는 단어로만 변환할 수 있음가장 짧은 변환 횟수를 return 해야 함 ⇒ BFS 혹은 DFS 문제면서 distance 구하는 문제임을 알 수 있는 구절각 단어는 알파벳 소문자로만 이루어져 있다. ⇒ 대소문자 구분 필요 없음변환할 수 없는 경우에는 0을 return함문제 풀이우선 한 개의 알파벳만 달라야 하므로 diff(a,b) 라는 함수를 따로 짰다.def diff(a, b): diff = 0 for i in range(len(a)): if a[i] != b[i]:..

백준 1260번 DFS와 BFS 파이썬 풀이 DFS와 BFS의 차이점을 먼저 알아보자. 위의 예제를 그림으로 나타내면 다음과 같다. DFS는 끝까지 간다. 보통 재귀를 사용한다. 1에서 시작한다. 1은 2, 3, 4와 연결되어있다. 가장 가까운 친구한테 일단 간다. 제일 먼저 2를 마주친다. 2랑 연결돼있는 애 살펴본다. 1이랑 4가 연결돼있는데, 1은 이미 지나왔네?? 4로 간다. 이제 4랑 연결돼있는 애 살펴본다. 1, 2, 3 연결돼있는데 1, 2는 이미 지나왔네? 3으로 간다. 이제 3이랑 연결돼있는 애 살펴본다. 1, 2, 4 연결돼있는데 다 이미 지나온 애들이다. 더 살펴볼 게 없으니까 돌아간다. 4로 돌아왔다. 4랑 연결돼있는 애들도 이미 다 지나왔다. 더 살펴볼 게 없으니까 돌아간다. 2로..

📌 발전기 | 난이도 : ⭐️⭐️⭐️ 발전기 - 구름LEVEL 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 상하좌우로 인접한 집에서 전력을 공급받으면 되는 것이므로, 서로 인접한 집들끼리는 한 뭉텅이로 본다. 실패 코드 (테스트케이스 오답 : 4, 10, 11, 12, 13, 14, 16, 17, 19, 22 - Runtime Error) def dfs(y, x): if x = n or y = n: return if house[y][x] != 1: return # 상하좌우 dy = [-1, 1, 0, 0] dx = [0, 0, -1, 1] # 중복탐색 방지 house[y][x] = 0 for k in ..

📌 통증(2) | 난이도 : ⭐️⭐️⭐️ 통증 (2) - 구름LEVEL 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io DP로 풀면 되는 문제다. DP의 핵심은 이전에 구한 값을 재사용 해서 연산 횟수를 줄여 효율을 올리는 것 이다. 이 문제에서 DP는 통증 수치를 0으로 만들기 위해 필요한 아이템의 최소 개수다. 예를 들어 첫 번째 테스트케이스에서 a = 2, b = 7, n=11을 푸는 방법은 다음과 같다. DP[1]과 a, b를 이용해 DP[2]를 만들고, DP[2]와 a, b를 이용해 DP[3]을 만든다. 이렇게 직전의 것을 사용하므로 DP[ 현재 - a ], DP[ 현재 - b ]를 비교해봐야 한다는 것이다. 실패 코드 n = in..