🗨 개인적인 공부 기록용으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :) ⭐ 해시 테이블은 키(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번째 줄 전에 curcur과 cntcnt를 선언하는 과정에서 cntcnt만 00으로 초기화 했을 때 생긴 문제이다.curcur도 00으로 초기화 해줘야, 정상적인 회의 시간 비교가 가능하다. 문제한 개의 회의실이 있는데 이를 사용하고자 하는 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) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는..
🗨 개인적인 공부 기록용으로 정리한 내용입니다. 잘못된 내용에 대한 피드백은 언제나 감사합니다 :) ⭐ 오브젝트 풀은 반복적으로 생성/소멸되는 객체(오브젝트)를 풀(P∞l)에 미리 생성 및 저장해 두고 필요시 꺼내 쓰고, 사용이 끝나면 다시 반환하여 관리하는 디자인 패턴이다. 게임 개발을 하다 보면 특정 객체(Object)는 생성하고 소멸시키는 작업을 자주 해야 하는 상황이 생긴다.특히 총알, 적(Enemy), 파티클 이펙트처럼 짧은 시간에 생성과 소멸이 반복되는 오브젝트들은 성능 저하의 주요 원인이 된다.이때, 생성/소멸의 부담을 크게 줄여 성능을 최적화시키는 패턴이 바로 오브젝트 풀(Object Pool) 패턴이다. 📌 오브젝트 풀이란?오브젝트를 미리 생성하여 풀(`P..
🔗 문제 링크 : https://www.acmicpc.net/problem/1920 ☁ c∈.tie(0)의 필요성을 찾았다..! 지금까지 입출력 시간 절약을 위해 iosbase::syncwithstdio(0); 이 한 줄만 사용하고 있었다.운 좋게도 c∈.tie(0)까지 쓰지 않아도 통과되는 문제만 만났나 보다..그리고 내심 c∈.tie(0)를 꼭! 필요로 하는 시간 제한 문제를 원했는지도 모른다. ⏱ 해당 문제 풀이 코드에서 c∈.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가 주어질 때, 지갑에 넣기 위해서 지폐를 최소 몇 번 접어야 하는지..