tony9402

SCCC 14일차 스터디 MST/위상정렬 MST에는 크루스칼 알고리즘, 프림 알고리즘이 있다. 프림 알고리즘은 pq를 이용한 다익스트라와 거의 비슷하니 금방 이해를 할 것이다. 크루스칼 알고리즘은 disjoint-set 을 이용한다. 아직 못 푼 문제가 많다.... (스터디때 문제들이 조금 어려웠던 문제들이 많았다.) 1. 최소 스패닝 트리 - ●●○○○2. 네트워크 연결 - ●●○○○(1번을 풀었다면 ○○○○○ - toooooo easy)3. 음악 프로그램 - ●●◐○○4. 문제집 - ●●○○○5. 줄 세우기 - ●●○○○ (4번을 풀었다면 ○○○○○ - toooooo easy)

12일차에는 스터디가 아니라 컨테스트가 진행되었다. sccc 스터디 2月 11日에 13일차 최단거리로 스터디가 진행되었다. 최단거리에는 여러가지 알고리즘이 존재한다. 1. 다익스트라 => 맨 처음에 짰을때 queue로 짰지만 priority_queue로 짜도록 노력하자..2. 벨만-포드 => 음수간선이 있을때도 사용가능3. 플로이드 => n이 충분히 작을때 사용할 수 있다.4. SPFA 1. 최단경로 - ●●○○○2. 최소비용 구하기 - ●●○○○3. 거의 최단경로 - ●●●◐○4. 네트워크 복구 - ●●◐○○5. 케빈 베이컨의 6단계 법칙 - ●◐○○○6. 플로이드 - ●◐○○○7. 저울 - ●●◐○○8. 타임머신 - ●●◐○○9. 웜홀 - ●●◐○○10. 파티 - ●●○○○

sccc 스터디 11일차 1月 29日 DFS/BFS에 대해 스터디를 진행하였다. 넓이 우선 탐색 => BFS깊이 우선 탐색 => DFS최단 거리를 구할땐 DFS로 하지 말고 BFS로 하자.... 1. DFS와 BFS - ●○○○○2. 미로 탐색 - ●◐○○○3. 숨바꼭질 - ●●○○○4. 토마토 - ●●○○○5. 단지번호붙이기 - ●○○○○6. 유기농 배추 - ●○○○○7. 경로 찾기 - ●●◐○○8. 연결 요소의 개수 - ●●○○○9. 영역 구하기 - ●◐○○○10. 로또 - ●◐○○○11. 나이트의 이동 - ●◐○○○12. 말이 되고픈 원숭이 - ●◐○○○13. 집배원 한상덕 - 아직 안품14. 상범 빌딩 - ●●●○○15. 열쇠 - ●●●●○16. 벽 부수고 이동하기2 - ●●●◐○17. 레이저 통..

sccc 스터디 10일차 1月 28日 이날엔 이분탐색에 대해서 스터디를 진행했었다. 간단히 설명하자면 이분탐색은 찾을 범위의 양 끝점을 잡고 찾을려하는 값을 찾아가는 것이다. 단 여기서 이분탐색을 적용하기 위해서는 정렬이 되어있어야한다. 즉 단조증가나, 단조감소여야 적용가능하다. 이분탐색은 계속 반을 쪼개가면서 찾기 때문에 원하는 수를 찾는데 O(log N) 만큼 걸린다. 파라메트릭 서치라는 것도 있는데 이것은 이분탐색을 기반을 두면서 최적의 답을 찾아가는 것이다. 1. 수 찾기 - ●○○○○2. 숫자카드 - ●○○○○3. 나무자르기 - ●●◐○○4. 예산 - ●●◐○○5. 숫자카드2 - ●○○○○6. 공유기 설치 - ●●●○○7. 기타 레슨 - ●●●○○8. 나는야 포켓몬 마스터 이다솜 - ●●○○○

문제 : 돌 게임 3문제 유형 : 다이나믹 프로그래밍 이 문제는 숭실대 알고리즘 대회에서 비슷한 문제가 나왔던 문제랑 거의 똑같다. (그 문제에는 승리, 패배만 있는게 아니라 무승부까지 있다.) 하지만 문제 푸는건 거기서 거기다. 두명이 다 최선을 다하여 게임을 한다는 가정과 돌을 1개, 3개, 4개 중 하나를 가지고 갈 수 있다는 조건이 있으므로 이 조건에 맞게 한번 DP 테이블을 채워보자. 가로에 써져 있는 건 현재 돌이 몇개 남았는지 뜻하는것이고 세로줄에는 SK이가 할 차례, CY가 할 차례를 표현한것이다. 표를 채울때 1과 -1을 사용할 것이다. 1은 자신이 승리한다는 뜻이고 -1은 자신이 패배한다는 뜻으로 사용할 껏이다. (1과 0으로 해도 상관없다.)돌이 1개, 3개, 4개가 남았을땐 누가 시..

