WhatISYourName?

이번 글의 주제는 '팰린드롬 판별'에 관한 이야기이다. 쉬운 주제이지만, 팰린드롬 판별을 구현할 수 있는 방법은 여러 가지이니 이에 대하여 작성해보려 한다. 1. 팰린드롬이란? 팰린드롬(Palindrome, 회문)은 처음부터 끝까지 거꾸로 읽어도 똑같이 읽히는 수 또는 문자열을 의미한다. 예를 들면, "racecar"나 "abcdcba", 한글로 하면 "수박이박수", "다시합창합시다" 정도가 되겠다. 이 팰린드롬을 판별하는 것은 여러 방법이 있지만, 먼저 가장 팰린드롬의 기본에 충실하게 코드를 작성하여 보자. 2. 팰린드롬 판별 1 - Naive 팰린드롬을 판별하려면, 처음 글자부터 마지막 글자까지 거꾸로 셌을 때 같은 수거나 문자열이면 가능하다. 입력이 문자열일 경우 다음과 같이 함수를 작성할 수 있다..

코드를 작성하다 보면, 두 배열을 비교해야 하는 순간이 찾아온다. 두 배열의 원소가 같은 값인지, 아니면 다른 값인지 하여서 하나씩 비교해야 할 때, 우리는 다음과 같이 작성한다. vector 형인 두 배열 vec, vec2를 비교한다고 하고, 두 배열의 길이는 같다고 가정하자. HTML 삽입 미리보기할 수 없는 소스 이런! 단순 비교인데 코드를 7줄이니 먹는다는게 불편하다. 이를 한 번에 해결할 수 있는 함수 equal을 소개하도록 하겠다. 1. equal (※ https://www.cplusplus.com/reference/algorithm/equal/ 에서 함수에 대한 정보를 확인할 수 있다.) C++의 알고리즘 관련 여러 함수들이 담긴 헤더 에서의 equal 함수는 다음과 같은 두 가지 구조를 가..

종종 비트마스킹을 활용한 다이나믹 프로그래밍이나 요세푸스 문제, BFS 등등 배열을 반시계 방향으로 $k$번 회전시켜야 할 경우, 다음과 같은 방법을 활용하였다. 다음 코드는 vector vec를 $k = 1$만큼 회전시킨다고 할 때, C++의 함수 swap를 활용하면 다음과 같이 작성할 수 있다. HTML 삽입 미리보기할 수 없는 소스 만약, $k > 1$이라면 새로운 container를 만들어, 나머지 연산을 활용하여 회전 이후 해당하는 위치에 새로 데이터를 담을 수 있다. 그러나, 이 경우 불필요하게 배열의 크기만큼 새로운 공간을 할당해야 하여 불편하다. HTML 삽입 미리보기할 수 없는 소스 이 경우 한 줄의 코드로 위의 작업을 한 번에 할 수 있는 함수가 있으니, rotate 되시겠다. 1. r..

[※ 주의 ※] 아래를 이해하지 않고 이 글을 볼 경우, 이해가 되지 않는 부분이 있을 수 있습니다. 1. [Algorithm] 어떤 알고리즘이 더 빠르고 효율적인가? - 시간복잡도 (4) 자, 대략적인 시간 복잡도 간 속도를 알았으니, 구체적으로 시간 복잡도를 어떻게 활용할 수 있는지 생각하여보자. 시간 복잡도는 말 그대로 "대략적인 시간"에 관한 이야기이다. 다른 말로, 대충 최대 어느 정도의 시간 및 연산 횟수가 소요될 지 어림잡을 수 있다는 이야기이다. 실제 코딩 테스트나 각종 대회에서도 필요한것은 소요되는 시간이지 시간 복잡도 그 자체가 아니다. 코딩계에서 통용되는 하나의 관습이 있다. 1초당 연산 횟수는 대략 1억($10^8$)번이다.구체적으로 말하자면 시간 제한이 1초라면 대략 1억번 연산 ..

C++에서 많은 사람들이 최솟값, 최댓값을 찾을 때 min, max를 쓸때 다음과 같이 쓰는 모습을 너무나도 많이 봤다. HTML 삽입 미리보기할 수 없는 소스 위에 코드같이 세 개의 값에 대해서만 min, max를 구한다면 그래도 불편을 감수하고 사용할 수 있다. 그런데, 만약 4개, 5개 등등... 굉장히 많은 수들의 최댓값, 최솟값을 비교해야 한다면? 값들이 배열이나 container안에 있으면 함수(max_element / min_element)를 통해 구할 수 있지만, 만약 각각의 값들이 다른 공간안에 담겨있다면 조금 곤란할 수 있다. C++ 11부터는 다음과 같이 min과 max를 구할 수 있다. 네 개의 값 a, b, c, d의 값 중 최솟값과 최댓값을 찾는다고 하면 코드를 이렇게 작성할 수..

종종 누적 합(partial_sum) 알고리즘을 사용하기 위하여 각 부분별 부분 합을 구할 때가 많다. 그럴 때 우리는 이런식으로 코드를 작성하였다. vector nums의 처음부터 끝까지 각 부분별 누적합을 구하고, 이를 vector acc_nums에 담는다고 가정하자. HTML 삽입 미리보기할 수 없는 소스 위와 같은 코드를 단 두 줄의 코드로 압축할 수 있으면 믿을 것인가? 누적 합을 쉽게 위하여 C++에는 partial_sum이라는 함수가 정의되어 있다. 1. partial_sum (※ https://www.cplusplus.com/reference/numeric/partial_sum/ 에서 함수에 대한 정보를 확인할 수 있다.) C의 Sequence 관련 여러 함수들이 담긴 헤더 에서의 part..