J.Althea

vector<bool>를 foreach에서 사용하려다가 컴파일 오류가 발생했다. 다른 primitive type, object type 에서는 발생하지 않아서 신기함을 느끼고 찾아보게 되었다. bool은 바이트 단위로 표현하면 1byte라고 볼 수 있지만, 내부적으로는 1bit만 사용하게 되므로 나머지 공간을 사용하지 않아서 메모리 관점에서 비효율이 발생한다. (char는 1byte를 제대로 사용하는 것과 비교된다.) 'vector<bool>는 내부적으로 1byte에 여러 개의 bool 값을 저장한다. (dynamic bitset)' 라 는 답변이 가장 와닿았고, 이를 바탕으로 더 찾아보게 되었다. 메모리 공간 최적화로 인해서, 표준 컨테이너의 기능과 인터페이스를 다소 잃게 된다. vector<bool>에서 operator[]는 bit를 조작할 수 있는 프록시 객체를 반환하게 되는데, 프록시 객체는 bool &이 아니기 때문에, bool *에 주소를 할당할 수 없다는 것이다. 예) bool * b = & v[0];    //Compile Error  이와 대조적으로, deque는 이러한 특수화가 이루어지지 않으므로 bool은 1byte를 취하고, operator[]에서 반환된 값의 주소를 가져올 수 있다. (의도한 방향) Proxy Class는 다른 클래스에 원하는 인터페이스 사용 을 위해서 사용하는 대리자 역할을 한다. 위에 operator[]처럼 1bit(0과 1)만 사용하기를 원하는 경우, 이를 표현하게 해준다. https://stackoverflow.com/questions/994488/what-is-proxy-class-in-c (1) vector<bool>의 내부적 구현 => Proxy Object로 반환(rvalue) => 반복자(iterator)는 lvalue만 참조가능 => Compile Error! (2) vector<char>의 내부...

동적 프로그래밍을 설계하는 데 있어서, 가장 먼저 고려해야 할 것은 변수 간의 규칙성 이다. 규칙을 찾아 점화식 을 작성할 수 있게 되면, 가장 간단한 코드 작성으로도 답은 구할 수 있는 상황이 된다. 여기에서 추가적인 최적화 (불필요한 연산 제거)를 통해서 시간을 단축할 수 있다. 즉, 메모이제이션(Memoization) 을 통해서 연산이 중복되는 것을 방지해야 한다. 1. 점화식 2. 메모이제이션 3. 더 최적화할 방법 찾기 1번을 만족시키게 되면, 완전 탐색(Brute-force) 으로 볼 수 있고, 1번과 2번을 모두 만족시켜야 동적 프로그래밍(Dynamic Programming) 이라고 볼 수 있다. 추가로 어려운 문제의 경우, 3번까지 활용해야 제한 시간 내에 해결할 수 있다. https://www.acmicpc.net/problem/14501 DP(Dynamic Programming) 를 연습할 수 있는 문제이다. 위의 문제를 풀다가, 재귀 로 푸는 방법은 쉽게 떠올랐으나 반복 문으로 푸는 방법이 바로 떠오르지 않아서 여러 코드를 분석해보았다. 여러 가지 방법이 있겠지만, 시간복잡도와 이해하기 쉬운 코드를 기준으로 선별하였다. 풀이 방법에 따라 어떤 변수를 고려하고, 어떻게 접근해야 하는지 생각해볼 수 있겠다. 0. 점화식 i번을 선택하지 않을 경우 : f(i + 1) i번을 선택하는 경우 : f(i + t(i)) + p(i) f(i) = max(f(i + 1), f(i + t(i)) + p(i))    (i <= n) f(i) = 0    (i > n)  1. 재귀적인 방법 int n, d[ 16 ], t[ 16 ], p[ 16 ]; int f( int index) { if (index == n) return 0 ; if (index > n) return INT_MIN; if (d[index] != - 1 ) return d[...

