본문 바로가기
728x90

Algorithm

[백준] 13023번 : ABCDE - C/C++ 문제에서 말하는 친구 관계에 대해 다시 살펴보자.A는 B와 친구다.B는 C와 친구다.C는 D와 친구다.D는 E와 친구다.간단하지만 문제에서 말하고 있는 문장을 도식화하면 위와 같다. 사람의 수를 node라고 볼 수 있고, 친구 관계의 수는 edge라고 볼 수 있다.각각 2,000이 MAX 임을 문제에서 이야기하고 있다.그래프를 보고 위의 그림과 같은 관계가 있는지 파악하는 문제이다. 예제 입력4를 그림으로 그려서 확인해 보자.그림은 이렇게 그릴 수가 있다.이제 친구 관계가 위에서 본 것과 같이 일자로 된 것이 있는지 확인해보자.0번 노드에서 출발하여 2번 노드까지 도착하는 것을 도식화하면 아래와 같다.ABCDE 순서로 일자로 나열되기 때문에 해당 예시는 1을 출력하게 되는 것이다. 13023번은 아래와 .. 더보기
[백준] 16953번 : A → B - C/C++ 문제를 보고 A → B 이렇게 가는건 너무 경우의 수가 많지 않은가?라는 생각을 했다.하지만 반대로 B → A 의 수는 연산의 횟수가 적을 것이라고 생각할 수 있다. 그러니, 우리는 위와 같은 아이디어로 문제를 풀어나갈 수 있다. B → A 를 생각해보자.짝수라면 2로 나누기끝자리가 1이라면 1을 제외시키기1번과 2번에 속하지 않는다면 -1 출력1번과 2번을 코드로 바꾸면 아래처럼 작성할 수 있다.더 깔끔한 코드가 있을 수 있겠지만, 필자는 이렇게까지가 최선이다.while(a  b가 짝수라면 2로 나누기. (가능한 연산이 곱하기 2, 맨 끝자리에 1 추가하기 뿐이니..)if(b % 10 == 1) 이 부분이 끝자리가 1일 때 제거하는 방법. (왜 끝자리가 1이냐면, 1만 추가할 수 있으니까.) 이렇게 핵.. 더보기
[백준] 11719번 : 그대로 출력하기 2 - C/C++ 문제가 간단하다.설명도 엄청 간결하다. 이 문제를 해결하기 위해서 쓰인 개념은getline()이다. getline() 함수를 사용하기 위해서는 string 라이브러리를 사용해야 한다.공백의 문자열이 주어질 수도 있어서 while 문의 조건식으로 getline() 함수를 사용하자.string str;while(getline(cin,str)){ cout  이렇게 코드를 작성하면 된다.근데 입력이 없다면 종료가 되어야하는데,내가 작성한 코드는 control(^)+c 를 눌러야 종료가 된다.이런식으로 작성해서 제출한 코드가 수두룩빽빽인데,다 맞았다고 하니까 이번에도 스리슬쩍.. 내가 처음에 썼던 getline() 함수는 아래와 같다.getline(cin, str);cout 이렇게 되어버리면 공백을 포함해서.. 더보기
[백준] 2839번 : 설탕 배달 - C/C++ 문제 풀이 순서는 다음과 같다.1. n 입력 받기2. 합리적으로 무게 나누기 필자는 말을 잘 못하기 때문에.. 이정도로 정리하겠다. 최소 개수의 설탕 봉지가 필요한 것이기 때문에3킬로그램 짜리와 5킬로그램 짜리 중에서 우리는 "5"를 적극 활용하도록 하자. 만약 입력한 수 n이 15라면, 3킬로그램 짜리를 5개, 5킬로그램 0개 가 필요하므로 총 5개가 필요하다.하지만 5킬로그램만 사용하게 된다면 3킬로그램 짜리 0개, 5킬로그램 3개가 필요하다.그러니 5킬로그램을 필터링에 걸리도록 작성해주자. if(n%5==0){ cnt += n/5; cout  그럼 3킬로그램짜리는 어떻게 처리할까?5로 나누어 떨어지지 않을 때 3씩 빼주면서 처리해주면 된다.n -= 3;cnt++; 우리는 설탕 봉지의 개수를 출력.. 더보기
[백준] 1292번 : 쉽게 푸는 문제 - C/C++ 문제 자체는 특정 규칙을 따르는 수열을 생성한 뒤, 주어진 구간 합을 구하는 문제이다.1,2,2,3,3,3,4,4,4,4,5,5,...i라는 수가 i번 반복된다는 규칙을 가진다. A,B 입력받고, 그에 해당하는 구간합 구하기구간합 [a,b]는 sum += ary[i] 로 쉽게 구할 수 있다.for(int i = a; i  문제에서 제약조건을  정수 A, B(1 ≤ A ≤ B ≤ 1,000) 이렇게 걸어두었기 때문에const로 NMAX를 선언하자.const int NMAX = 1001;1000으로 안 하고 왜 1001로 하나요?--> 상관은 없다. (반복문 돌릴때 등호 쓰기 싫어서) k는 현재 배열의 인덱스이다.1로 초기화했었다.for(int i = 0; i 1000){ break; .. 더보기
[백준] 11660번 : 구간 합 구하기 5 - C/C++ 지난번에 풀었던 문제와 비슷하다.누적합(prefix sum)을 이용하자. 입력 받은 2차원 배열을 저장할 공간과 누적합을 저장할 dp 테이블을 미리 선언해주자.int sum[1025][1025], dp[1025][1025]; N과 M을 입력 받았다면 dp를 처리하자.for(int i=1; i> sum[i][j]; dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + sum[i][j]; }} 왜 dp를 저렇게 처리하나요?https://binaryroot.tistory.com/17 [자료구조] 구간 합구간 합은 합 배열이라는 것을 이용하여 시간 복잡도를 줄이는 알고리즘이다.코딩 테스트에서는 사용 빈도가 높다고 한다. 핵심 이론구간 합 알고리즘을 활용하.. 더보기
[백준] 11659번 : 구간 합 구하기 4 - C/C++ 문제 풀이 순서는 아래와 같다.1. 데이터의 개수 N과 질의 개수 M 입력2. 구간 합을 구할 대상 배열 입력3. 구간 i,j 입력4. 출력 이전 글에 구간 합에 대한 내용을 정리했으니참고하길 바란다.https://binaryroot.tistory.com/17 [자료구조] 구간 합구간 합은 합 배열이라는 것을 이용하여 시간 복잡도를 줄이는 알고리즘이다.코딩 테스트에서는 사용 빈도가 높다고 한다. 핵심 이론구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한binaryroot.tistory.com 글을 확인했다면, 풀이를 시작해보자.  N과 M 입력int n,m;cin >> n >> m; 배열은 100000를 넘을 수 없으니const로 미리 선언해주기const int NMAX = 100020;int a.. 더보기
[자료구조] 구간 합 구간 합은 합 배열이라는 것을 이용하여 시간 복잡도를 줄이는 알고리즘이다.코딩 테스트에서는 사용 빈도가 높다고 한다. 핵심 이론구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다.배열 A가 있을 대 합 배열 S는 아래와 같이 정의할 수 있다.S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]    // A[0]부터 A[i]까지의 합 합 배열은 기존의 배열을 전처리한 배열이다.합 배열을 미리 구해 놓으면 일정 범위의 합을 구하는 시간 복잡도가 줄어든다. 어떻게 줄어드나요?--> O(N)에서 O(1)이라는 선형 시간으로 줄어들게 됩니다 :) A[i]부터 A[j]까지의 배열 합을 합 배열 없이 구하는 경우,최악의 경우를 생각해보자.i가 0이고 j가 N인 경우일 것이고,.. 더보기
728x90

티스토리툴바