공부하자

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 우선순위 큐에 관련된 간단한 예제이다. 입력되는 인덱스들의 절댓값이 더 작은 원소들을 출력하고, 절댓값이 같다면 실제 인덱스 값이 더 작은 (쉽게 말해 양수와 음수중 음수를 출력) 값을 출력하면 된다. 이 매커니즘을 구현하려면 먼저 우선순위 큐 라는 자료구조를 알고 있어야 한다. 우선순위 큐에 대한 내용은 다음 게시글에서 자세하게 작성해 놓았다. https://jhoon-st..

priority queue C++ STL 컨테이너 중 하나로, 내부적으로 힙 자료구조로 구현된 우선순위 큐를 보다 편하게 사용할 수 있게 해준다. 기존의 스택이나 큐 같은 자료구조의 경우, 먼저 들어왔는지 나중에 들어왔는지 같은 인덱스가 삽입된 순서에 의거하여 구성되는 자료구조 형식이라면, 우선순위 큐는 인덱스가 삽입된 순서와는 별개로 특정한 가중치를 가지고 그 가중치에 따라 순서가 결정되는 자료구조 형식이다. 보통 C++ STL에서 사용하는 priority_queue 컨테이너의 경우엔 인덱스의 크기가 가장 큰 순서대로 top에 정렬된다. (기본은 내림차순) 만약 인덱스의 크기가 가장 작은 순서대로 top에 정렬하고 싶다면, priority_queue pq; 와 같이 정렬기준을 명시하거나 그냥 삽입할때에..

[종합] - 코스피 2,620·코스닥 820 회복, 코스피·코스닥, 외국인 '사자'에 설 연휴전 연이틀 상승 - 美S&P 5000선 목전… 사상 최고치, 나스닥·다우도 상승 마감 - 한국은행, 설 연휴 앞두고 4조7000억 상당 자금 공급, 지난해 대비 10% 상승 - 금감원, ‘틸론 불공정거래’ 참고인 키움證 수사 [글로벌] - 원·달러 환율 0.4원 오른 1328.2원 마감 - SMIC, TSMC등, 글로벌 파운드리 업체 연이어 호실적 - "美 금리인하 언제?" 글로벌IB 10곳 만장일치 2분기 금리 인하 예상 [기업] - 삼성전자 美 파운드리 공장 연내 가동 유력… 4나노 칩 연내 양산 속도 전망. 보조금 변수 - CJ ENM 영업이익 780% 급증…"티빙 폭풍성장" 목표주가 상향 - KB금융, S..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 이번 문제는 왕복 경로에 대한 다익스트라 수행에 대한 내용이다. 보통 다익스트라 라고 함은, 방향성 그래프에서 시작점과 도착점에 대한 경로의 최소비용을 구하는 알고리즘이다. 하지만 이 문제는 특정 경유지를 제시해주고, 시작점에서 출발하여 경유지를 경유한 다음 다시 원점으로 돌아오는 왕복 경로에 대한 탐색을 요구한다. 문제에서 요구하는 조건이 얼핏보면 복잡해 보이지만 ..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 알고리즘을 활용하는 기초중의 기초 문제다. 문제에서 요구하는대로 입력을 받아 다익스트라 알고리즘을 통해 도시간의 최소비용을 구해서 출력하기만 하면 된다. 필자는 다익스트라 알고리즘 구현에 배열 자료구조 대신 우선순위큐를 활용하여 구현하였다. 다익스트라를 구현할때에는 배열을 사용하는 것보다 우선순위큐를 사용하는것이 훨씬 좋다. 정점의 개수를 V, 간선의 ..

[종합] - 외국인, 기관 순매수 힘입어 2600선 되찾은 코스피…저PBR株 계속 뛸까 - 지난달 주요 시중은행 저축성 예금 총 잔액 14조원 증가... 기준금리 인하 기대감 커지며 정기예적금 수요 상승 - 비트코인 2주 연속 반등 기조, 5700만원대 회복, 다만 美 연준 발 3월 금리인하 가능성으로 인해 후퇴…전주比 0.9%↑ - 연초 5대 시중은행서 1868명 희망퇴직…퇴직금 평균 5억 - 건강보험 의료비 폭증에 2년 뒤부터 적자…2028년엔 1.6조로 5배 치솟아 - "12만원 돌려드려요" 건보료 내고 병원 안 가면 '바우처'로 돌려준다. 연 의요 이용 4회 미만이면 최대 12만원까지 환급 - ‘빨리빨리’ 한국, 이동통신 다운로드 속도 아태 1위 [글로벌] - S&P500, 다우지수 사상 최고치 ..

https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 입력받은 행렬을 평면좌표 형태로 바꾸어 BFS 순회로 인근 영역의 넓이와 갯수를 구하는 문제이다. 근래에 계속 풀어왔던 문제 형태인지라 어렵지 않게 풀어낼 수 있었다. 다만, 실제로 코테나 시험장에 가서 이정도 난이도의 문제를 마주쳤을때 지금처럼 능숙히 풀어낼 수 있을지는 미지수다. PS는 별 지름길이 따로 없이 그냥 계속 연습하고 꾸준히 풀어보는수 밖에 없는 것 같다. #in..

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 요 근래에 BFS를 활용한 문제들을 계속 풀어보고 있는데, 이제 좀 감이 생긴 듯 하다. 문제 접근방식도 그렇고 풀이 과정에 있어서도 나름 매끄럽게 풀었던 문제라 생각한다. 이 문제의 요점은 다음과 같다. 나타날 수 있는 테스트 케이스에 대해 특정한 조건마다 브루트포스 방식으로 순회하며 BFS로 같은 영역을 구하는 것이다. 어차피 맥시멈이 100인 케이스밖에 다루지 않기 때문에 조건문이 3-4개가 중첩된..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 이 문제 또한 백준 #2667 단지 번호 붙이기와 유사한 문제이다. 주어진 행렬 형태의 그래프를 순회하며 같은 문자로 묶인 구역을 탐색하는 문제인데, 이 문제와 다른 문제들의 차별점이라 함은 행렬에서 나타나는 알파벳이 여러가지이고, 그 알파벳들을 각기 다른 구역으로 판별하여 탐색하여야한다. 따라서 기존에 사용하던 BFS 함수 포맷에 char 인자를 하나 더 전달하여 각기 다른 알파벳들을 따..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 가중치가 없는 그래프에서의 최단경로 찾기. 역시나 BFS를 활용하는 문제이다. 인접리스트 형식이 아닌 숫자 행렬로 입력이 주어지기 때문에 상하좌우 연산을 통해서 그래프를 탐색하고, 목적지까지의 거리를 계산하기 위해 중간중간에 거치는 정점마다의 거리값 배열인 dist를 이용하여 해결했다. 다만 도중에 scanf에서 &arr[i][j]와 같이 이중반복문으로 배열의 인덱스에 직접 접근하여 입력했는데, 숫자가 공백없이 주어지다 보니 입..