우리가 코딩하면서, 가장 많이 사용하는 자료구조 개념은 무엇일까 생각해보았다. 또, 그 중 중요하면서 유용한 것이 무엇일까 생각해보았다. 배열(array) , 해시 개념을 사용한 맵(map) , 집합(set) 같은 자료구조가 아닐까 생각이 들었고, (트리를 이용한 map, set도 있기 때문에 '해시 개념을 사용한'이라고 하였다) 검색과 생각 끝에 공통적인 개념이 사용됨을 알았다. 해시 테이블의 개념을 살펴보면, key - value 를 이용하여 원하는 자료구조를 순차 탐색할 필요 없이 바로 찾아가는 것에 있다. 그리고 이를 흔히 말하는 상수 시간 O(1) 로 볼 수 있다. 먼저, 배열을 살펴보자. 배열은 정수(0, 1, 2, ... )를 이용해서 해당 위치에 있는 자료를 바로 불러올 수 있다. 이것은 key - value로 나타내면, int형을 갖는 key와 각기 다른 타입을 갖는 value로 볼 수 있다. 즉, 배열은 key가 정수인 해시 테이블 이라고 볼 수 있다. 그러면 배열을 선언하면, 내부적으로는 어떤 일이 일어날 것인지 추측해볼 수 있다. 일단, 배열의 원하는 원소에 바로 접근하려면, 기본 주소가 필요하다. 즉, 배열의 기본주소 Base Address를 저장할 변수가 필요하다. 다음으로는 value에 해당하는 자료형의 크기를 저장할 변수가 필요할 것이다. 왜냐하면, int 32형의 경우 4byte를, int 64형의 경우 8byte가 배열 한 칸을 움직이는 최솟값이 되기 때문이다. (배열의 해당 원소의 주소 = base address + offset, offset = sizeof(자료형) * index) 그럼 좀 더 확장하여, 해시 테이블에서 사용되는 모든 타입의 key 에 대해선 어떻게 계산할까? key가 string이라고 가정하면, 문자열 abc와 문자열 bca는 위의 인덱스 개념처럼 서로 다른 위치를 가르치게 해야 한다. 그러면, 이 문자열들을 각기 다른 key를 갖게 해야 하는데, 컴퓨터 내부적으로는 숫자 이진수 0과 1로 ...

우리는 인텔의 x86-IA32를 줄여서 32bit 운영체제라고 부르고, x86-64(또는 x64)를 줄여서 64bit 운영체제라고 부른다. 이전에 AMD에서 32bit가 호환가능한 64bit OS를 선보이고, 인텔도 x64 이후 x86-64를 출시하면서 이제는 어떤 것이든 호환가능한게 당연한 상식이 되었다고 알고 있다. 따라서 호환가능함을 당연한 전제를 깔고 시작한다. 32bit 로 표현 가능한 메모리의 크기는 대략적으로 4GB(2^32)가 된다. 포인터는 변수의 메모리 주소를 가르키기 때문에, 우리가 사용하려는 주소값을 모두 가르킬 수 있는 크기가 필요하다. 따라서 위의 32bit 의 경우에는 어떤 변수 타입의 포인터라도 4byte 크기면 충분 하다. 64bit 의 경우에 포인터의 크기가 8byte 인 것도 위와 같은 논리를 따른다. 그런데, Visual Studio를 비롯한 컴파일러에서 x86, x64를 선택하여 컴파일하는 기능이 있다. 이를 이용하면, 사용가능한 메모리의 크기가 정해지므로 이에 따라서 포인터의 크기가 정해지게 되는 것이다. 결론적으로 운영체제의 표현 비트에 따라서 포인터의 크기가 변하는 것이 아니라, 컴파일 설정 에 따라서 변하게 된다. [참고] https://stackoverflow.com/questions/16823752/why-size-of-void-pointer-is-4-on-windows-64-bit-platform

