서론 진짜 순수 문제 풀이 시간만 5시간은 걸렸다. 이렇게 어렵게 풀 문제였나 생각이 들어서 마음이 심란했던 하루다. 2일 차 통신망 분석 문제 : 그래프에서 연결된 것들의 집합 중 가장 밀도가 높은 컴포넌트의 정보를 구하자. 간선을 2차원 배열 edge에 받아 저장해 주었다. 빠른 시간 복잡도를 위해서 각 노드(i)에서 갈수 있는 노드(j)를 저장해 주었다. 연결된 것들의 집합을 DFS를 통하여 구하고(밀도를 구하기 위해 간선의 갯수도 구하고), realComponent에 저장해주었다. 출력 조건을 맞추기 위해서 realComponent배열 앞에 밀도와 (컴퓨터의 수 * -1) 마지막으로 (컴포넌트에서 가장 작은 수* -1) 를 넣어주고 내림차순으로 정렬하여 realComponent[0]에 있는 값을 ..
문제 링크 https://www.acmicpc.net/problem/17252 ◆문제 해결 및 설명◆ 문제 : 3의 거듭제곱의 합으로만 이루어져 있다면 YES, 아닐 시 NO를 출력하여라. 알고리즘 분류 : 수학, 부르트포스 알고리즘, 사칙연산 첫째 줄에 2,147,483,647보다 작거나 같은 음이 아닌 정수 N이 입력된다. 기본 int로는 해결 할 수 없어 int64_t를 헤더를 통해서 선언해 사용하였다. ※ 0은 삼삼한 수가 아니다. 풀고 검색해보니 생각보다 푸는 법이 많았다는 걸 알 수 있었다. 첫째. 3^N > 3^(N-1) + ... + 3^(0) 내가 푼 방법인데, 3진수를 cpp에서 지원하지 않기 때문에 이를 구현하지 않고 풀 방법이 있나 생각하다 쓰게 되었다. 아래 표는 3의 거듭제곱을 ..
서론 DFS로 풀다가 Runtime Error... BFS로 풀다가 Timeout.... 으악 살려줘~ 2일 차 발전기 문제 : 상하좌우로 "연결된 집" 집단의 개수를 구하여라 문제 설명을 비약적으로 짧게 만들었으나 문제를 푸는 데에 문제는 없다... 처음엔 DFS를 통해서 풀었으나 1000 * 1000과 같은 경우에 Runtime Error(재귀 한도 초과로 추측)가 발생하여 BFS로 짜주었다. 오늘도 맞왜틀? Timeout을 중점으로 글을 쓴다. ◆코드 전문◆ #include #include using namespace std; int N, answer = 0; int map[1100][1100]; int dx[4]{1, -1, 0, 0}; int dy[4]{0, 0, 1, -1}; queue que..
서론 새로운 한 주의 시작이다. DP 배낭 문제를 생각하며 푸니 금방 풀었지만... Runtime Error가 발생하여 골머리를 앓았다. DP적인 부분은 다른 블로그에서 많이 이야기할 테니, 내가 겪은 맞는데 왜 틀리지를 위주로 설명하도록 하겠다. 바로 확인해보자. 1일 차 통증(2) 문제 요약 : 통증 N과 치료제 A(x만큼 회복), B(y만큼 회복)가 무제한으로 주어질 때, 최소한의 치료제를 써서 통증을 0으로 만들 아이템의 최소 사용 개수를 출력하라. 0으로 맞추지 못할 때는 -1을 출력하여라. 0으로 맞추지 못할때는 -1을 출력하여라.라는 구문 덕에 자연스럽게 DP를 통해서 구현하게 되었다. 원리는 A, B를 하나 더 쓰기 전 스트레스 상태에서 0이 될 수 있다면, 최소 값을 구하였다. dp[i]..
