2020의 게시물 표시

[Halloween Day] Github grass

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

Codility Silver Challenge 후기

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

프로그래머스 월간 코드 챌린지 1차 10월 후기

이미지
  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 방식으로 모든 부분 문자열에 대...

2021 카카오 블라인드 코딩테스트 1차 후기

이미지
..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" 이라는 형태로 쿼리가 들어올 수 있으므로  ...

[C++] 형식 지정자 키워드 : decltype

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

배열의 인덱스 범위부터 먼저 처리하기 : out of range

예를 들어서, 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) 인접한 두 조건을 모두 만족시켜야 하기 때문에 앞에서 하나라도 거짓인 명제를 만나면, 뒤를 볼 필요없이 빠져나오게 되기 때문이다.

[C++] 예외처리 한정자 키워드 : noexcept

//예외를 반환하지 않는다. 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++] Move semantics

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()...

2020 KAKAO BLIND RECRUITMENT - 블록 이동하기 : set에서 unordered_set으로 바꿔서 풀어보기

이미지
문득, 트리 구조(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;     } ...

const char* 형태의 문자열을 활용한 획기적인 방법?

연속된 데이터를 출력문에 대한 코드를 작성하다보면, 마지막 출력의 경우에는 줄바꿈을 하고 싶을 경우가 있다. 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과 unordered_map(hash_map) 중 무엇을 사용할까?

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/C++] C의 struct와 C++의 struct의 차이

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

Range-based for loop에서의 속도 차이

각종 언어에서 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) 으로 사용하면 해결된다. 다른 언어에서도 내부 동작은 마찬가지로 생각할 수 있다.

[C++] printf, scanf, "\n"와 cin, cout, endl의 속도 차이의 이유

알고리즘 문제를 풀다보면, 입출력이 빈번한 경우 cin, cout을 사용하기 전에 입출력 속도를 빠르게 하기 위해서 ios::sync_with_stdio(false);와 cin.tie(0);을 작성하여 쓰는 것을 볼 수 있다. 실제로 printf, scanf와 거의 차이가 없을 정도로 속도가 향상된 것을 볼 수 있다. 이유는 이 함수 내부에서 입출력을 포함하여 버퍼를 'flush' 해주기 때문에 그렇다. 마찬가지의 이유로 줄바꿈을 나타낼 때 endl 대신에 "\n"을 사용하여 속도를 향상 시키자.

undefined behavior

코딩하다보면, undefined behavior를 생각할 때가 있다. 틈날 때마다 보기위해 여기 링크를 걸어둔다. https://stackoverflow.com/questions/367633/what-are-all-the-common-undefined-behaviours-that-a-c-programmer-should-know-a

C++에서 for문이 제대로 돌지 않는 현상?

이미지
동적배열의 크기만큼 for문을 돌리는 문제에서 디버깅하다 발견하게 되었다. 현상은 다음과 같다. 위는 프로그래머스 사이트에서 돌린 결과이고, 아래는 필자의 비쥬얼 스튜디오에서 돌린 결과이다. 의미는 같은데, 아래의 for문이 전혀 출력되지 않는 것을 볼 수 있다! 혹시나 싶어서, Java에서 이클립스 환경에서 돌려보았는데, 자바는 성공적으로 출력이 되었다. 어떤 조건일 때 출력이 정상적으로 되지 않을까 궁금했는데, i가 -이면 위와 같은 현상이 발생하였다. 글을 쓰다가, 원인을 찾던 중 size()의 자료형이 size_t 인 것을 발견하였다. 이는 C/C++에서 쓰이는 데이터 타입으로 자세한 내용은 위키에 있다.  https://namu.wiki/w/size_t 이 자료형은 언뜻 보면 int형과 같아보이는데, 사실은 unsigned 정수형이라는 것이다. (size_t는 '이론상 가장 큰 사이즈를 담을 수 있는 unsigned 데이터 타입'으로 정의) 따라서 int형으로 선언된 i와 unsigned 정수형인 size()와의 비교에서 오버플로우 현상이 나타나는 것이었다.