https://www.acmicpc.net/problem/10610 Silver 5 라는 난이도 보다는 체감상 어려웠던 문제이다. 이 문제를 풀면서, 30의 배수를 어떻게 빠른 시간내에 판단할 수 있을까를 고민했다. 30의 배수는 3의 배수이면서 10의 배수인지를 판단하면 되는데,  10의 배수를 판단하는 방법은 0이 하나라도 있는지 보면 알 수 있어서 간단했다. 3의 배수가 관건이었는데, 3의 배수는 각 자릿수의 합을 다 더해도 3의 배수 꼴로 나타난다. 이렇게 주어진 수가 30의 배수임을 알게 되면, 내림차순으로 정렬해도 30의 배수가 된다. 추가적으로 이 문제를 풀면서, 각 자릿수의 합이 어떤 규칙을 갖는지 알아보았다. 3 6 9 12 15 18 21 24 27 30... 3 6 9 3 6 9 3 6 9... (각 자리수의 합이 3의 배수꼴로 나타남) 9 18 27 36 45 54 63 72 81 90... 162...  6147 9 9 9 9 9 9 9 9 9... (각 자리수의 합이 9의 배수꼴로 나타남) 3, 9 가 이러한 문제로 응용될 수 있겠다. 생각해보면, 90의 배수는 9의 배수와 10의 배수를 만족시켜야 한다. 그런데 9의 배수는 3의 배수이므로 저 문제에서 주어진 30이라는 수를 구했던 방법처럼 구할 수 있다. 이 방법 외에도 시간 내에 풀 수 있는 방법이 있는지 궁금하다.  :)

memset 함수를 사용하게 되면, 일반적인 for문을 이용하여 초기화할 때보다 속도상의 이점이 있기 때문에 배열을 초기화할 때 자주 사용하게 된다. 그런데, memset을 사용할 때 초기화할 값을 넣을 때는 조심해야한다. void   * memset (   void   * dest,  int  ch,  size_t  count  ) ; 값에 대한 타입이 int 형이지만, 기본적으로 내부에서 1byte 에 해당하는 단위로 초기화를 진행한다. 예를 들어서,  int n;  memset(&n, 1, sizeof(int)); cout << n; 위와 같이 사용한 경우, 출력 값이 16843009가 나온다. cout << (short)n; 위의 출력 값은 257이 나온다. 이 출력 값들을 이진수로 변환하여 분석해보자. 16843009 => 1000000010000000100000001 257 => 100000001 위를 최하위 비트부터 8개씩 끊으면, 1byte가 된다. 1    00000001    00000001    00000001 1    00000001 즉, 내부적으로 1byte에 해당하는 단위로 초기화를 진행하는 것을 볼 수 있다. 우리가 원했던 것은 int 형의 변수 n에 1이라는 정수형 값으로 초기화하는 것이다. 그런데 int 형은 4byte이므로, 4byte가 하나의 단위로 보고 최하위 비트에 1을 쓰고, 나머지 비트 31개를 0으로 초기화해야 하는데, memset 함수는 그러지 않고 1byte를 하나의 단위로 보고 초기화를 진행했던 것이다. 이러한 이유로 검색을 해보면, memset에 초기화할 때는 0을 쓰라고 권유 한다. 0의 경우에는 어떠한 단위로 진행해도, 모든 비트에 숫자가 0이기 때문에 올바른 결과가 나오기 때문이다. 그러나 0 이외에...

