
스핀락스핀락은 스핀락은 임계 영역(critical section)에 접근하기 위해 락을 획득할 때까지 CPU를 멈추지 않고 계속 루프를 돌면서 대기하는 방식의 동기화 기법이다. 장점으로는 '컨텍스트 스위칭이 발생하는 다른 동기화 기법보다 오버헤드가 낮다.'단점으로는 '다수의 쓰레드가 경쟁할 경우, CPU 사용률이 급격히 증가할 수 있다.' 스핀락기법을 사용할 때 컨텍스트 스위칭 비용이 다른 동기화 기법들 보다 낮은 이유는 System Call 호출을 통해 커널 모드로의 전환이 발생하지 않기 때문이다. 예로 this_thread::sleep_for(std::chrono::milliseconds(100)); 를 호출하게 되면 쓰레드는 '커널 모드'로의 전환이 발생한다.OS는 현재 쓰레드를 대기 목록에 추가하..
![[C++] 다형성과 가상 소멸자](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FWB2bS%2FbtsMUrxouUA%2F6Lqw6AbYE9q31kYQ6JsTy1%2Fimg.png)
C++은 객체 지향 프로그래밍 언어이다.OOP의 속성으로는 은닉화, 캡슐화, 상속성, 다형성이 있고 OOP의 특성으로는 추상화가 있다.이중에서도 다형성은 쉽게 말하면 '모습은 같은데 형태는 다른 것'을 의미한다.상속관계에서 다형성이 활용되는데 주의해야할 것들 중 이번 글은 '가상 소멸자'에 대한 부분이다. parent* p = new child();우리는 위처럼 '업캐스팅'을 자주 사용할 때가 많다. 위 코드를 컴퓨터 입장에서 보면 부모 클래스 포인터로 무엇인가 가르키고 있기 때문에 가르키는 대상이 무조건 부모 클래스 객체라고 생각할 수 밖에 없다.(원하는 동작은 parent*로 가르키고 있지만 실 객체는 child라고 인식 시키고 싶은 것이다) 위 코드는 child클래스가 parent클래스로 부터 함수..
![[백준] 2852 NBA 농구 C++](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F2d84A%2FbtsMI6UmiAd%2Fusep3HAmd9thcd0qUHNTKk%2Fimg.png)
https://www.acmicpc.net/problem/2852풀이 농구 골 넣는 문제이다.포인트는 '분 -> 초'로 단위로 단위 통일 인듯하다. 분끼리 계산 & 초끼리 계산하면 복잡하기 때문에 단위를 통일해주고이긴 시간을 누적해주어야 하기 때문에 prev라는 변수를 통해 이전에 골을 넣은 시간을 추적해준다.그리고 분 & 초를 초단위로 변경 및 출력하기 위해 substr를 사용해주도록 하자. 1. 초로 단위 통일2. 이긴 팀 변수 증가3. 골을 넣은 시간(prev)로 추적4. 이긴 팀의 시간을 계산하여 누적5. substr로 출력 코드#includeusing namespace std;#define endl '\n'using ll = long long;#define prev ppp1#define visi..
![[백준] 3474 교수가 된 현우 C++](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FwFcFA%2FbtsMI5HI00o%2Fl0R7bN3tFonTa4MnE3kRD1%2Fimg.png)
https://www.acmicpc.net/problem/3474 접근 아이디어적인 문제라고 생각한다. 안 풀어 보면 맞추기 힘들거 같은...우선 5600에서 0의 개수를 구해야한다. 지금은 2개라는 것을 알 수 있는데 한번 쪼개보자.5600 = 56 * 10 * 10 = 56 * (2 * 5) * (2 * 5)이다.5600에서 0의 개수는 10의 개수에 따라 결정이 된다는 것을 알 수 있고 10의 개수는 2와 5의 개수로 결정이 된다는 것을 알 수 있다.어떤 수 n에서 2의 개수가 7개 5의 개수가 3개라면 10은 3개가 나오게 된다. 7, 3 중에 최소값이 10의 개수가 된다. 5!을 예로 들면 1 2 3 4 5에서 2의 배수의 개수는 5 / 2 => 2개, 5의 배수의 개수는 5 / 5 => 1개 ..
![[백준] 16953 A->B C++](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fmc9D3%2FbtsLJAWtPYH%2Fd8JQfA9O1ki0UEUCtRjVu1%2Fimg.png)
https://www.acmicpc.net/problem/16953해설A->B를 만드는 문제이다.본인은 처음에 일단 그리디하게 A에서 어떻게 해야 최소의 연산 횟수로 B를 만들 수 있을 지 고민을 했는데 답이 안나오더라.. 그래서 반대로 생각해보면 A에서 B를 만들 수 있다는 것은 B에서 A로도 만들 수 있다는 것이고 그렇지 않다면 -1을 출력하면된다.B에서 A를 그리디하게 만드는 것이다. dfs, bfs로도 풀 수 있다.우선 bfs로 푸는 경우 노드간의 가중치가 모두 동일 하다고 볼 수 있다. a * 2나 a * 10 + 1이나 비용이 1이라 할 수 있기때문에 최단거리(최소 비용)을 보장해준다. bfs도 만약 b까지 도달하지 못하면 -1을 출력하면 된다. dfs로 푸는 경우 a를 2배 하는 경우, a ..
![[백준] 블로그2 C++](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fc5TvMF%2FbtsLFg9KT8b%2FWyWjvk4NDk8iXgYbAKF1Q1%2Fimg.png)
https://www.acmicpc.net/problem/20365해설우선 언제 최소의 횟수가 되는지 부터 생각을 했다.모든 문제를 파란색으로 다 칠하고 나머지 빨간색에 해당하는 부분들을 빨간색으로 칠하면 최소가 되지 않을까? 생각했는데 문제는 빨간색이 더 많을 때였다따라서 빨간색이 더 많은지 파란색이 더 많은지 살펴보고 더 작은 개수를 차지하는 색으로 일부분을 칠해주어야한다. 본인은 처음에 파란색으로 일부분을 칠할 때, 빨간색으로 일부분을 칠할 때, 둘다 계산을 해준다음에 이중 최소를 출력했는데, 이렇게 하지않고 밑줄 친 부분대로 해주어도 상관없다. 코드 본인 코드#include using namespace std;using ll = long long;// 빨간색으로 색을 칠하는 것과 파란색으로 색을 ..
![[백준] 14916 거스름돈 C++](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FJmQJf%2FbtsLClEhVcR%2F0wV3AM4lkCPF6USa9Px0f0%2Fimg.png)
https://www.acmicpc.net/problem/14916 해설그리디 문제인데 DP로도 풀 수 있다. 5원을 최대한 많이 거슬러 주어야한다.어떻게 최대한 많이 거슬러 줄 수 있을까? 첫번째 방법은 2원씩 n에서 빼본다. 그러다가 5로 나누어 떨어지면 정답을 출력한다.두번째 방법은 A(n / 5)개의 동전에서(5원의 개수) n - A가 홀수라면 --A 해주고 짝수라면 2로 나눈 몫을 출력한다.5원을 최대한 많이 주어야 하기때문에 A의 개수를 줄여가보면서 개수를 세어보는 것이다.세번째 방법은 DP이다. n원의 최소 값은 min(n - 2, n - 5) + 1이다.만약 11원의 경우 9원에서 2원을 더한 것, 6원에서 5원을 더한 것 중 최소 값을 고르면 되는 것이다.메모이제이션을 활용한 DP이고 B..
![[백준] 줄세우기 2631 C++](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbEseQj%2FbtsLDmIMsin%2FPoglOHaocoBTNwdyGVZcH0%2Fimg.png)
https://www.acmicpc.net/problem/2631 해설줄세우기 문제이다.어떻게 아이들을 옮기면 최소의 횟수로 정렬된 상태를 만들 수 있는지 묻는 문제이다.직관적으로는 간단한데, 어떠한 기준으로 어떤 수를 옮길지 처음 풀면 알기가 굉장히 힘들다.본인도 https://www.acmicpc.net/problem/7570 문제 풀다가 안 풀려서 해당 문제 부터 풀었다...ㅎㅎ해당 문제는 LIS (Longest Increasing Subsequence) 문제이다.가장 큰 증가하는 부분 수열의 길이만 구해주면 바로 풀린다.근데 이 문제가 LIS라는것 자체를 생각해내는게 어렵다. 그럼 일단 왜 LIS인지 보자.3 7 5 2 6 1 4 순으로 있을 때 최소의 이동 횟수를 구하려면 3 5 6 아이들은 이..