tony9402

SCCC 스터디 5일차 1月 16日 (수학 어렵다.........................) 1. 수학1 에라토스테네스의 체 - N 이하의 소수를 빠르게 찾는 알고리즘이다. 소수의 배수를 없애는 방식으로 진행한다. 자세한 내용은 여기에서 참고하면 될 것이다. 이 방법을 이용하면 시간복잡도는 O(n log log n)이다. 유클리드 호제법 - 최대공약수(GCD)를 빠르게 구하는 알고리즘이다.나머지 연산을 이용해서 빨리 구할 수 있는데 이에 대한 자세한 내용은 여기에서 참고하면 될 것이다. 에라토스테네스의 체 - 소수인지 판별하는 방식은 거의 동일하지만 소스코드를 작성할때 살짝 다른게 있다. 다른 곳에서 계산과정 중 오버플로우를 방지하기 위해서 사용한다고 들었다. - 에라토스테네스 1. 에라토스테네스의 ..

SCCC 스터디 5일차 1月 15日 오늘은 미세먼지로 인해 전날 스터디 모임이 취소가 됬다. 그래도 배울 내용은 적어 홈스터디로 진행됬다. 1. 분할정복 분할정복은 Divide and Conquer로 문제를 같은 유형의 여러 작은 문제들로 나눈 뒤, 그 작은 문제들의 답을 이용해서 문제를 해결하는 방식을 말한다. 분할정복을 이용하면 시간 복잡도를 줄일 수 있다. 예를 들어, 1부터 100까지 더하는 것을 공식을 이용하지 않고 더한다면 아주 간단하게 O(n)로 더할수는 있다. 하지만 분할정복을 이용하면 O(log n)으로 더 줄일 수 있다. 1 + 2 + 3 + ... + 51 + 52 + 53 + ... + 99 + 100 이를 한번 Divide(분할)을 해보자. 1 + 2 + 3 + ... + 50 +..

성능 분석과 측정 프로그램의 평가 기준 - 우리가 원하는 작업을 하는가? - 원래 작업의 명세에 부합해서 정확히 작동하는가? - 문서화가 되어 있는가? - 논리적 작업 단위를 수행하는 기준으로 함수가 생성되었는가? - 코드가 읽기 쉬운가? 성능 평가(performance evaluation) - 성능 분석(performance analysis) => 사전 예측 - 성능 측정(performance measurement) => 이후 검사 공간 복잡도 공간복잡도 - 프로그램을 실행 시켜 완료하는 데 필요한 메모리 양 - 고정 부분 => 보통 명령어 공간, 단순 변수, 집합체, 상수를 위한 공간 - 가변 부분 => 특정 문제의 인스턴스에 따라 크기가 달라지는 변수, 순환 스택 공간 - 프로그램 P의 공간 유고 ..

시스템 생명 주기(System Life Cycle) 요구사항 - 프로젝트들의 목적을 정의한 명세들의 집합 - 입력과 출력에 관한 정보를 기술 분석 - 문제들을 다룰 수 있는 작은 단위들로 나눔 설계 - 추상 데이터 타입(abstract data type) 생성 - 알고리즘 명세와 설계 기법 고려 정제와 코딩 - 데이터 객체에 대한 표현 선택 - 수행되는 연산에 대한 알고리즘 작성 검증 - 정확성 증명 : 수학적 기법들을 이용해서 증명 - 테스트 : 프로그램의 정확한 수행 검증, 프로그램의 성능 검사 오류 제거 - 독립적 단위로 테스트 후 전체 시스템으로 통합 객체 지향 설계 구조적 프로그래밍 설계와의 비교 - 유사점 : 분할 - 정복 기법 : 복잡한 문제를 여러개의 단순한 부분 작업으로 나누어 각각을 개..

