[알고리즘] 2차원 배열 90도 회전하기
코딩 테스트 구현 문제에서는 2차원 배열을 90도, 180도, 270도 회전해야 하는 경우가 종종 등장한다. 이번 포스팅에서는 2차원 배열을 시계 방향으로 90도 회전하는 공식 과 구현 방법을 정리한다. 2차원 배열 90도 회전 N × N 크기의 2차원 배열이 있다고 가정하자. 1 2 3 4 5 6 7 8 9 이를 시계...
코딩 테스트 구현 문제에서는 2차원 배열을 90도, 180도, 270도 회전해야 하는 경우가 종종 등장한다. 이번 포스팅에서는 2차원 배열을 시계 방향으로 90도 회전하는 공식 과 구현 방법을 정리한다. 2차원 배열 90도 회전 N × N 크기의 2차원 배열이 있다고 가정하자. 1 2 3 4 5 6 7 8 9 이를 시계...
컴퓨터의 성능을 결정하는 요소를 떠올리면 보통 CPU의 클럭 속도나 코어 수를 생각한다. 하지만 실제로는 CPU가 아무리 빨라도 필요한 데이터를 제때 가져오지 못하면 성능은 크게 떨어진다. CPU는 매우 빠르게 연산할 수 있지만, 필요한 데이터를 메인 메모리(DRAM)에서 가져오는 속도는 상대적으로 느리다. 이러한 속도 차이를 완화하기 위해 등장한 것이 바로 캐시(Cache) 이다. 이번...
이분 탐색(Binary Search)은 탐색 공간을 절반씩 줄여가며 원하는 값을 찾는 알고리즘이다. 정렬된 배열에서 값을 찾는 알고리즘 이라고 알고 있지만, 실제로 코딩 테스트에서 더 중요한 형태는 매개변수 탐색(Parametric Search)이다. 즉, 단순 배열 탐색이 아닌, 결정 문제(Decision Problem) 를 반복적으로 풀어가며 최적해를 찾아야 하는 경우가 많다. 이분 탐색(Binary Search) 정렬된 배열에서 특정...
C++ STL의 unordered_map은 Key-Value 형태의 데이터를 해시 기반으로 저장하는 연관 컨테이너 이다. 이전 포스팅에서 살펴본 map과 기능적으로는 유사하지만, 정렬을 하지 않고 속도에 집중한 컨테이너 라는 점이 가장 큰 차이이다. std::unordered_map은 내부적으로 해시 테이블 을 사용한다. 특징 Key 중복 X 정렬 X 삽입/삭제/탐색: O(1) 최악의 경우: O(n) (해시 충돌이 심한 경우)...
C++ STL의 map은 Key-Value(키-값) 쌍을 저장하는 연관 컨테이너(associative container)이다. map을 제대로 이해하려면, 그 기반이 되는 pair부터 짚고 넘어가는 것이 좋다. pair std::pair는 서로 다른 두 개의 값을 하나의 객체로 묶어주는 구조체이다. STL에서 아주 자주 사용되며, map의 내부 요소 타입도 pair이다. pair의 선언과 사용 #include <iostream> #include <utility> using namespace std;...