전체 글

🗨 개인적인 공부 기록용으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)     ⭐ 해시 테이블은 키(Key)를 해시 함수를 통해 해시 값으로 변환하고, 이를 인덱스로 사용하여 데이터를 저장하는 자료구조이다.     📌 해시 테이블의 정의해시 테이블은 키(Key)를 특정 연산(해시 함수, Hash Function)을 통해 해시 값(Hash Value)으로 변환하고, 이를 인덱스로 사용하여 데이터를 저장하는 키-값(Key-Value) 매핑 자료구조이다.  일반적으로 해시 맵(Hash Map)이라고도 하며, 빠른 검색, 삽입, 삭제가 가능한 점이 특징이다.  키-값 구조는 "사전(Dictionary)"으로 예를 들 수 있다.사전(Dictionary)은 단어(키, Key)와 뜻..

🔗 문제 링크 : https://www.acmicpc.net/problem/2217  문제N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용..

🔗 문제 링크 : https://www.acmicpc.net/problem/1931  💀 2% 틀렸습니다! 19번째 줄 전에 `cur`과 `cnt`를 선언하는 과정에서 `cnt`만 `0`으로 초기화 했을 때 생긴 문제이다.`cur`도 `0`으로 초기화 해줘야, 정상적인 회의 시간 비교가 가능하다.   문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 ..

🔗 문제 링크 : https://www.acmicpc.net/problem/11047  문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.     입출력 예시입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)  출력첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.       풀이 그리디 알고리즘으로 해결할 수 있는 문제다...

🔗 문제 링크 : https://www.acmicpc.net/problem/7662  💀 12%에서 틀렸습니다! 이 경우는 문제에서 새로운 테스트케이스가 시작되면서 Q를 깨끗하게 비워주지 않아서 생기는 문제일 확률이 높다.본인도 Q로 사용할 컨테이너를 선언하는 위치를 테스트케이스 "시작 전" -> 테스트케이스 "시작" 부분으로 옮겨서 문제를 해결하였다.   문제이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는..

🗨 개인적인 공부 기록용으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)   ⭐ 오브젝트 풀은 반복적으로 생성/소멸되는 객체(`오브젝트`)를 풀(`Pool`)에 미리 생성 및 저장해 두고 필요시 꺼내 쓰고, 사용이 끝나면 다시 반환하여 관리하는 디자인 패턴이다.   게임 개발을 하다 보면 특정 객체(`Object`)는 생성하고 소멸시키는 작업을 자주 해야 하는 상황이 생긴다.특히 총알, 적(Enemy), 파티클 이펙트처럼 짧은 시간에 생성과 소멸이 반복되는 오브젝트들은 성능 저하의 주요 원인이 된다.이때, 생성/소멸의 부담을 크게 줄여 성능을 최적화시키는 패턴이 바로 오브젝트 풀(Object Pool) 패턴이다.     📌 오브젝트 풀이란?오브젝트를 미리 생성하여 풀(`P..

🔗 문제 링크 : https://www.acmicpc.net/problem/1920  ☁ `cin.tie(0)`의 필요성을 찾았다..! 지금까지 입출력 시간 절약을 위해 `ios_base::sync_with_stdio(0);` 이 한 줄만 사용하고 있었다.운 좋게도 `cin.tie(0)`까지 쓰지 않아도 통과되는 문제만 만났나 보다..그리고 내심 `cin.tie(0)`를 꼭! 필요로 하는 시간 제한 문제를 원했는지도 모른다. ⏱ 해당 문제 풀이 코드에서 `cin.tie(0)`를 사용하지 않으면 1%에서 시간초과가 뜨는 모습을 볼 수 있다.      문제N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.     입출력 예..

🗨 개인적인 공부 기록용으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :)   ⭐ 싱글톤 패턴은 클래스가 인스턴스를 단 하나만 갖도록 보장하며, 어디에서든 그 인스턴스에 접근할 수 있도록 전역 액세스를 제공하는 디자인 패턴이다.   클래스를 만들면 해당 클래스로부터 여러 개의 인스턴스를 생성할 수 있게 된다.하지만, 클래스에 대해 하나의 인스턴스만을 생성하고, 이 인스턴스를 전역적으로 관리해야 할 때도 생긴다. 예를 들면, 게임의 설정 정보를 한 곳에서 관리하는 경우가 있다. 이런 상황에서 가장 적합한 디자인 패턴이 바로 싱글톤(Singleton) 패턴이다.     📌 싱글톤 패턴이란?클래스가 인스턴스를 단 하나만 갖도록 보장어디에서든 그 단일 인스턴스에 접근할 수 있도록 ..

❗ 문제의 입출력 예시에 오류가 있어 문제(그림)에 맞게 입력값을 수정하여 풀이하였습니다. (2024-11-23)   문제지민이는 다양한 크기의 정사각형 모양 돗자리를 가지고 공원에 소풍을 나왔습니다. 공원에는 이미 돗자리를 깔고 여가를 즐기는 사람들이 많아 지민이가 깔 수 있는 가장 큰 돗자리가 어떤 건지 확인하려 합니다. 예를 들어 지민이가 가지고 있는 돗자리의 한 변 길이가 5, 3, 2 세 종류이고, 사람들이 다음과 같이 앉아 있다면 지민이가 깔 수 있는 가장 큰 돗자리는 3x3 크기입니다. 지민이가 가진 돗자리들의 한 변의 길이들이 담긴 정수 리스트 mats, 현재 공원의 자리 배치도를 의미하는 2차원 문자열 리스트 park가 주어질 때 지민이가 깔 수 있는 가장 큰 돗자리의 한 변 길이를 re..

문제민수는 다양한 지폐를 수집하는 취미를 가지고 있습니다. 지폐마다 크기가 달라 지갑에 넣으려면 여러 번 접어서 넣어야 합니다. 예를 들어 지갑의 크기가 30 * 15이고 지폐의 크기가 26 * 17이라면 한번 반으로 접어 13 * 17 크기로 만든 뒤 90도 돌려서 지갑에 넣을 수 있습니다. 지폐를 접을 때는 다음과 같은 규칙을 지킵니다.지폐를 접을 때는 항상 길이가 긴 쪽을 반으로 접습니다.접기 전 길이가 홀수였다면 접은 후 소수점 이하는 버립니다.접힌 지폐를 그대로 또는 90도 돌려서 지갑에 넣을 수 있다면 그만 접습니다.지갑의 가로, 세로 크기를 담은 정수 리스트 wallet과 지폐의 가로, 세로 크기를 담은 정수 리스트 bill가 주어질 때, 지갑에 넣기 위해서 지폐를 최소 몇 번 접어야 하는지..