tony9402

SCCC 스터디 4일차 1月 14日 오늘은 기초 자료구조에 대해 공부했다. 1. list STL에 있는 list을 이용하여 구현해봤다. list를 이용한 문제가 잘 안나온다고 하는데 그렇게 어려운것도 아니고 간단한 자료구조이기도 하고 혹시 나오면 당황해서 못짜는 것보단 아는 것이 좋아 list를 이용해 백준에 있는 문제를 풀었다. 2. Graph Graph를 인접행렬로 표현 할 수 있고, 인접리스트로 표현 가능하다. 각자의 장단점이 존재한다. 어느정도 작을땐 인접행렬을 이용해 문제를 풀어도 되고 좀 클땐 인접리스트가 효율적이다. 3. Tree 트리에 가장 큰 특징은 사이클이 없는 연결 그래프라는 점이다. 즉, Tree는 Graph의 일종이다. 또한 트리는 정점이 n개가 있으면 간선은 n - 1개가 있다...

C++ 환경에서 코딩을 하면 STL이라는 것을 사용할 수 있다. STL에는 queue가 기본적으로 만들어져있다. 또한 이 queue을 상황에 따라 편하게 선언을 할 수 있다.STL을 이용하여 n을 입력받고 1부터 n까지의 값을 queue에 넣고 queue에 있던 모든 값을 출력해보는 간단한 소스코드를 작성해보자. 12345678910111213141516171819202122232425#include#include using namespace std; queue q; int main(){ int n; cin >> n; //scanf("%d",&n); for (int i = 1; i

SCCC 스터디 3일차 정렬 - 힙 정렬 - 선택 정렬 - 삽입 정렬 - 버블 정렬 - 합병 정렬 - 쉘 정렬 - 퀵 정렬 - 카운팅 정렬 1. 힙 정렬 STL priority_queue를 이용하지 않고 힙 정렬 구현해보기 - 최대 힙 ●●◐○○ (만약 STL을 이용하면 난이도 ●○○○○) - 최소 힙 ●●◐○○ (만약 STL을 이용하면 난이도 ●○○○○) - 수 정렬하기2 ●●◐○○ (만약 STL을 이용하면 난이도 ●○○○○) 2. 삽입 정렬 - 수 정렬하기 ◐○○○○ - 수 정렬하기2 ●●●●● (수 정렬하기2에서는 삽입 정렬를 이용해서 절.대.로 맞았습니다!가 뜨지 못한다.) 3. 합병 정렬(merge sort) - 수 정렬하기2 ●●●○○ 4. 퀵 정렬 - 수 정렬하기2 ●●●○○ (퀵 정렬은 최..

SCCC 스터디 2일차 시간복잡도에 대해 간단히 이해하고 어떤 표기법을 쓰는지 알고 나머지 시간은 구현 time~ 1억번의 연산을 수행할 때 걸리는 시간을 약 1초가 걸린다고 생각하면 된다. 단순 연결 리스트 - 조회, 삽입, 삭제 - O(N) 정렬 - 선택, 버블, 삽입 - O() - 퀵정렬 - O() -> 평균은 O(NlogN) - 힙, 머지. etc - O(NlogN) 스택, 큐 - 삽입, 삭제 O(1) 이분 탐색 - 탐색 - O(NlogN) 힙 - 삽입, 삭제 O(logN) 1. 터널의 입구와 출구 - ●○○○○2. 도깨비말 - ●◐○○○3. 크로스워드 만들기 - ●○○○○4. 그림 비교 - ●◐○○○5. 지뢰 찾기 - ●○○○○6. 비밀번호 발음하기 - ●●○○○7. 고장난 시계 - ●○○○○8..

문제 : 1,2,3 더하기 6유형 : 다이나믹 프로그래밍 이 문제는 1,2,3 더하기 4, 5보단 조금 더 쉽고 재밌었던 문제였다.더하기 식이 대칭이 되도록 만들면 되는 문제이다. 이를 어떻게 풀지 고민하다가 다이나믹 프로그래밍이므로 재귀적으로, 또한 합이 대칭을 만족해야 한다는 요점을 잡고 다시 보니 바로 눈에 보였다. 어떤 수 x가 있는데 이를 어떻게 대칭적이고 재귀적으로 풀 수 있을까?바로 x에서 2, 4, 6을 빼고 반을 나눠 양쪽에 이어서 붙이면 된다.ex) x => 1 + (x-2) + 1, 2 + (x-4) + 2, 3 + (x-6) + 3 이렇게 빼면 된다. 근데 여기서 궁금증을 가지는 사람이 있을 수 있다.ex) 4를 1 + 1 + 1 + 1로 만들 수 있는데 이는 어떻게 만들어지지.....

