'🐺 매일 알고리즘' 카테고리의 글 목록 (3 Page)

본문 바로가기

🐺 매일 알고리즘

2018 카카오 코딩테스트 1차 캐시 JS 문제풀이 🔗직접 문제 풀러가기 입력 캐시크기 n과 도시이름 배열 cities를 입력받는다. 0 더보기

2018 카카오 코딩테스트 1차 비밀지도 JS 문제풀이 🔗직접 문제 풀러가기 문제 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ") 또는벽("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도1과 지도2라고 하자. 지도1 또는 지도2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. 지도 1과 지도 2는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다. 문제풀이 1. 각 배열의 i번째 정수를 이진수로 바꾸었을 떄 01 과 11라면 해독된 숫자는 이진수 11이다. 즉, OR 연산을 활용하면 된다. 2. .. 더보기

매트릭스 회전시키기 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.. 더보기

연결리스트 사이클이 시작되는 노드 찾기 leetcode 142. Linked List Cycle II 문제풀이 문제: 주어진 연결리스트에서 사이클이 없다면 null을, 있다면 사이클이 시작되는 노드를 반환하라. 1. 주어진 노드를 Hash Set에 추가하면 순회한다. 2. 이미 Hash Set에 있는 노드를 만나면 사이클이 시작된 것이므로 해당 노드를 반환한다. 3. 무사히 순회를 끝냈으면 사이클이 없는 것 이므로, null을 반환한다. 141번 사이클 감지하기 문제에서 활용한 투 포인터 테크닉을 활용하여 공간을 O(1)만큼만 사용할 수 있다. leetcode 141. Linked List Cycle 사이클 감지하기 leetcode 141. Linked List Cycle 문제풀이 문제: 주어진 연결리스트에 사이클이 있다면 true를 없다면 .. 더보기

사이클 감지하기 leetcode 141. Linked List Cycle 문제풀이 문제: 주어진 연결리스트에 사이클이 있다면 true를 없다면 false를 반환하라 Hash Set 1. 각 노드를 set에 추가해가며 순회한다. 2. 다음에 순회할 노드가 이미 set에 들어있다면 true를 반환. 3. 순회를 무사히 마쳤다면 사이클이 없는 것이므로 false를 반환. 모든 노드를 set에 저장하려면 O(N)공간이 필요하다. set에 노드를 저장하는 것 대신, 노드의 val값에 이미 방문했음을 표시한다면 메모리를 아낄 수있다. Two Pointer 투 포인터 테크닉을 활용해서도 공간복잡도를 O(1)으로 제한할 수 있다. 투 포인터 테크닉은 한 포인터는 더 빠르게 또 다른 포인터는 더 느리게 움직이도록하는 테크닉을 말한다. .. 더보기

이전 1 2 3 4 5 다음

티스토리툴바