코드 낙서장

문제 주소 : www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 문제 확인 bit dp 문제입니다. 입력받는 숫자의 개수가 15개 이므로 bit 형으로 표현할 수 있으며 나머지 값인 k 또한 100보다 작은 수 이므로 dp[1

문제 주소 : www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 문제 확인 스위핑과 우선순위 큐를 활용하는 문제입니다. 풀이 입력받은 선들을 x기준으로 내림차순 정렬을 한 후 우선순위 큐에 y 값을 내림차순으로 넣어 비교합니다. 비교식은 ary[i].x + dist que.pop() 이며 이러한 동작으로 인해 현재 이 조건을 만족하게 된다면 다음 단계에서 의미 없는 값이 되기 때문에..

문제 주소 : www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 문제 확인 그래프 탐색 문제입니다. BFS, 다익스트라 알고리즘으로 해결할 수 있습니다. 맵에서 도달할 수 있는 각 점을 하나의 버텍스로 잡으며 탐색한 후 기록된 값을 이용해 풀 수 있는 문제입니다. 풀이 죄수 2명과 상근이가 모두 움직이면서 한 점에서 만나는 경우 탈옥을 할 수 있다는 것을 이용합니다. 이 경우 한 점에서 만나는 특성상 정점에서의 각각 문을 연 최솟값이 다른 최솟값에게 영향을 미치지 않습니다..

문제 주소 : www.acmicpc.net/problem/18233 18233번: 러버덕을 사랑하는 모임 첫 번째 줄에 정수 N, P, E가 공백으로 구분되어 주어진다. (1 ≤ N, P ≤ 20, 1 ≤ E ≤ 1,000,000) 그 다음 줄부터 N개의 줄에 걸쳐 회원 1부터 순서대로 xi와 yi가 공백으로 구분되어 주어진다. (1 ≤ xi www.acmicpc.net 문제 확인 간단한 dfs 문제입니다. 통과는 간단하지만 시간과 메모리 단축을 하기 위해서는 조금 생각해야 할 것이 있습니다. dfs 탐색 횟수 줄이기 dfs 함수의 인자 수 줄이기 조건에 부합하는지 확인하는 함수를 dfs와 분리하여 dfs 함수 크기 줄이기 조건 확인 시 루프 문 최소화 풀이 stack을 이용하여 p개만큼 사람을 선택 해..

문제 주소 : www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 확인 세그먼트 트리를 활용하면 쉽게 풀 수 있는 문제입니다. 세그먼트 트리 : latter2005.tistory.com/28 [자료구조] 세그먼트 트리 자료구조 설명 : www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 ..

세그먼트 트리 : latter2005.tistory.com/28?category=946518 [자료구조] 세그먼트 트리 자료구조 설명 : www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A.. latter2005.tistory.com 세그먼트 트리에서 자주 업데이트가 발생할 때 이를 더욱 효율적으로 처리하기 위한 알고리즘입니다. 간단하게 설명하자면 구간 a~b의 값을 변경할 때 모든 트리구조, 배열을 변경하지 않고 접근 시 차근차근 변경해 나가겠다는 의미입니다. 예시를 들어 설명하도록 하겠습니다. ary = {0, 1,..

문제 주소 : programmers.co.kr/learn/courses/30/lessons/70130 코딩테스트 연습 - 스타 수열 programmers.co.kr 문제 확인 특별한 알고리즘이 필요없는 구현 문제입니다. 나오는 값들을 그래프 형식으로 저장한 후 하나씩 탐색하면서 최대 스타수열의 길이를 찾습니다. 풀이 수열의 길이가 길어지면 스타 수열을 찾기 위해 배열을 탐색하는 시간이 길어지므로 중복된 숫자를 다시 탐색하는 것은 비효율적입니다. 이를 방지하면서 해당하는 인덱스만 탐색을 하기 위하여 그래프를 사용합니다. 문제에서 나올 수 있는 숫자의 범위가 배열의 길이 이하이므로 2차원 배열 형태를 사용하며, 나오는 인덱스만 저장을 하면 되기 때문에 vector을 사용하여 저장합니다. ex) {0, 1, ..

문제 주소 : www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 확인 완전 탐색을 하게 되면 시간 초과가 나므로 이를 방지하기 위해 해쉬와 분할을 사용합니다. dfs의 변형으로 알고리즘만 이해한다면 쉽게 풀 수 있습니다. 풀이 n은 최대 40, 각 수는 절댓값이 100000을 넘지 않으므로 해쉬의 컨테이너를 4000000개로 설정하고 2000000을 기준으로 음수와 양수를 구분합니다. 백준 알고리즘 분류에 "중간에서..

문제 주소 : www.acmicpc.net/problem/2315 2315번: 가로등 끄기 첫째 줄에는 2개의 정수 N(1 ≤ N ≤ 1,000), M 이 있다. 첫 번째 정수 N은 가로등의 개수를 나타내는 정수이고, 두 번째 정수 M은 마징가 처음에 위치하는 가로등 번호이다. 다음 N 개의 줄에는 각 가 www.acmicpc.net 문제 확인 dp 응용문제입니다. 지나치는 길의 가로등은 끄는 것이 이득이므로 지나친 지점의 가로등을 고려할 필요는 없습니다. 따라서 dp 스텝을 총 2가지로 분류할 수 있습니다. left : right 사이의 가로등을 모두 끈 상태에서 left : right + 1 상태로 전의 하는 방법 ==> left 에서 right + 1로 이동 : 이동거리 = ary[right + 1..

문제 주소 : www.acmicpc.net/problem/1150 1150번: 백업 입력의 첫 번째 줄에는 정수 n 과 k 가 주어지는데, 각각 길 위의 회사 수(2 ≤ n≤ 100 000), 그리고 제공되는 네트워크 케이블 수(1 ≤ k ≤ ½ n)를 의미한다. 그 다음 n 줄에는 각각 하나의 정수 s (0 www.acmicpc.net 문제 확인 그리디 알고리즘 문제입니다. 선택할 간선들을 우선순위 큐를 활용하여 짧은 순서대로 뽑고, 뽑은 위치에 왼쪽, 오른쪽 간선을 하나로 합쳐 큐에 삽입하는 형식을 통해 인접 케이스를 해결합니다. 풀이 우선순위 큐를 사용하면 간단하게 연결된 회사끼리 묶으며 짧은 쌍을 쉽게 뽑아낼 수 있습니다. 주의해야 할 점은 조건 상 한 쌍을 뽑게 되면 양 옆의 쌍을 뽑을 수 없으..