https://www.acmicpc.net/problem/20543 (혹시나 풀어보실 분들은 알고리즘 분류를 보지 않고 풀어보길 권장합니다.) 이 문제를 처음 보고, 간만에 신선하다는 느낌을 받았다. 어떤 알고리즘이나 자료구조를 알고 있으면,  흔히 많이 나오는 유형에 속하는 문제가 있는가 하면, 그렇지 않은 문제도 있다. 이 문제를 풀면서 규칙을 찾고 시간을 단축시켜 나가는 과정이 재미있었고, 예전에 수학에 매력을 느꼈을 때의 느낌과 비슷했다. 물론, 영문까지 포함한 많은 문제를 풀어본 건 아니지만 부족한 내가 느끼기에는 그랬다. 어려운 자료구조를 쓰지 않아도 (기본적인 재료로도)  충분히 난이도를 높여 갈 수 있는 (까다로우며 맛있는 요리?) 그런 문제들의 초입에 해당하지 않나 싶다. 아래는 풀이를 생각한 순서이다. 1. 출력은 맞지만 시간초과 풀이 2. 정답 풀이 먼저, 제한도 까다롭지 않고 시간도 2초나 주어졌기 때문에 풀어보는 것이 중요하다고 생각했다. N이 2,000일 때, 2차원 배열의 데이터 개수는 2,000 x 2,000 = 4,000,000 이다. O(n)에 해당하는 과정은 시간초과를 발생시키지 않으나, 폭탄을 찾기 위해서 자기 자신의 위치(arr[i][j])에서 가능한 모든 경우의 수를 찾으려고 하면 시간초과가 뜰 것이다. 여기까지 생각하고, 규칙을 생각해보았다. 예제 입력과 예제 출력들을 보면서, 가장 외곽에 위치한 배열의 원소들부터 채워가면 될 것이라고 생각했다. 먼저, (0, 0)부터 시작한다고 하면, 시계방향으로 테두리를 돌면서 1칸씩 안쪽으로 진행해볼 수 있다. 그러나 가장 첫 줄을 시물레이션 해보면,  우리가 이중 for문을 통해 배열을 탐색하는 일반적인 과정으로도 채워나갈 수 있다는 것을 알게 되었다. 왜냐하면, 폭탄이 있을 수 없는 구역이 존재하기 때문이다. (m = 1의 경우는 예외) m이 1인 경우에는 그대로 절댓값으로 바꿔서 출력하면 되고, m이 3이상의 홀수인 경우에 생각해보면, 외곽 테두리에 ...

  할로윈데이(10/31)를 맞이하여 깃헙에서도 소소한 변화가 있었다. 일명 잔디밭의 색이 바뀐 것이다. 이뻐서 기념샷을 촬영하였다.  :)

https://app.codility.com/programmers/challenges/ 이메일을 읽다가 Silver Challenge라는 문구에 관심이 생겨 참여하게 되었다. 읽어보니, 대략 알고리즘 문제를 풀면 되는 것 같았다. 그래서 '주말이고 시간도 있으니 풀어봐야지' 라고 생각하고 있다가 UTC 기준이라서 대한민국 시간으로 10/18(토) 02:00 인 걸 보고 다음 날에 풀기로 다짐했다. 문제는 1문제였고, 2시간 동안 풀면 되는 것이였는데, 1, 2, 3등의 푼 시간을 보니 쉬운 문제인 것 같았다. 다 풀고 나니 Codility에서 이런 것을 주었다. 정성이 담겨진 디자인이라 기분은 좋았다. 아래는 해당 문제에 대한 정보와 점수, 정확성, 효율성 이다. 다음에도 참여해보면 좋을 것 같다.  :)

  1번 문제 [Level 1] 3진수로 변환할 수 있는지 물어보는 문제였다. 2번 문제 [Level 2] 요구 조건에 따라 재귀 함수를 작성할 수 있는지 물어보는 문제였다. 쿼드트리를 규칙에 따라 압축하여 표현해야 한다. 비슷한 문제 : https://www.acmicpc.net/problem/1992 3번 문제 [Level 4] 트리 구조에서 세 점 사이의 거리의 최댓값 : f(a, b, c) = max(dist(a, b) + dist(b, c) + dist(c, a)) 를  만족하는 각각의 거리 중 중간값 : median(dist(a, b), dist(b, c), dist(c, a)) 을 구하는 문제였다. 일일이 구하면 시간초과가 뜰 것이므로 생각을 달리해야 한다. 트리에서 두 점 사이가 가장 멀 때(이 거리를 '트리의 지름')를 구하는 방법을 응용하여 풀었다. Idea : dfs(임의의 점, 현재까지 거리) dfs(1, 0) -> dfs(e1, 0) -> dfs(e2, 0) -> dfs(e3, 0) 비슷한 문제 : https://www.acmicpc.net/problem/1967 4번 문제 [Level 5] 문자열의 부분 문자 a와 b의 인덱스 차이가 최대가 되도록 골라서 합을 구하는 문제였다. https://programmers.co.kr/learn/courses/30/lessons/68938 시간초과를 해결할 수 있는 방법이 생각나지 않아서, 일단 할 수 있는 한 시간을 줄여보고자 노력했다. DP 개념을 응용했다. 문자열의 길이가 n이라고 하면, 부분 문자열들의 길이는 2~n이므로 먼저 메모이제이션을 이용해서 부분 문자열의 길이가 2일 때의 최댓값들을 구해놓으면, 다음 부분 문자열의 길이가 3일 때는 양 끝만 비교하면 된다. 이 과정을 부분 문자열의 길이가 n이 될 때까지 반복한다. 핵심은 부분 문자열의 모든 인덱스를 중복없이 계산하려고 했다. 이렇게 bottom-up 방식으로 모든 부분 문자열에 대...

