tony9402

이 글은 지속적으로 업데이트가 될 예정입니다. 알고리즘 공부를 제대로 해보려고 한다. 공부를 시작하기 전에 들어본 적 있는 자료구조 및 알고리즘을 나열해보려고 한다. 간단한 종류로 나눈다면 아래와 같다. 문자열 수학 트리 그래프 정렬 다이나믹 프로그래밍 네트워크 플로우 아래 Bar는 내가 아는 정도를 표시하는 것이다. 문자열 KMP 알고리즘 라빈카프 알고리즘 트라이(Trie) 아호코라식 접미사 배열(Suffix Array) Z 알고리즘 Hashing LCP Manacher 트리 트리 순회 이진 검색 트리 우선순위 큐 유니온 파인드 세그먼트 트리 펜윅 느리게 갱신되는 세그먼트 트리 머지소트 트리 세그먼트 트리 비츠 스플레이 Persistent Segment Tree LCA(최소 공통 조상) Heavy-Li..

문제 : 별 찍기 - 11 이번에는 재귀, memcpy, memset, 배열을 안쓰고 오로지 반복문와 if문(삼항 연산자 포함)으로만 짤 수 있다는 것을 보여주겠다.좀있다 나올 규칙은 비트 연산 이외에 수학적인 계산으로 발견한 것이 아닌 우연히 발견한 것이다. 먼저, 띄어쓰기의 개수를 파악해보자. 아주 작은 삼각형에서 별이 3개씩 찍히므로 높이는 n / 3이다. 아래 경우에는 n이 24일 때를 보는 것이므로 높이는 24 / 3인 8이 된다. 높이가 1일땐 띄어쓰기의 개수는 n - h(h는 높이)이다. 그 다음은 작은 삼각형이 찍히는 부분과 그 사이에서 띄어쓰기를 하는 규칙을 찾아야한다. 이를 찾으려고 하기엔 너무 어렵긴 하다. 2차원 표에서 0부터 8까지의 각각 & (AND) 연산 한 결과를 표에다가 작..

문제 : 별찍기 - 11 이전 포스트에 규칙을 찾아 분할정복(재귀)로 푸는 방법을 해설했었다.이번엔 반복문 + memcpy를 이용해서 풀이를 해보겠다. 아주 작은 케이스를 계속 찍듯이 반복하면 된다. 1. 아주 작은 케이스의 별을 먼저 찍는다. 2. 그 다음의 크기의 별을 만들기 위해서 규칙을 찾아 해당하는 위치에 copy and paste를 한다. 3. 그 다음의 크기의 별을 만들었다면 그 별을 복사한다. 4. 똑같은 규칙으로 3번에서 복사한 별을 찍어나간다. 이를 원하는 크기의 별을 찍을때까지 반복하면 완성이다. 이러한 규칙을 가지고 문제를 풀면 아래와 같이 된다. chogahui05님이 memcpy, memset을 이용해서 풀었다는 얘기를 듣고 한번 규칙을 찾아 소스를 만들어 보았다. 자세한 설명은..

문제 : 별찍기-11 문제 유형 : 분할 정복, 구현 별 찍는 규칙을 잘 찾아 별을 찍으면 되는 말로는 간단한 문제이다. 구현은 매우 간단하지만 삼각형의 규칙을 찾는게 어려웠다. 일단 예제 있는 걸로 규칙을 파악해보자. n이 24일때 별의 모양은 아래와 같다. 문제를 잘 읽어보니 n은 항상 (k는 10이하의 음이 아닌 정수) 인 수가 들어온다는 조건이 있다. 이를 보고 삼각형의 높이(세로)의 길이와 밑변(가로)의 길이를 세보았다. 그랬더니 세로은 24즉 이고 가로은 (k=3)이라는 것을 알게 되었다. (여기서 가로에 별 5개와 띄어쓰기를 하나로 묶은 것이다.) 이제 가로를 4등분 하고 세로를 2등분 해보자. 여기서 n=24일때와 닮은 프렉탈 모양 3개가 보일 것이다. 이를 박스로 구분해보자. 맨 위에 있..

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. 암호코드 - ●●●○..