백준 2178 미로탐색 이 문제는 (1,1)부터 시작해 (N,M)로 가는 길 중 가장 짧게 갈 수 있는 경로를 찾는 것이다. 최단 경로를 구하는 문제는 대부분 BFS로 푸는 문제이다. 따라서 이 문제도 BFS로 푸는 문제이다. BFS는 queue를 이용하는데 queue에서 pop할때 도착 지점의 좌표가 나올때까지 하면 된다.문제에 길은 무조건 있다고 하니깐 그냥 없을 경우를 생각하지 않고 계속 push하고 pop을 하면 된다. 1. pair가 있다는 걸 몰랐을 때 짠 소스(queue에 대해서 독학 했을 때...) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585..

오랜만에 에듀코포가 있어 해보게 되었다. 너무 오랜만이라 그런지 문제를 해석해야하는데 해석도 안되고 문제를 읽기도 싫어서 대충 예제를 보고 풀려고 했지만 A번은 1시간 동안 안 풀려서 B -> A -> C로 풀었더니 1시간이 훌쩍 지나가버렸다. A번은 두 문자의 차이가 2 또는 0(같은것)인것을 보면 되는 단순한 문제였는데 문제를 안읽어 제출을 많이 했다. B번은 대충 배열 쓰면 되겠지하고 봤더니 n의 범위가 최대 10^9여서 멍 때리다가 규칙을 찾고 대충 제출 했지만 케이스 n == 2일때만 틀려서 2일땐 그냥 노가다로 if문 떡칠을 하였다. C번은 처음에 O(n^2)로 풀었는데 TLE가 떠서 O(n) 풀이가 있을꺼 같아 살짝 그리디하게 짜봤더니 AC가 떳다. 시간 복잡도 A번 -> O(N)B번 -> ..

백준 2606 바이러스 이 문제는 (매우..?) 쉬운 문제이다. 알고리즘 분류에는 플로이드 와샬로 되어있는데 이건 단순히 DFS로 풀린다.입력 받는 데이터를 이용해 인접리스트를 만들고 컴퓨터 1번에서 DFS를 한 번 돌리면 답이 나온다. 1234567891011121314151617181920212223242526272829303132333435363738#include#include using namespace std; vector map;bool visit[101] = { false };int computer_num, ans = 0; void dfs(int x){ ans++; visit[x] = true; for (int k = 0; k

백준 10026 적록색약 이 문제는 DFS 또는 BFS로 풀 수 있는 문제지만 둘 중에 하나로 두 번 돌려야 되는 문제이다. (두가지 풀이로 쓰기 귀찮아서 BFS 풀이만 올리겠다.) 먼저 BFS로 한 바퀴 돌릴 때 G인 곳을 R로 바꾸면서(R을 G로 바꿔도 상관없다) 색상에 의해 몇 구역으로 나뉘는지 체크를 하고 또 다시 BFS로 한 바퀴 돌리면 풀리는 단순한 문제이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include#include#include u..

백준 1012번 유기농 배추 이 문제는 백준 2667번 단지번호붙이기와 거의 같은 문제이다.단지번호붙이기와 다른점은 단지마다 넓이를 구해야하고, 유기농 배추는 단지의 갯수만 구하면 되는 문제이다. 1. BFS를 이용한 풀이 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include#include using namespace std; queue q;int dx[] = { -1,1,0,0 };int dy[] = { 0,0,-1,1 };int map[55][55] = { 0 }; int main(){ int T; int m, n, k; int x, y; int ans; ..

백준 2667번 단지번호 붙이기 이 문제는 BFS로 풀어도 되고 DFS로 풀어도 되는 문제이다. 아는 사람도 있을 것이고 모르는 사람도 있을 수도 있으니 입력부분에서 하나 집고 가자면 예제 입력 부분을 보면 0110100 이런식으로 숫자가 붙어서 들어오는데 scanf를 잘 사용하면 숫자 한개씩 입력 받게 가능하다. (어떤 사람은 이걸 몰라 문자열로 입력 받아 처리하는 경우가 있었다. 이 문제에선 큰 상관이 없긴 하지만 다른 문제에서 쓰일 때가 있을 것이다.) 1234567for(int i=0;i