투투

https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 접근 먼저 각각의 banned_id가 될 수 있는 아이디를 찾는다. 이후 불량 사용자가 될 수 있는 조합을 찾는다. 구현 - names 배열에 해당 banned_id가 될 수 있는 아이디를 담는다. - banned_id를 순차적으로 탐색하여 아이디를 찾는데 길이가 같을 때에 아이디를 비교한다. - 별표(*)가 있을 때는 아무 문자나 올 수 있기 때문에 conti..

https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 접근 힙을 이용하여 주어진 명령어대로 최댓값을 삭제하거나 최솟값을 삭제한다. 구현 - 빈 배열인 numbers를 선언한다. - 주어진 operations를 탐색하여 명령어와 숫자를 분리하고 - 명령이 I일 때는 heappush로 숫자를 numbers에 대입한다. 이를 통해 numbers는 오름차순으로 정렬될 것이다. - 명령어가 D이고 numbers가 비어있지 않을 때는 - 숫자가 1일 때 리스트 메서드인 pop으로 최댓값을 삭제하고 -1일 때는 heappop로 최솟값을 삭제한다. - 연산을 모두 완료했을 때 numbers가 비어있다면 [..

https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 접근 총 4방향으로 회전하기 때문에 각 방향에 대해 회전해야 하는 범위를 정하여 새로운 2차원 배열에 저장한다. 이후에 새로운 2차원 배열의 좌표에 아무 숫자도 들어있지 않았다면 기존의 숫자를 대입한다. 구현 - 아래는 좌표를 입력받아 테두리를 회전시키는 함수이다. - 각각의 4방향으로 나누고 범위를 지정하여 새로운 2차원 배열인 new_boa..

https://programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 접근 기본적으로 투 포인터 알고리즘을 적용하였다. left와 right가 처음에 0번째 인덱스를 가리킨다. 이제 right를 증가시키면서 해당되는 보석을 table에 추가한다. 만약 table의 길이가 보석의 종류와 같을 때는 최소 길이를 찾는다. 구현 - 먼저 set을 통해 보석 종류의 개수를 구한다. - left와 right가 0번째 인덱스를 가리키면서 탐색을 시작한다. - right가 증가하면서 table..

문제 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. 100,000이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다. 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자. 입력 첫째 줄에 N과 K를 입력하고 둘 째줄에는 N개의 숫자를 입력한다. N은 1이상 200,000이하, K는 1이상 100이하이다. 출력 조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다. 접근 투 포인터 알고리즘을 공부하기 위해 이 문제를 풀게되었다. 먼저 left와 right가 첫 번째 원소를 가리킨다. ..

Array와 Linked List가 무엇인지 안다면 그 차이는 쉽게 알 수 있을 것이다. Array 배열은 특정 크기만큼 연속된 메모리 공간에 데이터를 저장하는 자료구조이다. 만약 int형 데이터 3개를 저장할 수 있는 배열을 생각해보자. 그렇다면 아래의 그림처럼 연속된 공간에 메모리를 확보하여 데이터를 이곳에 저장할 수 있게 된다. 위의 그림에서 볼 수 있듯이 연속된 공간에 데이터들이 나열되어 있기 때문에 처음 주소만 알면 다른 위치도 쉽게 알 수 있을 것이다. 따라서 배열은 랜덤으로 접근하는 것이 가능하다. 그렇다면 어떻게 랜덤으로 접근하는 것이 가능할까? C언어로 예를 들어보면 배열을 선언했을 때 배열의 주소는 배열에 저장되어 있는 첫 번째 원소의 주소와 같다. 이때 4번째 데이터를 조회한다고 하면..

https://programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 접근 최대로 건널 수 있는 사람부터 한 명까지 탐색을 한다. 그리고 건널 수 있는 사람의 명수를 stones에 있는 각각의 숫자와 빼준다. 이때 0이하인 숫자가 K개 이하라면 해당 숫자가 최대로 건널 수 있는 사람의 명 수가 된다. 하지만 stones에 있는 원소는 최대 200,000,000의 수를 갖기 때문에 효율성 테스트에서 통과하지 못할 것이다. 따라서 선형적으로 탐색하는 것이 아니라 이진탐색을 활용한다. 이진 탐색으로 건널 수 있는 사람의 명수를 찾는다. 구현 - le..

Javascript의 Array 관련 메서드인 forEach와 map은 ES5부터 나왔다. 두 개의 메서드가 모두 배열 내의 원소를 탐색하는 것이기 때문에 프로젝트에스 forEach와 map을 자주 사용하였다. 하지만 언제 forEach를 사용하는 것이 좋고, 언제 map을 사용하는 것이 좋은지 구분지을 필요가 있었다. 따라서 forEach와 map의 차이점을 파악하고 각각의 메서드를 언제 사용하는 것이 좋은지 알아보려고 한다. 먼저 forEach와 map이 어떻게 동작하는지 알아보자. forEach forEach는 콜백 함수를 인자로 전달받아 배열 내의 각 원소에 대해 콜백 함수를 실행하도록 한다. 다음 코드에서 1부터 5까지의 숫자를 갖는 numbers라는 배열을 선언하였다. 이를 forEach를 통..

오늘은 Hash Table라는 자료구조에서 충돌이 발생하는 이유와 충돌이 발생하지 않도록 하기 위해서는 어떻게 해야 하는지 알아본다. 먼저 Hash Table은 저장되는 데이터가 (key, value)처럼 하나의 쌍을 이루는 자료구조를 말한다. 이때 key가 존재하지 않는 value는 저장할 수 없으며 key가 중복되어서는 안 된다. 해쉬 함수 학생들의 정보를 Hash Table에 저장하려고 한다. 이때 학생들의 학번을 key로 하는데, 학번이 2020103과 같은 형태로 되어있어서 배열의 크기를 이에 맞춰서 선언해야하며 배열을 생성하더라도 쓰지 않는 공간이 많기 때문에 효율적이지 못하다. 따라서 학번을 해쉬 함수로 전달하여 반환된 값을 key로 설정하려고 한다. 해쉬 함수는 다음과 같다. 학번을 입력하..

https://programmers.co.kr/learn/courses/30/lessons/12979 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 접근 기지국의 영향을 받지 않는 곳의 크기를 구하고 이를 기지국이 영향을 주는 범위만큼 나눈다. 이제 몫을 올림하여 최종해에 더한다. 기지국의 영향을 받지않는 곳을 봤을 때 (2 * w + 1)로 나누면 필요한 기지국의 개수를 알 수 있다고 판단하였다. 구현 - 먼저 기지국의 범위를 (left, right)의 형태로 ranges에 추가한다. ..