공부하자

https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 감정이입이 되는 문제다. 행렬 형식으로 주어지는 그래프에 대해 도연이의 위치를 시작점으로 BFS로 탐색하여 행렬 전체에서 P의 갯수를 찾으면 되는 문제이다. 이때 주의할 점은, O라고 해서 탐색을 하지않고 넘어가는것이 아니라, X를 제외한 모두를 탐색을 하긴 하지만 P일 경우에만 cnt를 올려주어야 한다. int BFS(int x, int y) { queue Q; Q.push(make..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 골드3 정도 난이도의 DFS + DP를 활용한 문제이다. 처음에는 BFS로 접근을 했다가 여러 경로를 모두 탐색해야 하기에 visited 배열을 사용할 수 없음을 깨닫고 DFS로 방향을 틀었다가 시간초과가 나서 DFS에 DP를 접목시킨 방법으로 풀었다... 상당히 험난한 과정을 거쳤다. 애초에 행렬의 최대 사이즈가 500x500인 250,000이고, 방향 4개를 전부 탐색해야 하는데다가 그것도 ..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 인접 리스트로 주어진 그래프를 보고 이분 그래프인지 아닌지 판별하면 된다. 이분 그래프에 대한 자세한 내용은 필자가 따로 정리해두었으니 해당 게시물 참조하면 된다. ⤵️ https://jhoon-study.tistory.com/89 [자료구조] 이분 그래프 Bipartite Graph 이분 그래프란? 인접한 정점끼리 서로 다른 두가지 집합으로만 나눈 그래프를 의미한다. 위 그림과 같이 모든 정점이..

이분 그래프란? 인접한 정점끼리 서로 다른 두가지 집합으로만 나눈 그래프를 의미한다. 위 그림과 같이 모든 정점이 두 집합으로 나뉘고(여기서는 서로 다른 두 색상으로 구별한다.) 같은 집합끼리는 인접하지 않는 그래프의 형태이다. 이분 그래프의 특징 한 간선의 양 끝 정점은 서로 다른 집합에 속해 있어야 한다. 같은 집합의 정점끼리는 하나의 간선으로 이어질 수 없다. Cycle이 발생했을 때, 그 Cycle을 잇는 간선의 개수는 짝수여야 한다. 간선이 없고 정점만 있는 그래프도 이분 그래프이다. 이분 그래프 판별볍 이분 그래프 여부를 판별하기 위해서는 보통 DFS나 BFS로 그래프를 탐색하면서 판별한다. 1. BFS , DFS 를 수행하며 각 정점을 방문할때 마다 인접한 그룹과 다른 색으로 칠한다. 2. ..

[종합] - 한국은행 금통위, 기준금리 연 3.5%로 9차례 연속 동결 - 금통위 "3개월 후 인하 가능성" 첫 언급…채권 '강세' - "내수 부진 더 악화"… 한은, 올 성장률 2.1%·물가 2.6% 유지 - 코스피, 외인·기관 매수세에 반등…2660선 안착 - 뉴욕증시, 엔비디아 실적 발표 앞두고 혼조 마감... 나스닥 사흘째 하락 - 日증시, 역대 최고치 34년만에 경신…'버블 경제' 시절 넘어섰다. 39,000선 첫 돌파 - 유럽 주가도 장중 최고치…스톡스600, 495.46p 넘어 - 홍콩 증시, 中 정책 기대로 상승 마감…H주 2.05%↑ [글로벌] - 美 엔비디아 실적 시장 예상치 상회…주가 시간외거래 7%↑, 작년 4분기 매출 265%↑·총이익 769%↑…1분기 매출도 전망치 넘어 - 월가..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 간단한 문제인거 같은데, 생각보다 많이 헤맸다... 일단 가중치 없는 그래프 탐색이니 BFS 문제로 갈피를 잡고 들어갔으나, 각 인덱스 마다 계속 BFS를 하는것으로 방향을 잡고 풀다가 계속 틀렸다. 이유인 즉, 자식노드가 복수일 경우에는 해당 방법으로는 절대 부모노드를 구할 수 없기 때문이다. 따라서, 그냥 루트 노드 1에서부터 BFS를 한번만 돌리는 방향으로 바꾸어 풀었다. 처음에 왜 이 생각을 못했을까 싶다. 생각해보면 정말 당연한건데 말이다. 부모노드를..

[종합] - 4거래일 만에 외국인 매도세 전환‥코스피 2650대 마감 - ‘엔비디아 급락’ 충격에 뉴욕 증시 하락 마감… 나스닥 0.92%↓ - 日증시, 반도체주 매도에 하락 마감…닛케이지수 0.26%↓ - 엔비디아發 한파에다 임박한 FOMC... 신중 모드로 돌아선 투자자들 - 60대 이상 일자리 27만개 늘었는데...청년·40대 일자리는 감소 - 금감원, 올해 24개 금융사 정기검사…공정금융·건전성 등 초점 [글로벌] - 동남아 주요 6개국, 성장률 일제히 하락 - 이더리움, 2년만에 3000달러 '터치'… 美 현물 ETF 승인 기대감 - 엔비디아 충격+포드 가격 인하, 테슬라 3% 이상 급락 - 실적 발표 하루 앞둔 엔비디아, 4% 이상 급락, 800억 달러 증발하며 시총 5위로 밀려 - 월마트, ..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net #1697 숨바꼭질의 연장선상에 있는 문제이다. 숨바꼭질 3는 아예 다익스트라로 노선을 변경해서 풀면 그나마 풀어냈었는데, 2는 오히려 같은 BFS 코드를 공유하는 문제인지라, 방법을 생각해내는것에 더 어려움을 겪었다. 일단 문제 자체는 가중치가 없는 그래프를 탐색하여 최단거리를 도출해야 하기 때문에 BFS를 이용해 풀었고, 기존 #1697에서 썼던 코드를 일..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 이전에 작성했던 #1697 숨바꼭질 문제의 연장선상에 있는 문제이다. 당시엔 가중치가 없는 그래프에서 최단 경로를 찾는 형식이었기에, BFS를 이용해서 해결했었지만, 이번엔 가중치가 새로 생겼다. 걸어가는 경우와 순간이동을 하는 경우 두가지 경우의 가중치가 다르기 때문에 BFS가 아닌 다익스트라를 이용하여 문제를 풀어야 한다. 필자가 기존에 다익스트라를 활용하..

https://www.acmicpc.net/problem/25757 25757번: 임스와 함께하는 미니게임 첫 번째 줄에는 사람들이 임스와 같이 플레이하기를 신청한 횟수 $N$과 같이 플레이할 게임의 종류가 주어진다. $(1 \le N \le 100\,000)$ 두 번째 줄부터 $N$개의 줄에는 같이 플레이하고자 하는 사람들 www.acmicpc.net 실버5 난이도라 매우 쉽다. 중복제거 매커니즘만 알고있으면 5분만에 풀수 있을 정도다. 입력받은 사람들의 명단에서 중복되는 값들을 제거 한 후, 중복 없는 자료구조의 크기만큼 케이스에 따라 1이나 2나 3으로 나눠주면 된다. 다만 여기서, "임스는 한 번 같이 플레이한 사람과는 다시 플레이하지 않습니다." 라는 조건이 있기 때문에, 한번 플레이한 사람은 ..