너와 나의 스토리

문제: https://www.acmicpc.net/problem/11722 문제 풀이: https://hororolol.tistory.com/103 (BOJ) 11053 가장 긴 증가하는 부분수열 문제: https://www.acmicpc.net/problem/11053 문제풀이: 현재 위치 이전에 자기보다 작은 값 찾아서, 작은 녀석까지의 최대 개수+1 소스 코드: int n,arr[1001],dp[1001],res; int main() { ios::sync_with_stdio.. hororolol.tistory.com ㄴ 거의 같은 문제 부등호 방향만 바꾸면 됨 소스코드: 풀이1 - 시간 복잡도: O($n^{2}$) int n,arr[1001],dp[1001],res; int main() { ios:..

문제: https://www.acmicpc.net/problem/11053 문제풀이: 현재 위치 이전에 자기보다 작은 값 찾아서, 작은 녀석까지의 최대 개수+1 소스 코드: 시간복잡도: O($n^{2}$) int n,arr[1001],dp[1001],res; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n; for (int i = 0; i > arr[i]; dp[i] = 1; for (int j = 0; j < i; j++) { if (arr[j] < arr[i]) { dp[i] = max(dp[i], dp[j] + 1); } } res = max(res, dp[i]); } c..

문제: https://www.acmicpc.net/problem/9251 문제풀이: ex) ACAYKP CAPCAK A C A Y K P 0 0 0 0 0 0 0 C 0 0 1 1 1 1 1 A 0 1 1 2 2 2 2 P 0 1 1 1 2 2 3 C 0 1 2 2 2 2 2 A 0 1 2 3 3 3 3 K 0 1 2 3 3 4 4 => 답: 4 행과 열의 첫 줄을 0으로 해둠 같은 문자를 만나면 대각선, 즉, 현재 (x,y)라면 (x-1,y-1) 값 +1 해준다 // arr[x][y]=arr[x-1][y-1]+1; 다른 문자를 만다면 자신의 왼쪽이나 위쪽 값 중 큰 값을 넣어줌 // arr[x][y]=max(arr[x][y-1],arr[x-1][y]); 가장 큰 값이 결과값이다. 소스 코드: strin..

문제: https://www.acmicpc.net/problem/12763 문제 풀이: dfs로 풀었다 dist[n]에 pair로 시간이랑 금액 저장 현재 가는 정점이 원래 저장된 값(다른 루트로 온 결과 값)보다 시간이랑 금액 둘 다 손해면 안 가고 둘 중 하나라도 이득이면 감 만약 제한된 금액이나 시간이 이미 지나게 되면 안감 소스 코드: typedef pair P; int n,m, time, money,res; vector dist; vector adj; void dfs(int cur) { if (cur == n) { res = min(res, dist[cur].second); return; } for (auto &i : adj[cur]) { if (dist[i.first].first money) ..

출처: http://pages.cs.wisc.edu/~remzi/OSTEP/threads-sema.pdf The crux: lock과 condition variables을 대신해서 어떻게 semaphores을 쓸까? 31.1 Semaphores: A definition semaphore: 우리가 두 개의 루틴으로 조작할 수 있는 정수 값을 가진 객체 POSIX 표준에서는 이 루틴은 sem_wait(), sem_post()이다 semaphore의 초기화 값은 이것의 행동을 결정하므로 초기화 필수 1. semaphore 초기화 sem_init(&s, 0, 1); // semaphore가 같은 프로세스 내에서 thread를 공유 ㄴ 초기화 값은 1이면 critical section을 보호하는 lock처럼 사용..

문제: https://www.acmicpc.net/problem/14618 문제풀이: 1. 진서집에서 시작해서 다익스트라 돌리기 (양방향) 2. 진서가 가장 빨리 갈 수 있는 집 찾기 B집부터 비교해서 갱신해주고 그 후, A집 비교해줘서 B집이랑 같은 거리이면 A 출력하기 소스코드: #define inf 987654321 using namespace std; typedef pair P; int n, m, jinsu, k,dist[5001]; bool visit[5001]; vector a, b; vector adj; priority_queue pq; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> n >> m;..

문제: https://www.acmicpc.net/problem/14615 문제풀이: 1번 부터 bfs 돌려서 갈 수 있는 곳들 찾아 놓음 진행 방향을 반대로 바꿔서 n번 부터 bfs 돌려서 갈 수 있는 곳들 찾아 놓기 폭탄 설치될 때 1에서 그 곳 갈 수 있고, (진행 방향 반대일 때) n번에서도 갈 수 있는 곳이면 "defend the CTP" 아니면 "Destroyed the CTP" 소스코드: int n, m, tc; bool visit[100001],cango[100001]; vector v,v2; queue q; bool bfs() { memset(visit, false, sizeof(visit)); while (!q.empty()) q.pop(); visit[n] = true; q.push(..

문제: https://www.acmicpc.net/problem/15787 문제풀이: 승객 태우기 v[w] = v[w] | (1 w >> e; v[w] = v[w] | (1 > w >> e; v[w] = v[w] &~ (1 > w; v[w] = v[w] w; v[w] = v[w] >> 1; v[w] = v[w] & ~1; } } for (int i = 1; i