코딩테스트 썸네일형 리스트형 2018 카카오 코딩테스트 1차 프렌즈4블록 JS 문제풀이 🔗직접 문제 풀러가기 문제 지워지는 블록은 몇개인가? 2 x 2 형태로 같은 캐릭터가 붙어있으면 사라지면서 점수를 얻는다. 한 블록은 여러개의 2 x 2 에 포함될 수 있다. 블록이 지워진 뒤에는 위에서 아래로 블록들이 쏟아진다. 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C) 문제풀이 function solution(m, n, board) { board = board.map(line => line.split('')); let pang = new Set(); while (true) { for (let i = 0; i + 1 < m; i++) { for (let j = 0; j + 1 < n; j++) { if (!board[i][j]) { conti.. 더보기 2018 카카오 코딩테스트 1차 뉴스 클러스터링 JS 문제풀이 🔗직접 문제 풀러가기 문제 두 문자열을 자카드 유사도를 구하라. J(A,B) = 두 집합의 교집합 크기를 두 집합의 합집합 크기로 나눈 값. 두 집합이 공집합일 경우 나눗셈 정의가 안되므로 J(A,B) = 1 을 따로 정의하라. 입력값 2 < str1, str2 더보기 2018 카카오 코딩테스트 1차 셔틀버스 JS 문제풀이 🔗직접 문제 풀러가기 문제 콘이 셔틀을 타고 사무실로 갈 수 있는 정류장 도착 시각 중 제일 늦은 시각을 구하여라 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다. 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다. 모든 크루는 잠을 자야 하므로 23:59에는 집에 돌아간다. 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 입력값 셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetabl.. 더보기 매트릭스 회전시키기 leetcode 48. Rotate Image 문제풀이 문제: 주어진 행렬을 시계반향으로 90도 회전시켜라. 아이디어 회전된 행렬의 원소들이 원래 어떤 인덱스를 가지고 있었는지 관찰해보면 힌트를 얻을 수 있다. 원본 |00|01|02| |10|11|12| |20|21|22| 회전된 행렬 |20|10|00| |21|11|01| |22|12|02| 첫번째 행의 원소들은 모두 첫번째 열에서 왔다. 열과 행이 바뀌었다. 각 행의 원소들은 [2x, 1x, 0x] 역순으로 정렬되어있다. 알고리즘 원본 |00|01|02| |10|11|12| |20|21|22| 전치 행렬 |00|10|20| |01|11|21| |02|12|22| 그리고나서 각 행이 반전된 행렬 |20|10|00| |21|11|01| |22|12|02.. 더보기 뒤에서 n번째 노드 삭제하기 알고리즘 1. 포인터 hare를 n만큼 먼저 이동시킨다. 2. curr와 hare를 같은 속도로 이동시킨다. 이때 curr는 헤드에서 hare는 n번째 노드에서 출발한다. 3. curr과 hare사이에는 n개의 노드가 있으므로, hare가 뒤에서부터 1번째에 있을 때 curr는 뒤에서부터 n+1번째 노드에 있다. 그러므로 curr.next가 다음다음 노드를 가르키도록 수정하여 n번째 노드를 삭제할 수 있다. 엣지 케이스 n이 연결리스트의 길이와 같을때가 엣지케이스이다. curr의 다음 노드를 삭제하는 것이 아니라, 리스트의 첫번째 노드를 삭제해야해야한다. 길이가 n인 연결리스트의 헤드에서 n번 떨어진 곳은 null이다. 그러므로 hare가 null값인지에 따라 이를 구분할 수 있다. 복잡도 분석 시간복잡.. 더보기 서로 다른 두 연결리스트 교차점찾기 2 leetcode 160. Intersection of Two Linked Lists 문제풀이. 문제: 서로 다른 두 연결리스트가 주어졌을 때, 첫 교차점을 찾아라. 두 연결리스트의 노드 수 차이 1. 두 연결리스트의 길이를 잰다. 2. 길이차이가 있다면 그만큼 둘 중 더 긴 리스트의 포인터를 스킵한다. 3. 길이가 같은 두 연결리스트의 포인터를 같은 속도로 이동시키며 비교했을때, 서로 같은 노드가 첫 교차점이다. Time Complexity: O(A+B) Space Complexity: O(1) 이 방법으로 통과를 했으나 첫 교차점를 지난 후 노드가 서로 다를 경우를 포함하지 못한다. 더보기 서로 다른 두 연결리스트의 교차점 찾기 leetcode 160. Intersection of Two Linked Lists 문제풀이. 문제: 서로 다른 두 연결리스트가 주어졌을 때, 첫 교차점을 찾아라. Hash Set 1. A 리스트를 먼저 순회하며 hash set에 노드들을 저장한다. 2. B 리스트 순회하며 노드들이 이미 hash set에 저장되어있는지 확인한다. 이미 저장되어 있다면 해당 노드를 반환한다. 3. 무사히 B리스트 순회를 마지막 노드까지 마쳤다면, 교차되는 노드가 없다는 뜻이므로 null을 반환한다. Floyd's Tortoise and Hare algorithm 이 문제 또한 토끼와 거북이 알고리즘으로 메모리를 사용을 O(1)으로 줄여줄 수 있다. Time Complexity: O(N) Space Complexity: O.. 더보기 Sieve of Eratosthenes, 에라토스테네스의 체 에라토스테네스의 체Sieve of Eratosthenes는 2부터 n까지의 숫자 중 모든 소수prime number를 찾기 위한 간단한 알고리즘이다.1. 오름차순으로 2 부터 n까지의 모든 숫자를 set={ 2, 3, ..., n} 집합에 갖고있다.2. 아직 처리하지 않은 숫자 중 가장 작은 숫자를 선택한다.3. 해당 숫자의 배수들을 집합에서 모두 지운다. 4. 2로 돌아간다. 끝. 위의 방법으로 모든 합성수들을 집합에서 지울 수 있다. 하지만 2-4번을 N번 반복하는 코드를 작성한다면 O(n**2)시간이 걸릴 것이다. O(n log log n) 시간 걸리는 코드를 작성하기 위해서는 합성수composite number를 제거하는 동작의 중복을 줄이면된다.- 모든 합성수composite number 는 최.. 더보기 이전 1 다음