..9/17 18:00 쯤에 카카오톡이 와서 이메일을 확인해봤다. 작년에 보았을 때는 2.5솔 정도 했었는데, 이번에는 4솔로 마무리하게 되었다. (1, 2, 3, 4 풀고, 5번 푸는 도중에 테스트 종료) 내가 느낀 문제별로 필요한 지식 및 아이디어는 다음과 같다. 1번 문제 - 문자열 처리 (+ 정규식) -> 문제에서 시키는 대로 차례대로 조건에 맞게 문자열을 필터링하였다. 2번 문제 - 적절한 자료구조 사용 능력 (완전탐색 / 해시) -> map을 사용하여 해당 값이 들어온 횟수를 세고, 큰 순서대로 담았다.     데이터의 개수가 많지 않기 때문에, 빈틈없이 잘 처리하는게 중요한 것 같았다. 3번 문제 - 적절한 자료구조 사용 능력 + 이분 탐색 응용 (트라이?) -> (1) 다차원 배열(마지막 차원은 동적 배열)을 사용하여 데이터를 담아 정렬한 뒤,     (2) lower_bound를 사용하여 조건에 맞는 데이터들을 가져왔다.     예를 들어서, "java, backend, junior, pizza, 100" 라는 데이터를     h[1][2][1][1].push_back(100); ~ h[0][0][0][0].push_back(100); 까지 저장했고,      "python, frontend, senior, pizza, 200" 라는 데이터는     h[2][1][2][1].push_back(200); ~ h[0][0][0][0].push_back(200); 까지 저장했다.     문제에 조건에 따라, "언어(3종류), 직무(2종류), 경력(2종류), 음식(2종류), 점수" 의      각 항목마다 정해진 개수가 있었는데,      이때, "- and - and - and - and 100" 이라는 형태로 쿼리가 들어올 수 있으므로  ...

decltype은 알고자 하는 변수 식의 타입으로 치환하는 역할을 한다. 예를 들어서 int a = 10; decltype(a) b = 3; b의 타입은 a의 타입인 int로 된다. 이로써, 정확하게 타입 그대로를 전달할 수 있게 된다. 또, 타입의 결과를 알 수 없을 때도 사용한다. template <typename T, typename U> void add(T t, U u, decltype(t + u) *result) {     *result = t + u; } (1) double t, double u => double * result (2) double t, int u => double * result (3) int t, int u => int * result

