이세계개발자의 개발일지

이번 문제는 1764번 듣보잡이다.접근법두 리스트의 교집합을 구해야 함각 이름은 문자열이며 중복되지 않음이름이 50만 개씩 들어오므로 시간복잡도 O(N log N) 이하 알고리즘 필수작성코드#include using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0); long long N,M; cin >> N >> M; unordered_set s; for(int i = 0; i > str; s.insert(str); } vector v; long long count = 0; for(int j = 0; j > str; auto a = s.count(str);..

이번 문제는 7785번 회사에 있는 사람이다.접근법✔ 요구사항같은 사람이 여러 번 출입할 수 있음중복된 출입이나 퇴근은 없음현재 사무실에 남아 있는 사람만 출력출력은 사전 역순✔ 핵심 아이디어이름을 집합(set) 또는 해시셋(unordered_set)으로 관리하면 삽입/삭제가 빠름enter → 이름을 집합에 추가leave → 이름을 집합에서 제거최종적으로 남은 사람들을 사전 역순으로 출력1차코드#include using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0); long long N; cin >> N; vector v; for(int i = 0; i > name >> inout; i..

이번 문제는 14425번 문자열 집합이다.접근법문자열을 빠르게 검색할 수 있는 자료구조가 필요함 > 중복이 없고, 정렬된 상태를 유지하는 set 사용각 문자열을 탐색할 때는 s.find(str)을 사용하면 O(log N) 시간 내 탐색 가능작성코드#include using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0); int N,M; cin >> N >> M; set s; for(int i = 0; i > str; s.insert(str); } int count = 0; for(int i = 0; i > str; if (s.find(str) != s.end(..

이번 문제는 18870번 좌표압축이다.문제 설명N개의 정수가 주어진다. 각 정수에 대해, 해당 값보다 작은 서로 다른 값의 개수를 출력하라.즉, 배열 내 모든 값을 0부터 시작하는 순위(rank)로 압축한 결과를 출력하면 된다.단, 입력되는 정수의 범위는 최대 ±10⁹이므로, 단순하게 배열로 인덱싱할 수 없다.따라서 좌표 압축(Coordinate Compression) 기법을 사용한다.접근법 핵심 아이디어값 자체가 아니라 값의 상대적인 순서만 중요하다.중복된 값은 같은 압축값을 가져야 한다.압축값은 해당 값이 정렬된 배열에서 몇 번째에 위치하는지로 정의된다. 좌표 압축 알고리즘 (O(N log N))원본 배열을 복사하고 정렬한다.정렬된 배열에서 중복을 제거한다.각 원소의 값을 압축된 순위로 매핑한다...

이번 문제는 1620번 나는야 포켓몬 마스터 이다솜이다. 접근법포켓몬 이름을 입력받으며:번호 → 이름 저장: vector v[N+1]이름 → 번호 저장: unordered_map m쿼리를 읽고:쿼리가 숫자인지 확인 (all_of(s.begin(), s.end(), isdigit))숫자면 v[번호] 출력문자열이면 m[이름] 출력 이름 → 번호unordered_mapO(1) 평균해시 기반 빠른 조회번호 → 이름vector (1-based)O(1)인덱스 직접 접근작성코드#include using namespace std;int main(void){ ios::sync_with_stdio(false); cin.tie(0); int N,M; cin >> N >> M; vector v; u..

이번 문제는 11723번 집합문제이다.접근법1. 원소 범위가 작다 → 배열 또는 비트마스크 사용 가능원소 범위: 1 ≤ x ≤ 20집합 전체를 표현하는 데 21칸짜리 배열 또는 정수형 1개로 충분함2. 연산이 많다 → O(1) 시간 복잡도 필수find(), erase()가 포함된 STL vector나 set 사용 시 시간 초과 발생모든 연산을 상수 시간에 처리해야 함 1차 코드int 형의 vector를 사용해서 find, erase 등의 메서드를 사용하여 구현 > 시간복잡도 O(n) TLE#include using namespace std;int main(){ ios::sync_with_stdio(false); long long num; cin >> num; vector v; ..

이번 문제는 2776번 암기왕이다.접근법주어진 수첩 1의 숫자 리스트에 대해 수첩 2의 각 숫자가 존재하는지를 빠르게 판단해야 한다.단순한 선형 탐색은 시간 초과되므로, 이분 탐색 또는 해시셋을 사용해야 한다. 알고리즘 설계수첩 1의 숫자들을 오름차순 정렬수첩 2의 각 숫자에 대해 이진 탐색 수행시간 복잡도정렬: O(N log N)M개의 숫자에 대해 각각 O(log N) → 총 O(M log N) 작성코드# include using namespace std;int main (void){ ios::sync_with_stdio(0); cin.tie(0); long long T; cin >> T; for (int i = 0; i > N; vector v1; for..

이번 문제는 17266번 어두운 굴다리이다.접근법특정 밝기 거리 X를 기준으로, 가로등들이 굴다리 전체를 커버할 수 있는지를 확인한다.이분 탐색을 통해 최소한의 X를 찾는다.알고리즘 설계이분 탐색 범위는 start = 1, end = NX가 주어졌을 때, 가로등이 굴다리 [0, N]을 모두 커버할 수 있는지를 판단판단 기준첫 번째 가로등이 0보다 멀면 안 됨 → pos[0] - X > 0이면 실패두 가로등 사이가 비면 안 됨 → pos[i+1] - pos[i] > 2 * X이면 실패마지막 가로등이 끝까지 도달해야 함 → pos.back() + X 작성코드# include using namespace std;int main (void){ ios::sync_with_stdio(0); cin.tie(0)..

이번 문제는 16401번 과자 나눠주기 문제이다.접근법어떤 길이 L로 자를 경우, 각 과자로 만들 수 있는 조각 수는 과자 길이 / L이다.모든 과자에 대해 이 값을 합산한 결과가 M 이상이면 해당 길이로 나눠주는 것이 가능하다.이분 탐색을 통해 가능한 최대 길이 L을 찾는다.알고리즘 설계입력된 과자 길이를 배열에 저장한다.탐색 범위는 start = 1부터 end = max(과자 길이)까지로 설정한다.이진 탐색을 수행하며, mid를 현재 시도하는 과자 길이로 간주한다.각 과자마다 길이 / mid를 계산하여 총 몇 개의 조각을 만들 수 있는지 확인한다.총 조각 수가 M 이상이면 길이를 더 늘려볼 수 있으므로 start = mid + 1, 답을 갱신한다.그렇지 않다면 end = mid - 1로 범위를 줄인다..

이번 문제는 1072번 게임이다.접근법이 문제는 정수 승률이기 때문에 변화가 일어나지 않을 수도 있다. 예를 들어,현재 승률이 80%일 때, 1~수십 판 이겨도 여전히 정수 승률은 80%일 수 있다.또한, 최대 10억 판 이상을 더 해야 바뀔 수도 있으므로 완전 탐색은 불가능하다.따라서 이진 탐색(Binary Search)을 이용한다. 알고리즘 설계현재 승률 Z를 계산한다: Z = (Y * 100) / XZ가 99 이상이면, 승률은 절대 1 이상 증가할 수 없으므로 -1 출력1부터 10억까지 이분 탐색 범위를 설정mid값을 더 이긴 경기 수로 가정하고, 새로운 승률을 계산새 승률이 Z보다 크면 정답 후보로 저장하고, 더 적은 mid를 탐색아니면 mid를 증가시킴최솟값을 찾아 출력작성코드# include ..