# cpp
[C++] 백준 11724 : 연결 요소의 개수
bfs 연습용으로 푼 문제.bfs로 노드를 하나하나씩 체크해준다. 한 번 bfs를 돌렸을때 방문되지 않은 노드가 있으면 그것이 바로 연결 요소가 아닌 것이 있음을 뜻한다. 따라서 cnt 개수를 올려주고, 그 노드에서 다시 bfs를 돌린다.
백준 10217번: KCM Travel
백준 10217번: KCM Travel도로포장 문제랑 비슷하다. cost 상태를 정의하고 소요 시간을 기록한다. 튜플 쓰기 넘 불편하다. 왜 5초나 걸렸을까? DP로 풀면 더 빨라질지도?
[C++] 백준 2178 : 미로탐색
dfs 열심히 풀어보려고 공부하면서 푼 문제. 전형적인 bfs 문제라고 볼 수 있다.이런 미로 문제는 목적지를 찾자마자 최단 경로임을 보장할 수 있으므로 bfs를 사용한다.
1162번: 도로포장
백준 1162번: 도로포장어려운 다익스트라. 단순하게 방문 여부로 우선순위 큐에서 거르지 말고, 거리를 비교한다. 거리를 기록할 때 몇 번 도로를 포장했는지 상태를 정의한다. 약간 dp느낌?연산자 오버로딩 잘못해놓고 한참 고민함 ㅠㅠtypedef struct \_Dat
[C++] 백준 5430 : AC
숫자를 쉽게 입력받기 위해 인터넷 검색을 좀 이용하였다! 역시 모든 라이브러리는 존재한다.stoi : string to intisdigit : 숫자인지를 판별덱에 대한 성질을 알면 쉽게 풀 수 있다.앞과 뒤에서 모두 양방향으로 넣고 뺄 수 있다.
[C++] 백준 18870 : 좌표 압축
메모리도 고려하고 푸는 방식도 전부 생각해냈지만 아쉽게 시간 복잡도 때문에 좀 헤멘 문제. O(N^2)는 불가능하고 O(N logN)의 시간 복잡도에 맞춰야한다.
메모리 모델
여러 쓰레드가 동일 메모리에 동시 접근 그 중 write가 문제가 된다atomic is_lock_free 원자적으로 처리되었는가?seq_cst(가장 엄격) 컴파일러 최적화 여지 적음 직관적, atomic 동작원리\-가시성 코드재배치 바로 해결 acquire_releas
Dijkstra풀이 (백준 9370번)
(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다
Thread Local Stoage(TLS)
쓰레드들이 하나의 로직에 몰리지 않게 해야한다. 쓰레드 마다 독립적으로 가지고 있는 공간(스레드별로 독립적으로 가지고 있는 스택영역과 같다) Heap이나 데이터영역(static 변수,전역변수)가 있는 공간에서 큰 덩어리를 떼어다가 TLS 영역에서 계산한다.
[C++] 백준 1927 : 최소 힙
백준 11279 최대힙 문제와 동일한 문제. 다른점이 있다면 최소 힙(부모노드가 자식노드보다 작거나 같은 값을 가진다) 이므로 자동으로 내림차순으로 정렬되는 우선순위 큐를 오름차순 우선순위 큐로 바꾸어서 사용하면 된다.
[C++] 백준 11279 : 최대 힙
힙에 대해서 다시 공부해 볼 수 있는 시간이었다.트리를 사용하여 높은 값을 트리의 부모 노드에 배치하는 그러한 완전 이진 트리의 형태를 띈다. 시험보면 무조건 나와서 아직 까먹지는 않았는데 트리를 직접 구현하라니 시간도 많이 들고 너무 막막했다...
