tony9402

성능 분석과 측정 프로그램의 평가 기준 - 우리가 원하는 작업을 하는가? - 원래 작업의 명세에 부합해서 정확히 작동하는가? - 문서화가 되어 있는가? - 논리적 작업 단위를 수행하는 기준으로 함수가 생성되었는가? - 코드가 읽기 쉬운가? 성능 평가(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..

백준 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

다음 글 부터는 백준 DFS/BFS 관련 문제를 풀이 하는 글을 올릴 예정이다. 일단 백준에 있는 문제들 중에서 DFS/BFS 문제를 나열해보자 boj.kr/1260 - DFS와 BFSboj.kr/2178 - 미로 탐색boj.kr/7576 - 토마토(2차원)boj.kr/7569 - 토마토(3차원)boj.kr/2667 - 단지번호붙이기boj.kr/1012 - 유기농 배추boj.kr/2583 - 영역 구하기boj.kr/2468 - 안전 영역boj.kr/14502 - 연구소boj.kr/2589 - 보물섬boj.kr/10026 - 적록색약boj.kr/3055 - 탈출boj.kr/2206 - 벽 부수고 이동하기boj.kr/14442 - 벽 부수고 이동하기 2boj.kr/1600 - 말이 되고픈 원숭이boj.kr/..