자료구조 썸네일형 리스트형 [백준] 1436번 : 영화감독 숌 - C/C++ 문제 풀이 순서는 간단하다.1. 몇 번째 영화 시리즈인지 n 값 입력 받기2. 초기값 설정3. 종말의 수 구하기 1번과 2번 과정을 한 번에 수행하면 아래와 같다.int n;cin >> n;int num = 666;int cnt = 1; cnt 값의 초기값을 1로 설정한 이유는 다음과 같다.첫 번째 '종말의 숫자'는 666이기 때문에 하나를 이미 찾았다고 가정한다. n번째 종말의 수를 찾을 때까지 while 문을 돌려주자.while (cnt != n) { num++; ... }} n의 값을 증가시켜주는 이유는 숫자를 하나씩 키우면서 666이 포함된 수를 찾아야하기 때문이다.666이라는 수가 포함되어있는지의 여부를 판단하기 위해서는int → string 의 형변환 작업이 필요하다.stri.. 더보기 [백준] 10773번 : 제로 - C/C++ 문제 풀이 순서는 아래와 같다.1. 입력할 숫자의 개수 k 입력2. k개만큼의 수 입력 받기 (0을 입력했다면 최근에 입력한 수 지우기)3. 입력을 완료했다면 남아있는 수 출력하기 최근에 입력한 수를 지우는 방법은 stack을 사용하면 된다.스택은 LIFO의 형태이기 때문에 0을 push 했을 경우에,두 번 pop 해주면 된다. 그렇게 코드를 작성해보자.스택을 사용하기 위해서는 헤더를 추가해주어야 한다.#include 입력받을 개수 k를 입력 받았다고 가정하고,스택을 구현하자.stack st;for(int i=0;i> n; if(n == 0){ if(!st.empty()){ st.pop(); } } else { t.push(n); }} 스택을 이렇게 간단하게 구현할 수 있다!0을.. 더보기 [백준] 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 이렇게 되어버리면 공백을 포함해서.. 더보기 [백준] 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인 경우일 것이고,.. 더보기 [백준] 2493번 : 탑 - C/C++ 하루 종일 걸렸다.나는 너무 어렵게 풀었다. 어렵게 풀었다기 보다는 아직 이정도 난이도의 문제를 풀 정도가 아닌 것 같다.엄청난 검색과 엄청난 참고를 통해 완성한 나의 코드 분류 보고 풀지 말라고 했는데,,, 나는 또 보고 풀었다. 일단 풀이를 시작해보겠다. 자료구조 문제이고 스택을 이용하라고 했으니까그렇게 풀어보자. 탑의 개수와 높이 설정하기.int n;cin >> n;stack> s; pair가 무엇인지에 대해서는 이전 글에 설명했으니아래 링크를 달아두겠다.https://binaryroot.tistory.com/9 [백준] 10814번 : 나이순 정렬 - C/C++내가 생각한 문제 해결 순서는 아래와 같다. 1. 회원수 n 입력하기2. 회원의 나이와 이름 입력하기3. 나이순으로 출력하기 문제는 간단했.. 더보기 이전 1 2 다음 목록 더보기
