개구리의 개발 블로그 개구리의 개발 블로그

백준 1707번 이분 그래프 파이썬 문제 링크 - https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 두 개의 그룹으로 노드를 나누고, 하나의 그룹의 노드끼리 연결되지 않도록 해야 한다. 문제를 보자마자 간단한 분리 집합 문제라고 생각했다. 하나의 노드를 기준으로 설정하고, 연결된 노드들을 모두 union 한다. 이 때 같은 부모를 가지는 집합에서 연결된 노드가 있다면 ‘NO’를 출력한다. 하지만 굳이 union을 할 필요 없이 BFS만으로도 간단..

백준 9370번 미확인 도착지점 파이썬 문제 링크 - https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 생각지도 못한 곳에서 계속해서 오답이 발생했다. 아마 나처럼 오답을 받고 검색하는 사람들이 꽤 될 것 같은 문제다. 최단 거리를 이동하면서 h→g 경로를 선택하는 경우가 무엇을 의미하는 지 파악하는 것이 중요하다. s→g 까지의 최단거리가 s→h→g 인 경우에 h→g 경로를 선택하게 된다. 반대로 s→h 까지의 최단거리가 s→g→h 인 경..

백준 1477번 휴게소 세우기 파이썬 문제 링크 - https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 프로그래머스의 징검다리와 유사한 문제였다. - https://school.programmers.co.kr/learn/courses/30/lessons/43236 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 만약 완전탐..

백준 1655번 가운데를 말해요 파이썬 문제 링크 - https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net N=10만이고 시간 제한이 0.1초인 문제다. 가운데 값이 갱신되는 블랙 박스가 있다고 할 때, 삽입과 조회가 모두 O(log N)안에 해결되어야 한다. B+tree가 생각났는데 이 때부터 계속 트리 구조를 수정하면서 그림을 그렸다. 제대로 구현되는 게 없어서 힌트를 보고 풀었다. 우선순위 큐를 사용하여 가운데에서 가장 가까운 ..

백준 2836번 수상 택시 파이썬 문제 링크 - https://www.acmicpc.net/problem/2836 2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 스위핑 알고리즘 문제이다. 스위핑 알고리즘이라고 해서 특별한 방법이 있는 것은 아닌 것 같고 전체를 탐색하며 마주하는 이벤트를 바로바로 처리하면서 푸는 유형이다. 그렇기 때문에 스위핑 자체에 집중하기보다 시간복잡도를 줄여 문제를 풀기 위한 방법을 떠올려야 한다. M명의 사람을 모두 태울 수 있기 때문에 순방향 구간을 태워줘야 하는 경우 신경 쓸 필..

백준 2370번 시장 선거 포스터 파이썬 문제 링크 - https://www.acmicpc.net/problem/2370 2370번: 시장 선거 포스터 첫줄에는 포스터의 개수 n(1 ≤ n ≤ 10,000)이 주어지고, 그 다음 n줄에는 각 포스터의 왼쪽 끝의 위치와 오른쪽 끝의 위치 l, r이 주어진다. (1 ≤ l

백준 14427번 수열과 쿼리 15 파이썬 문제 링크 - https://www.acmicpc.net/problem/14427 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 세그먼트 트리 문제를 공부해야겠다고 생각한 지 벌써 3개월은 된 것 같다. 심지어 이 문제도 트리를 이용한 해시 문제를 풀기 위해 시도했지만 도저히 안풀려서 알고리즘 분류를 보고 세그먼트 트리를 공부하게 되었다. 우선 쿼리 문제이기 때문에 python을 사용한다면 sys.stdin.re..

냅색 분류인 것을 보고 풀었기 때문에 일단 2차원 배열을 만들어야겠다는 생각을 했다. 풀긴 했지만 코드가 깔끔하지도 않고 시간도 꽤나 오래 걸렸다. 1106번 문제를 풀기 전에 1차원 배열을 이용해 평범한 배낭 문제를 풀이하는 방법을 알아보자. 0. 일반적인 냅색 문제 풀이(1차원 / 2차원 배열 이용) 12865번 평범한 배낭 문제를 기준으로 설명하겠습니다. https://www.acmicpc.net/problem/12865 2차원 배열에서 dp[i][j]에 i번째 보석까지 j 무게를 사용했을 때 얻을 수 있는 최대 가치를 저장한다. 모든 보석에 대하여 1에서 최대 용량까지 반복문을 실행하며 dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost]+ benefit)로 갱신한다. 2차..