SCCC 스터디 9일차 1月 23日 오늘은 디피랑 그리디 문제들을 처음부터 끝까지 풀었다.디피랑 그리디는 역시 문제를 좀 풀어보면서 익히는게 답이긴 하지만.... 어렵다.. 1. 저울 - ●●◐○○ (아이디어 생각하는게 좀 어려웠다.)2. 포도주 시식 - ●●◐○○ 3. 한 줄로 서기 - ●●○○○ 4. 동전 2 - ●●○○○ 5. 타일 채우기 - ●●●◐○ 6. 잃어버린 괄호 - ●●●○○ 7. 이항 계수 2 - ●◐○○○ 8. 기타줄 - ●●●○○ 9. 크게 만들기 - ●●●◐○ 10. RGB거리 - ●◐○○○ 11. 제곱수의 합 - ●◐○○○ 12. Revenge of the Pancakes (Large) - ●●●○○13. 행렬 - ●●●◐○ 14. 문자열 - ●◐○○○15. 암호코드 - ●●●○..

SCCC 스터디 8일차 1月 22日 그리디도 어렵다..그리디는 Greedy로 탐욕 알고리즘이라 불린다. 현재 선택이 나중 선택에 영향을 미치지 않게 고르는 것이다.디피랑 그리디에 대한 자세한 개념은 라이님 블로그, 나동빈님의 블로그에 잘 설명 되어있으니 거기서 개념을 보는게 좋다. (난 여기에 쓰는건 그냥 간단히 일기장처럼 쓰는 것이여서 개념보단 문제 리스트를 올리는 것이다.) 그리디 알고리즘의 종류가 있다. (여기서 내가 아는건 거.....의 없다....) 1. Fractional Knapsack Problem (=> 거스름돈 문제)2. 시간표 배정3. 수학적 성질이 최적해를 보장하는 경우4. Huffman Code5. 다익스트라6. MST(Kruskal, Prim)7. 최대 유량 1. 동전 0 - ●..

SCCC 스터디 7일차 1月 21日 DP 어려워;;;;;;;; 1. DP1 DP는 다이나믹 프로그래밍의 약자로 한국말로 하면 동적계획법이라 한다. (DP가 부르기 좋은 듯) 처음에 디피가 뭔지도 모르겠고 그냥 "어렵다"라는 말만 들어서 접근하기가 매우 힘들었다. 근데 맨 처음 풀 때 삽질과 다른 사람이 푼 방식을 보고 대충 어떤 느낌인지 깨닫기 시작했다. - 중복계산을 피해 한번 계산 했던 것은 저장해서 처리속도를 높인다. - 큰 문제를 해결하기 위해 작은 문제를 이용(이전 작업을 이용)하여 큰 문제를 해결 - 점화식을 이용해 문제 해결 첫 번째에 쓴 건 많이 들어봤을 것이다. (메모이제이션, memoization)두 번째는 분할정복과 비슷하다는 것을 느낄 수 있다.세 번째에는 점화식을 세워 풀면 된다는..

문제 : 1로 만들기문제 유형 : 다이나믹 프로그래밍 이 문제의 핵심은 입력 받은 수를 최소 횟수로 1로 만드는 것이다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. X에서 1을 뺸다. 위 세가지를 이용해서 1로 만들어야 하는데 이를 어떻게 할까? 다이나믹 프로그래밍 문제를 풀 땐 너무 복잡하게 생각하면 오히려 안풀린다. 다이나믹 프로그래밍 문제를 풀기 위한 방법은 탑다운 방식과 바텀업 방식이 있다. 나도 공부하는 입장이니 두 가지 방법으로 설명하겠다. 1. 탑다운(Top-down) 방식 현재 수를 X라 하자. X가 3으로 나눠떨어진다면 X/3을 만드는 횟수는 X 만든 횟수에 한번더 연산을 한 것이기 때문에 X를 만든 횟수에 +1을 해주면 된다.이..

문제 : 파도반 수열 문제 유형 : 다이나믹 프로그래밍 이 문제는 규칙을 찾기만 하면 되는 문제이다. 난 두가지 점화식으로 풀었다. 1. 점화식1 일단 가장 먼저 풀었던 방식을 설명하자면, 소용돌이처럼 이어지는 수를 한 줄로 써보았다. 1 1 1 2 2 3 4 5 7 9 12 ... 이것을 보고 규칙이 바로 보였다. 지금 현재 위치에서 왼쪽으로 2칸 떨어진 것과 같은 방향으로 3칸 떨어진 것의 합이 현재 위치의 값과 같다는 점화식을 발견했다. 이를 식으로 쓰자면 아래와 같다. 이 식을 가지고 초기값만 잘 넣어주면 쉽게 맞추는 문제이다. 또한 n이 커지면 int형의 범위가 벗어나니 맞왜틀 했던 사람들은 int를 long long으로 바꿔보기 바란다. - 소스코드 123456789101112131415161..