예를 들어서, while (arrSum[end] - arrSum[start - 1] < s) end++; 라는 코드가 있다고 하자. 반복문 안에서 end를 증가시키기 때문에, 배열의 범위를 벗어나지 않는 선에서 검사해야 한다. 인덱스에 대한 처리를 while 내부에 쓰거나, while의 조건문에 쓰는 방법 등이 있지만 아래처럼 범위를 검사하는 부분을 가장 먼저 쓰면 좋다. while (end < n && arrSum[end] - arrSum[start - 1] < s) end++; 이렇게 하면, if 문의 뒷 부분(arrSum[end] - arrSum[start - 1] < s)을 검사하기 이전에 앞 부분(end < n)을 검사하고 빠져나오게 된다. 왜냐하면, and 조건은 if (true && true) 인접한 두 조건을 모두 만족시켜야 하기 때문에 앞에서 하나라도 거짓인 명제를 만나면, 뒤를 볼 필요없이 빠져나오게 되기 때문이다.

//예외를 반환하지 않는다. int func1(int a, int b, int c) noexcept {     ... } //예외를 반환할 수 있다. int func2(int a, int b, int c) noexcept(false) {     ... } 예외처리에 관해서 한정자 noexcept를 작성하면 얻는 이점은 다음과 같다. (1) 예외 처리 여부를 바로 알 수 있다. (2) Strong exception guarantee (강한 예외 보증)     copy semantics가 아닌 move semantics로 처리한다. (3) Performance improvement (성능 향상)     해당 함수가 예외처리를 무조건적으로 하지 않는다고 가정하므로     예외를 반환할 수 있는 상황에 대한 고려를 하지 않는다. (여분공간X)

C++11 이후부터 이동 생성자라는 것이 생겼는데, 사용법을 간단하게 살펴보면 //이동 생성자 Test(Test &&test) {     data = test.data;     test.data = nullptr;    //이동 후, 다시는 기존의 변수를 사용하지 않을 목적. } //복사 생성자 Test(const Test &test) {     ... } 이런식으로 참조자(&)를 사용해서 클래스 내부에 정의해줄 수 있다. 불필요한 복사와 임시 변수를 최대한 없애기 위한 과정에서 탄생하였다고 한다. 더 이상 사용하지 않을 변수를 포인터를 활용하여 바꿔치기 한다. (소유권 이전) 클래스에서 생성자를 정의할 때, 복사 생성자도 같이 정의하는 경우가 많다. STL에 있는 자료구조에 이 사용자 정의한 클래스 객체들을 초기화할 때를 생각하면 vector<Test> v; v.push_back(test1); v.push_back(test2); ... 이런식으로 넣게 되는데, 이 때 push하는 과정에서 v의 사이즈를 필요할 때마다 늘리므로 기존의 데이터를 옆 칸으로 복사하는 과정이 필요하다. 그러나 이동 생성자가 정의되어 있으므로 이 과정에서 복사가 일어나지 않게 되어 낭비를 막는다. 이러한 취지에서 move()라는 함수가 있다. move()는 인자를 받아서 'r-value 참조자' 형태로 바꿔주는 역할을 하는데, ('r-value 참조자'는 위에서 이동 생성자를 정의할 때, 매개변수로 작성하였던 모습이다.) 이 함수를 이용하면, 불필요한 낭비없이 초기화가 가능하다. v.push_back(std::move(test));    //더 이상 test를 사용하지 않음을 유의 여기에 더해 한번 더 최적화를 할 수 있는 방법이 있다. push_back() 대신 emplace_back()...

문득, 트리 구조(Tree)로 이루어진 set과 해쉬 테이블(Hash Table)로 이루어진 unordered_set의 속도 차이를 손쉽게 경험할 수 있을 것 같아서 기존의 코드를 수정하고 제출해보았다. * 수정 전 실행 결과(set을 이용) : * 수정 후 실행 결과(unordered_set을 이용) :  모든 테스트 케이스에 대해서 유의미한 속도 향상을 보였다. 아래는 수정한 코드이다. https://github.com/JAlthea/Algorithm/blob/master/BFS/Programmers%20%EB%B8%94%EB%A1%9D%20%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0.cpp #include <vector> #include <queue> #include <unordered_set> #include <algorithm> using namespace std; struct hashFuction {     size_t operator()(const vector<int> &a) const {         int resultA = 0;         int digit = 1;         for (int i=0; i<4; i++)         {             resultA += a[i] * digit;             digit *= 10;         }         return resultA;     } ...

