펭로그

문제 링크 : https://boj.kr/1932 입력이 위 그림과 같이 정삼각형 형태의 피라미드의 형태로 주어진다.이 형태를 어떻게 입력받아야 할까? 하고 고민을 해봤다.첫줄부터 인덱스를 메겨서12 34 5 67 8 9 1011 12 13 14 15이런 형태로 각 줄의 첫 인덱스들이 1, 2, 4, 7, 11 이런 식으로 늘어나는 계차수열 형태로 입력받아야 하는가? 하고 고민도 해봤다. 하지만 입력을 보니 그냥 이런 형태 그대로 입력 받아도 계산하는데는 문제 없겠구나 싶었다.따라서, N*N 형태의 일반 매트릭스 형태로 입력받고 모든 노드를 0으로 초기화 시킨 상태에서 계산하도록 하였다. 이 문제는 재귀로 풀게되면 엄청난 연산 횟수로 시간초과를 발생시킬 수 있는 문제이다.상위 단계에 있는 인접 노드의 값..

문제 링크 : https://boj.kr/1834 이 문제는 막상 해보니 어렵지 않았다.종이에 직접 써보면서 규칙을 찾으니 쉽게 점화식을 찾을 수 있었다. [N = 젯수 일 때, 피젯수(몫,나머지) 순서]N = 1 일 때, 존재하지 않음N = 2 일 때, 3(1,1)N = 3 일 때, 4(1,1) 8(2,2)N = 4 일 때, 5(1,1) 10(2,2) 15(3,3)N = 5 일 때, 6(1,1) 12(2,2) 18(3,3) 24(4,4) 벌써부터 규칙이 보인다.1. 몫과 나머지가 같은 수들은 N+1의 배수들2. 배수의 갯수는 N-1개점화식을 구해보면 (N + 1) * i 가 된다. 단, 이 문제는 입력 최대 값이 2,000,000이기 때문에 최대로 올 수 있는 값은 sigma(i=1~1,999,999)..

문제 링크 : https://boj.kr/1978 이 문제는 에라토스테네스의 체를 이용하여 소수 리스트를 미리 구한다음 계산하면 쉽게 답을 찾을 수 있다.입력 최대값이 1000밖에 안되기 때문에 그냥 1000까지 미리 소수를 구하는 편이 빠른 것 같다. 12345678910111213141516171819202122232425262728293031323334#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); bool isPrime[1001]; memset(isPrime, true, sizeof(isPrime)); // 에라토스테네스의 체 이용하여 1000까지의 소수..

문제 링크 : https://boj.kr/2581 소수는 어떤 수 N의 약수가 1과 자기 자신만 가지는 숫자를 의미한다.소수를 구하는 것은 정말 어렵지만 '판별'은 가능하다.자기 자신보다 작은 정수 중에서 약수가 존재하는지를 2~N까지 반복하면 된다.하지만, 약수는 N의 제곱근 보다 큰 숫자는 절대로 나올 수 없다. N의 제곱근 보다 큰 정수에 어떤 정수를 곱하면 이미 N보다 커지기 때문이다. 따라서 N의 제곱근 범위까지만 구하면 된다.하지만 이 방법은 소수를 판별하는 방법이지 소수를 구하는 방법이 아니다.어떤 범위의 숫자가 주어졌을때 소수인지 아닌지를 판별하려면 1~N의 제곱근 까지 계산해야 하는데 이 것을 주어진 범위만큼 반복해야 하기 때문에 소수 리스트를 미리 구해놓고 구하는 편이 빠른 연산 방법이..

문제링크 : https://boj.kr/2468 흰색으로 연결된 부분들의 갯수를 세는 문제다.갯수를 세는 것은 DFS로 풀면 되는데.. 문제는 1~100까지의 비 내리는 높이들을 하나 하나 다 계산해봐서 영역이 가장 많은 것을 구하는 것이다.어떻게 해야 효율적으로 구할 수 있을까 생각해봤는데.. 일단 풀었다.1~100까지의 횟수는 그리 많은 횟수가 아니라 시간 복잡도 상으로도 O(1)에 해당하기 때문에..그래서 1~100 까지의 모든 높이마다 각각 dfs를 그냥 돌렸는데 시간초과도 나지 않고 풀렸다. 이미 풀렸기 때문에 여기서 시간을 더 줄이는 효율적인 방법은 생각해보지 않았다.혹시나 해서 입력 받을때 최소 높이, 최대 높이를 추가로 체크해서 풀었는데 어짜피 시간은 똑같이 나왔다. 별로 의미가 없는듯 차..

