본문 바로가기

전체 글

(23)
[Baekjoon] 1759 - 암호 만들기 (C++) https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 알고리즘 분류는 백트래킹(backtracking)으로 되어 있지만, 입력으로 들어오는 데이터의 크기가 그렇게 크지 않기 때문에 완전 탐색(brute-force search)이나 그냥 모든 경우의 수를 DFS(depth-first search) 방법으로 다 확인하면서 해도 쉽게 해결할 수 있습니다. 하지만 그냥 문제 취지에 맞게 백트래킹을 이용해 풀어 보았습니다. 방법은 간단합니다. 먼저 입력으로 들어오..
[Baekjoon] 11053 - 가장 긴 증가하는 부분 수열 (C++) https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 처음엔 꽤나 고민했던 문제였지만, DP(dynamic programming) 태그가 붙은 것을 보고 간단히 구현해서 풀 수 있었습니다. 이런 문제를 풀면서 느낀 게 DP 기법을 이용하면 복잡해 보이는 문제도 제법 간단한 코드로 구현할 수 있는 것 같더라고요. 생각보다 강력한 기법인 것 같습니다. 아직..
[Baekjoon] 14503 - 로봇 청소기 (C++) https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 생각보다 크게 어려웠던 문제는 아니었습니다. 로봇 청소기의 작동 조건이 문제에 명확하게 나와있었기 때문에 이를 그대로 코딩으로 구..
[Baekjoon] 14502 - 연구소 (C++) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 벽이 세워질 수 있는 모든 경우의 수를 고려하여 풀었습니다. 매번 벽을 세운 뒤에 바이러스를 확산시킨 후, 빈 공간을 계산하는 방식으로 풀..
[C++ STL] set, map 정렬 기준 바꾸는 방법 C++ STL에서 제공하는 set, map, multiset, multimap 등의 컨테이너는 자동으로 데이터를 정렬된 상태로 유지시켜 줍니다. 그래서 이러한 컨테이너에 데이터를 넣고 그대로 출력하기만 하면 오름차순으로 정렬된 데이터를 얻을 수 있죠. 하지만 가끔은 내림차순 정렬이 필요하거나 내가 원하는 방식대로 정렬되어야 하는 경우도 생깁니다. 이럴 때 어떻게 할 수 있을까요? set 컨테이너로 예를 들어 설명해 보겠습니다. set의 템플릿(template)을 살펴보면 다음과 같이 되어 있습니다. template _Kty 부분은 흔히 사용하는 키 타입을 설정하는 부분입니다. 우리가 봐야 할 부분은 바로 _Pr 부분입니다. 기본 값으로 less가 설정된 모습을 볼 수 있는데 이 less는 아래와 같이 정..
[C++] C++ 속도 측정 및 비교 모듈 내가 만든 알고리즘의 속도를 측정하거나 무엇이 더 좋은 성능을 보이는지 비교하고 싶을 때가 있습니다. 시간 측정 자체는 간단히 구현할 수 있지만, 그때마다 매번 만드는 것이 귀찮기도 하고 여러 코드 블록들을 한 번에 비교할 수 있으면 편할 것 같아서 직접 클래스로 만들어 보았습니다. 소요 시간 측정에는 chrono 라이브러리를 이용했습니다. 이를 이용하면 최대 나노초(nanosecond) 단위의 정밀한 시간 측정이 가능합니다. #include "PerformanceBenchmark.hpp" #include #include using namespace std; void codeBlock1() { unordered_map data; bool isKeyExist; data["Test 1"] = 10; data..
[Data] 더미 이미지 생성 사이트 https://placeholder.com Placeholder.com: Placeholder.com – The Free Image Placeholder Service Favoured By Designers What Is Placeholder.com? Placeholder.com generates custom placeholder images on the fly, like these examples:- How To Use Our Placeholders Just specify the image size after our URL (https://via.placeholder.com/) and you'll get a placeholder image. placeholder.com 더미 이미지를 편하게 생성할 수 ..