연속된 데이터를 출력문에 대한 코드를 작성하다보면, 마지막 출력의 경우에는 줄바꿈을 하고 싶을 경우가 있다. for (int i=0; i<n; i++)     if (i == n - 1)         cout << a[i] << "\n";     else         cout << a[i] << " "; 위와 같이 작성하는 경우가 많은데, 이것을 for (int i=0; i<n; i++)     cout << a[i] + " \n "[i==n-1]; 이렇게 바꿔서 작성할 수 있다. const char* tmp = " \n"; 형태로 볼 수 있고,  tmp[0], tmp[1]을 사용하듯이 " \n"[0], " \n"[1]로 보는 것이다. 특정 규칙을 갖는 문자열을 작성해두고, 인덱스를 넣어서 활용하는 방법도 있다. 예) "122333444455555..."[n%k];

map이 내부 구조가 트리(레드-블랙트리) 형태로 되어 있기 때문에 기본 로직에 따라 자동 정렬되므로 logN의 시간이 추가된다. 반면에, unordered_map(hash_map)은 hash-table 구조로 되어 있기 때문에 데이터를 넣어도 자동으로 정렬되지 않으므로 logN의 시간을 아낄 수 있다. 그러나, 내부 hash-function에 의해서 성능이 저하되는 경우에 (특히, 문자열) map보다 오래 걸릴 수도 있다. 정리해보면 기본적인 경우에는 둘 다 'key-value' 형식으로 되어있으므로 key를 이용하여 정렬된 결과를 얻을 것이 아니면 unordered_map을 이용하는 편이 나은 것 경우가 많다. (대부분의 경우의 우리가 원하는 것은 key를 이용해 바로 value를 가져오고 싶기 때문) 물론 경우에 따라서 hash-function을 작성하기 나름이다. 아래 링크는 참고한 사이트 http://veblush.blogspot.com/2012/10/map-vs-unorderedmap-for-string-key.html unordered_map을 적절히 사용하여서 해결할 수 있는 문제는 다음과 같다. (map을 사용하였을 때와 unordered_map을 사용하였을 때, 시간 차이를 느낄 수 있다.) https://programmers.co.kr/learn/courses/30/lessons/60060

C에서의 구조체(struct)는 기존의 개념과 같다. '사용자 정의 자료 구조' 같거나 서로 다른 데이터 타입(구조체 자기 자신도 포함)을 묶어서 사용할 수 있게 한다. C++에서 struct는 기존의 구조체 개념에 더해서 class의 개념까지 갖는다. class처럼 멤버 함수를 가질 수 있고, 상속을 비롯한 나머지 성격을 갖는다. 사실상 C++에서 struct와 class의 차이는 기본 접근 제어자를 빼고는 같다고 볼 수 있다. (struct는 디폴트 값으로 public이고, class는 디폴트 값으로 private인 차이)

각종 언어에서 for문을 어떻게 쓰느냐에 따라 속도가 다른 것들이 있는 것 같다. C++로 예를 들면, //Classic for loop for (int i=0; i<m.size(); ++i)   //Range-based for loop 1 for (auto i : m)     간편하게 쓰려고 위와 같이 사용하기 쉬운데, 저 위의 i는 값 복사로 인해 할당 받은 변수이다. 따라서 기존의 참조하던 방식과 비교해서 속도 차이가 벌어질 수 있다. //Range-based for loop 2 for (auto &i : m) 으로 사용하면 해결된다. 다른 언어에서도 내부 동작은 마찬가지로 생각할 수 있다.