문제 링크 : https://boj.kr/1012 BOJ 11724 연결요소의 개수랑 매우 유사한 문제로 생각된다.인접한 배추들이 존재한다면 하나로 이어진 배추들에는 지렁이가 한마리씩만 필요하다.결국 연결요소 문제랑 동일하게 연결요소의 갯수를 세면 되는 문제다.visited를 따로 만들지 않고 dfs로 탐색이 가능한 위치면 true로 두었고 방문 불가능한 위치이거나 방문했다면 false로 두었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950// BOJ 1012 유기농 배추#include using namespace std; vector cbg;const int dx[4] = {1, -1..

문제 링크 : https://boj.kr/10451 그림과 같이 순열 사이클을 찾는 방법은 간단하다.그냥 dfs로 돌리면 된다. dfs를 몇번 시작했는지만 체크하면 된다.다음에 방문할 노드를 저장하는 것은 인접 리스트를 만드는 방법과 동일하고 방문했다면 0으로 설정하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243// BOJ 10451 순열 사이클#include using namespace std; vector permu; void dfs(int idx){ int next = permu[idx]; if(next != 0) { permu[idx] = 0; // 방문 표시 dfs(next); }} int main..

문제 링크 : https://boj.kr/11724 문제의 컨셉은 간단하다. 주어진 그래프에서 하나로 이어져 있는 연결 요소의 개수를 찾는 문제로 위 그림에서 하나로 이어져있는 연결 요소 수는 2개가 된다. 입력의 경우는 미리 인접 리스트를 만들어 간선을 입력 받는다. 그 이후 1부터 N까지 DFS를 돌려서 DFS가 끝나는 시점에 카운트를 하나 증가시켜 주면서 다음 시작 요소로 DFS를 돌리는 식으로 반복하면 답을 구할 수 있다. 스택으로 구현한 방법이 함수를 사용하여 재귀로 돌리는 것보다 시간이 덜 걸릴 줄 알았는데 함수로 재귀 돌리는 것이 의미 없는 수치이긴 하지만 더 빨랐다. (위 - 스택, 아래 - 재귀) 스택으로 구현한 방법 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..

문제 링크 : https://boj.kr/2178 지난번에 풀었던 BOJ 7576 토마토 문제보다 훨씬 쉬운 BFS 문제인듯 하다.토마토 문제에서 잡았던 대부분의 기본 개념을 그대로 가지고 풀었다.토마토 보다 이 문제를 더 먼저 풀었으면 좋았을걸.. 먼저 이 문제는 입력 자료형이 공백으로 구분지어져있지 않기 때문에 1. std::istringstream 를 split 하여 입력받기2. char형 그대로 입력 받는 방법3. 스트링 클래스의 getline(std::cin, input); 사용4. scanf("%1d", &input); 처럼 형식지정자로 1자리만 받도록 하기등등 다양한 방법을 활용하여 입력 받아야 한다. 이 외에도 getch나 gets 등등 아주 많다.scanf를 사용하는게 제일 편하긴 하지만..

문제 링크 : https://boj.kr/11399 A B C D 의 순서로 필요한 시간이 있다고 가정해보자1 - A2 - A + B3 - A + B + C4 - A + B + C + D TOTAL - 4*A + 3*B + 2*C + 1*D 로 식이 나오게 된다. 가장 큰 수를 적게 곱하고 작은 수를 많이 곱하는게 이득이 된다. 결국 모든 숫자를 오름차순으로 정렬해줘서 작은 숫자 부터 N - i 번씩 곱해나가는 방식으로 풀면 쉽게 풀린다. 1234567891011121314151617181920212223242526// BOJ 11399 ATM#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);..