tony9402

백준 11657 타임머신 SPFA 공부중.... 벨만 포드랑 비슷하면서 살짝 다른 알고리즘저번에 디피로 풀면 쉽게 풀리는 문제를 그냥 대충 BFS로 풀었는데 어떤 갓분이 그거 SPFA라고 하셔서 이번에 한번 공부해봄 그땐 음수가 없었기 때문에 사이클을 체크 하는 부분이 없어도 되지만 이 문젠 음수가 존재하여 음수 사이클 존재여부를 체크 해야함 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879#include#include#include#include using namespace std; qu..

백준 1504 특정한 최단 경로 우선순위 큐를 이용한 다익스트라 공부중.....(소스가 좀 드러울 수도 있음)(지금은 소스만 올리고 나중에 정리해서 수정할 예정) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include#include#include#include using namespace std; const long long INF = 98765432; vector map;priority_queue pq;vector ans;int v, e; long long Daijk(int start, int e..

백준 1753 최단경로 처음에 짤땐 모든 간선을 넣을려 하지 않고 중복된 간선이 있을 수 있어서 최소비용 간선으로 갱신을 하는 소스를 짰더니 0.7~0.9초까지 나왔다. 이 갱신하는 부분을 지우고 제출해보니깐 시간이 0.2초까지 줄어들었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include#include#include#include#include using namespace std; const int INF = 0x3f3f3f3f; vector map;vector visit;vector ans;priority_queue pq; ..

백준 1916 최소비용 구하기 소스 코드 메모(해설은 아직) - 우선순위 큐를 이용한 다익스트라 공부중 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include#include#include#include#include const int INF = 0x3f3f3f3f; using namespace std; vector map;vector visit;priority_queue pq;vector money; int main(){ ios::sync_with_stdio(false); cin.tie(0)..

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

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

백준 7569 토마토(3차원) 이 문제는 토마토(2차원)이랑 높이가 생겼다는 것 빼곤 똑같다. 2차원에서 위, 아래(높이 방향)이 추가 되었으므로 체크해야하는 위치가 2가지가 늘었다. 하지만 푸는 방식은 토마토(2차원)이랑 같다. (토마토(2차원) 풀이 보러가기) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include#include using namespace std; queue q;int map[101][101][101] = { 0 };bool visit[101][101][101] = ..

백준 7576 토마토 이 문제는 익은 토마토가 주변 익지 않은 토마토를 익게 만든다. 박스 안에 토마토의 정보를 받으면서 익은 토마토의 위치를 큐에 넣고 큐 사이즈만큼 돌면서 큐의 크기가 0이 될 때까지 돌리면 된다.이때까지 포스트를 올린 문제는 대부분 두 가지 유형으로 볼 수 있다. 이 문제에서 우리가 중심적으로 봐야하는 익은 토마토나 불이나 불! 문제에서 우리가 봐야하는 불이랑 사람의 위치를 알아야 하고 BFS를 돌리면서 주변으로 퍼지게 하는 느낌으로 짜면 된다.이러한 문제와 다르게 단지번호붙이기, 유기농 배추와 같은 문제는 한 좌표에서 주변으로 퍼져나가 넓이를 계산하고 다른 좌표(방문하지 않았던 좌표)에서 또 퍼져나가면서 넓이를 구하는 문제가 있다.하지만 두 가지 유형엔 공통점이 있다. 바로 한 중..

백준 4179 불! 이 문제는 불이랑 거의 같은 문제라고 볼 수 있다.(이 문제를 풀면서 다시 처음부터 짰기 때문에 풀이는 살짝 느낌이 다를 것이다. 불이랑 다른건 상근(@)이가 아니라 지훈(J)이로 바뀌었고 불(*)은 불(F)로 바뀌었다. 풀이는 이전 포스트에서 간단히 설명을 올렸으니 저 곳에서 한번 보면 될 것이다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071#include#include#include#include using namespace std; queue q;queue fire;char vmap[10..

백준 5427 불 이 문제는 상근(@)이가 안전하게 맵 밖으로 나가면 된다. 문제를 보면 불(*)이 붙으려는 칸으로 이동할 수 없다고 한다. 이를 알고리즘으로 해결하기 위해서는 불부터 이동시키고 그다음 상근이를 이동시키면 된다. 일단 먼저 맵의 정보를 읽으면서 불의 위치와 상근이의 위치를 각각 큐에 넣는다. 상근이의 위치가 들어 있는 큐의 크기가 0일 때까지 불을 한칸씩 이동시키고 상근이의 위치를 한 칸씩 이동시키면 된다. 이를 반복하다가 상근이가 맵 밖으로 나간다면 상근이가 이동한 횟수를 출력하면 되고 상근이의 위치가 담긴 큐의 크기가 0일 때까지 반복하는데 상근이가 맵 밖으로 못나갔으면 IMPOSSIBLE을 출력하면 된다. 1234567891011121314151617181920212223242526..