본문 바로가기

전체 글

Baekjoon 2110 공유기 설치 2019. 2. 13. Link https://www.acmicpc.net/problem/2110 소스결과 2576 KB / 20 ms 출처 Baekjoon 언어 C++ 17 분류 이분탐색 설명 도현이가 언제나 와이파이를 즐기기 위해 공유기 C개를 설치하려고 할때 인접한 공유기 사이의 거리를 가능한 크게 해서 설치 하려한다. 그 때 최대 값을 출력해주자 문제가 이해가 안간다. 코드를 봐도 모르겠다. 스터디에서 코드를 받고 코드를 보고 이해하려 했으나. 문제가 더 이해가 안되는 상황에 이르렀다. 공유기 개수.. 공유기 범위는 제한이 없는건가..? 문제 친절하게 설명해주실 분을 구합니다.. 소스코드 #include #include #include using namespace std; const int MAX = 200000; bo..
Baekjoon 2805 나무 자르기 2019. 2. 13. Link https://www.acmicpc.net/problem/2805 소스결과 5896 KB / 180 ms 출처 Baekjoon, COCI 2011/2012 Contest #5 언어 C++ 17 분류 이분 탐색 설명 환경에 관심 많은 상근이가 목재 절단기를 이용해 나무를 잘라 원하는 길이를 가져가기 위해 설정 하는 높이의 최대 값을 구하자 환경에 관심이 많으면 나무를 자르지 말지.. 왜 고통스럽게 ㅠㅠ 이분 탐색 문제라는 느낌이 들지만 기준을 잡기 너무 어렵다. 그리고 범위를 이동 시키는 방법도.. 이해가 잘 안가지만.. 처음에는 주어지는 나무 길이를 오름차순으로 정렬해 최소, 최대 값 사이중에 경계선 부분을 찾아내는 방법인줄 알았으나.. 그냥 설정 할 수 있는 최대 범위를 설정해 이분 탐색을 진..
Baekjoon 2463 비용 2019. 2. 13. Link https://www.acmicpc.net/problem/2463 소스결과 3948 KB / 44 ms 출처 Baekjoon, 한국정보올림피아드 지역본선 2001 중/고등부 언어 C++ 17 분류 Disjoint-Set 설명 정점과 가중치가 있는 간선으로 이루어져있는 그래프에서 특정 방식으로 된 연산을 진행 할 때 연산의 총 합을 구하는 프로그램을 작성하자 처음에 봤을 때 이해가 조금 안됬던 문제. 연산은 쉽게 이해가 가지만 총 합이라는 의미가 이해가 잘 안갔었다. 결론은 주어지는 모든 정점 중 2개의 점을 선택하는 경우에 대한 연산의 총 합을 구하는 문제. 앞 문제와 같이 해결 방식을 순차적 방법으로 해결 하는 것 보다 역순으로 가중치 총합을 이용하는 방법으로 해결 했다. 또한 역순으로 진행 ..
Baekjoon 13306 트리 2019. 2. 13. Link https://www.acmicpc.net/problem/13306 소스결과 10180 KB / 132 ms 출처 Baekjoon, KOI 2016 중등부 언어 C++ 17 분류 Disjoint-Set 설명 그래프의 정보가 주어지고, 그래프의 일부 내용이 변경 되었을 때 주어지는 질의에 대해서 답을 출력해주는 프로그램을 작성한다. 여태껏 문제와는 문제를 보는 방식이 조금 달랐던 문제. 좋은 내용을 배웠다. 주어지는 질의에 대해서 질의를 역순으로 해결해 나가면서 정답은 질의 순으로 제출하는 방법이다. 결과적으로 질의가 시작되기 전의 그래프는 주어진 그래프의 모습일테니 거꾸로 생각해서 풀어도 문제가 없다. 출력만 유의하면 될 뿐 Disjoint-Set의 기본 골격을 유지하고 질의를 거꾸로 풀어나가보..
Baekjoon 4195 친구 네트워크 2019. 2. 13. Link https://www.acmicpc.net/problem/4195 소스결과 4360 KB / 132 ms 출처 Baekjoon, Waterloo's local Programming Contest, 27 September, 2008 언어 C++ 17 분류 해싱, 최소 스패닝 트리, 강한 연결 요소, Disjoint-set, 최대 독립 집합 설명 친구를 모으는 것이 취미인 민혁이가 자신의 친구 관계를 줄 때, 두 사람의 친구 네트워크에 현재 몇명이 있는지 구하는 프로그램을 만들어주자. Disjoint-Set을 이용하여 친구 관계를 Tree형태로 저장한다, 또한 입력되는 순서에 따라 결과 값이 다르게 저장된다. 자료형을 직접 String으로 저장하면 비교 연산에서 오랜 시간이 필요하게 된다. 친구이름..
BaekJoon 1717 집합의 표현 2019. 2. 13. Link https://www.acmicpc.net/problem/1717 소스결과 5896 KB / 40 ms 출처 Baekjoon 언어 C++ 17 분류 Disjoint-set 설명 0 ~ n 까지 총 n + 1개로 구성된 집합이 합 연산과 두 원소가 같은 집합에 속해 있는지 구하는 연산을 진행 할 때 같은 집합에 속하는지 확인 하는 연산에 대해서 결과 값을 출력해주어야 한다. Dis-Joint Set에 대한 기초적인 문제, 추가로 위 문제에서는 높이를 최대 2로 낮추는 작업을 해주어야 시간제한에 걸리지 않는다. 합집합을 구하는 연산을 진행 할 때 부모를 찾는 작업을 진행 해야 하는데 그 과정에서 높이를 압축시키는 과정이 진행 된다. 스터디를 진행 하면서 푸는 문제이기에 DIs-Joint Set을 클..
BaekJoon 16922 로마 숫자 만들기 2019. 2. 13. Link https://www.acmicpc.net/problem/16922 소스결과 1984 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 브루트포스 설명 I V X L 4개로 구성된 로마 숫자 N개를 이용하여 서로 만들 수 있는 다른 수의 총 가지 수를 출력하는 문제. 한개의 경우에 대해서 총 4개의 가지가 존재하는 전형적인 브루트 포스 문제 앞에서 미리 탐색을 한 경우에는 경우의 수에 추가 하지 않도록 확인 하는 변수가 필요하다. 또한 가지치기를 하지 않는 다면 바로 타임아웃이 걸린다. 모든 경우의 수를 다 확인 하면서 탐색을 적게 하는 방법을 적용해야 한다. 알고리즘 1. 숫자 n을 입력 받는다 ( 최대 깊이 ) 2. 0번 인덱스 부터 앞서 선택한 값 이상인 경우를 전부 탐색한다...
BaekJoon 1339 단어 수학 2019. 2. 8. Link https://www.acmicpc.net/problem/1339 소스결과 1988 KB / 1716 ms 출처 Baekjoon 언어 C++ 17 분류 수학 백트래킹 설명 단어로 된 수학 문제를 푸는 숙제를 받은 민식이를 도와주자. 각 알파벳에 대해서 0 ~ 9 사이의 숫자를 대입했을 때 합이 최대는 값을 찾아주자 백트래킹으로 풀기에는 생각보다 간당간당한 문제 처음에는 사용되는 알파벳에 9부터 역순으로 값을 대입해 보는 방법을 사용했지만 결과는 시간초과 TC조차도 상당히 오랜 시간이 걸렸다. 두번째로 선택한 방법은 사용되는 알파벳이 최대 10개이기에 10개에 맞춰 저장을 하고 각 값에 대해서 값을 지정하고 모든 값이 지정이 된다면 값을 치환해 결과를 구하는 방식으로 구했다. 두번째 방법이 되려 ..

티스토리툴바