문제 : 1,2,3 더하기 5문제 유형 : 다이나믹 프로그래밍 일단 정수 4인 경우, 1,2,3의 합으로 나타내는 방법이 왜 3개인지 알아보자. 처음엔 1,2,3의 합으로 나타낼 수 있는 모든 경우의 수를 구해보면 아래와 같다. 3 + 11 + 32 + 22 + 1 + 11 + 2 + 11 + 1 + 21 + 1 + 1 + 1 여기서 문제 조건에 만족하지 않은 것은 2 + 2와 1 + 1 + 1 + 1, 2 + 1 + 1, 1 + 1 + 2이다.이를 어떻게 풀까.......? 정수 n이 있다고 가정해보자. n은 아래와 같이 쓸 수 있을 것이다. 1. 3 + (n - 3)2. 2 + (n - 2)3. 1 + (n - 1) 1번에서 n - 3이 3이 아닌 1과 2로 식을 전개하면 된다.3 + 1 + (n -..

문제 : 1,2,3 더하기 4 문제 유형 : 다이나믹 프로그래밍 이 문제는 1,2,3 더하기로 표현하는 것들 중에서 더하기 순서를 바꿨을때랑 같은 것을 한 종류로 보는 문제이다. 4를 가지로 예를 들어보자. 4를 1,2,3더하기로 표현해보면 3+1 2+2 1+3 2+1+1 1+2+1 1+1+2 1+1+1+1 이렇게 7가지가 있는데 더하기 순서를 바꾸면 같아지는것을 묶어보자. 3+1 (1+3) 2+2 2+1+1 (1+2+1, 1+1+2) 1+1+1+1 이렇게 4가지가 있다. 이것을 어떻게 수식으로 표현할까? 1,2,3 더하기 시리즈 문제는 모두 다이나믹 프로그래밍으로 풀 수 있다. 이를 재귀적으로 생각해보면 점화식이 보인다. 한 종류로 만들 때, 여러가지 순서 중 비오름차순으로 짜면 된다. 4를 가지고 예..

알고리즘 분류 : 다이나믹 프로그래밍 문제 : 1,2,3 더하기 3 위 문제는 1, 2, 3 더하기 문제에서 n의 범위가 더 커졌고 모듈러 연산을 하면 되는 문제이다.따라서 이 문제는 여기에서 세운 점화식에다가 모듈러 연산만 추가 하면 된다. 1234567891011121314151617181920212223242526272829#include long long dp[1000001] = {0, 1, 2, 4 }; const long long mod = 1000000009; long long DP(int n){ if (n

알고리즘 분류 : 다이나믹 프로그래밍 문제 : 1,2,3 더하기 2 이 문제는 1,2,3 더하기 문제를 이용해서 풀었다. 먼저 4를 본다고 하면 DP[3] + DP[2] + DP[1]를 더한게 DP[4]의 값이다. 아래 그림을 보며 이해를 하자. 4는 3 + 1, 2 + 2, 1 + 3인 경우의 수를 알 수 있고 이를 사전 순으로 정렬하면 1 + 3, 2 + 2, 3 + 1이렇게 된다. 따라서 4를 간단한 규칙으로 정리하면 1부터 DP[4-1]까지는 1로, DP[4-1] + 1부터 DP[4-1] + DP[4-2] 까지는 2로, DP[4-1] + DP[4-2] + 1부터 DP[4-1] + DP[4-2] + DP[4-3] 까지는 3으로 채워진다. 이런 방식으로 계산을 하면 원하는 구간에서 값을 계속 vect..