본문 바로가기

전체 글

 (336)
백준 23843번 콘센트 (C++) https://www.acmicpc.net/problem/23843 23843번: 콘센트 광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한 www.acmicpc.net - 접근법 - 먼저 콘센트의 개수가 최대 10개이기 때문에 시간복잡도에 큰 영향을 받지 않는 문제이다. 중요한 것은 콘센트들에 기기가 충전중 일 때 가장 오래걸리는 것을 꽂아놔야한다는 것이다. 만약 작은것 부터 꽂았다면 예제 1 1 4 4 8 에서 콘센트 1 - 1 4 콘센트 2 - 1 4 이런식으로 꽂히게 될 것이고 이후 8이 들어오면 답이 아니다. 그러므로 먼저 큰 놈이 들어와서 자리를 잡아야한다. 그..
백준 1339번 단어 수학 (C++) https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net ------------- 접근법 처음 보면 Backtracking 인가? 최적의 해를 어떻게 구할 수 있지? 라는 고민을 먼저 하게 된다. PS를 하면서 느끼는 건 "이렇게 하면 답이 나오는데 증명이 안됐다" 라는 해는 사용하면 안된다 맞는 경우도 있겠지만 매우 위험하다. 이 문제도 마찬가지다. ABCDE FCG 에서 AB까지는 9 8 을 하고 나머지는 번갈아가며 7 6 5 4.. 를 주니 ..
전통적인 동기화 문제 은행동기화 문제 같이 우리 실생활에서 사용되는 문제들도 있지만 예전부터 전통적으로 문제가 되는 문제들이 있다. 이를 전통적 동기화 문제라고 한다. Producer and Consumer Problem 생산자 소비자 문제 생산자는 데이터를 생성하고 소비자는 그 데이터를 소비한다. 예를들어 컴파일러가 데이터를 컴파일하면 어샘블리 코드가 되고 어셈블리어를 번역하여 기계어가 된다. 생산자는 데이터를 생성하고서 바로 소비자에게 넘기지 않는다. I/O차이, 연산차이 등 속도를 맞추기 위해 먼저 buffer에 데이터를 삽입하고 이후 소비자가 버퍼에 접근해 take 하는 식으로 처리된다. 즉, 버퍼는 생산자와 소비자가 모두 접근하는 Critical Section이 되는 것이다. 이를 해결하기 위해 상호배재를 위한 세마..
백준 20208번 진우의 민트초코우유 (C++) https://www.acmicpc.net/problem/20208 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 이전에 풀어본 문제들을 다시 풀어보는 프로젝트(?)를 진행중이다. 문제 양치기보다 각 문제들을 더 잘 파악하는게 좋을 것 같다는 생각이 들었다. 모든 문제를 내 힘으로 푼 것도 아니기 때문이다. 1. 문제 조건 - 가능한 많은 초코우유를 마시고 돌아올 수 있는 최대 민트초코우유 개수를 찾아낸다. 2. 접근법 - 먼저 보고 생각나는 건 DFS 완전탐색이다. 그리고 이것은 틀린 생..
백준 2533번 사회방 서비스(SNS) C++ https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 트리에서 다이나믹 프로그래밍 문제이다. 진짜 너무 어렵다 이런거 어떻게 풀어야하는 걸까. 계속 하면 할 수 있겠지라 생각하며 계속 하는 수 밖에 없다. * 트리에서 다이나믹 프로그래밍을 적용할 때는 보통 이번 노드에서의 dp값 다음 노드까지 포함했을 때 dp값으로 이어지는 top Down방식이거나 leaf까지 도달한 후 올라오며 값을 갱신하는 Bottom Up 방..
OS - 임계구역과 세마포어 Critical Section 공통 자원을 건드릴 수 있는 공간이다. 멀티 프로세싱에 의한 오류는 보통 여기서 발생한다. 해결 방안이 갖춰야하는 것 Mutual exclusion - 오직 한 쓰레드만 진입 Progress - 진입 결정은 유한 시간 내 Bounded waiting - 어느 스레드라도 유한 시간 내에 해결해야함. 프로세스/쓰레드 동기화 임계구역 문제 해결 (틀린 답 X) 프로세스 실행 순서 제어 비효율성 제거 세마포어 유명한 동기화 해결 도구 acquire() release() 세마포어는 상호베타를 위해 사용한다. void acquire(){ value--; if(value < 0){ add this process/thread to list block } } void release(){ v..
DOMIAS: Membership Inference Attacks against Synthetic Data through Overfitting Detection 논문 이론 MIA(Membership Inference Attack)는AI 모델이 어떤 데이터셋으로 학습되었는지 유추하는 공격법. 그 중에서도 DOMIAS는 데이터셋에서 적은 비중을 차지하는 부분의 데이터, 즉 원본 데이터셋에서 과적합된 데이터셋을 찾아내는데 효과적인 성능을 보임. 논문의 제목이 DOMIAS: Membership Inference Attacks against Synthetic Data through Overfitting Detection인 이유임. Attack AUC: 특정 데이터가 학습 데이터셋에 속하는지 추론하는데 얼마나 효과적인가를 나타냄. 값이 높다면 공격에 대해 민감하다는 의미. DOMIAS는 과적합된 모델에 대해 좋은 성능을 나타내기 때문에 모델 Epoch이 높을수록 다른 모델..
백준 1092번 배( C++) https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 정렬, 그리디 알고리즘 문제이다. 난 그리디 알고리즘이 약한 것 같다. - 내 접근법 먼저 Crain과 Weight는 최대한 비슷한 값 끼리 매져주는 것이 좋다. 그러므로 난 Crain은 오름차순, Weight는 내림차순 정렬을 해주었다. 그리고 Crain의 시작부분과 Weight의 시작부분부터 비교하며 크레인에 적재가 가능하면 Weight 벡터에서 삭제하고 다음 크레인의 상태로 ..

티스토리툴바