본문 바로가기

분류 전체보기

백준 2252 줄 세우기 <위상 정렬> https://www.acmicpc.net/problem/2252 이 문제는 위상 정렬로 푸는 문제로, STACK을 이용한 DFS 알고리즘을 통해 풀 수 있고, queue를 이용하여 degree 1차원 배열을 이용해서도 풀 수 있다. 위상 정렬에 대한 개념은, http://jason9319.tistory.com/93 > n >> m; student.resize(n + 1); for (int i = 0; i > front >> back; student[back].push_back(front); // indgree 증가 ++dg[front]; } solution(); return 0; } 2. DFS를 이용한 풀이 #include #include #include #define SIZE 32000 using ..
void 포인터 void 포인터는 함수로 어떤 데이터가 들어올 지 모르는 상황에서 사용한다. void func(void* pData) { char*pChangeData = (char*)pData; int temp = 'j'; for(int i=0; i
BOJ 백준 1753 최단경로 https://www.acmicpc.net/problem/1753 이 문제의 입력은 총 정점의 수와 간선의 수, 시작할 정점과 각 간선들에 대한 정보가 주어진다. 간선의 방향이 존재하며, 시작 정점으로부터 다른 모든 정점들에 대해 최단 경로를 출력해주어야 한다. 다익스트라 문제는 종종 풀었으나, 우선순위 큐를 이용하여 푼 적은 거의 없었다. 이 문제도 보자마자 다익스트라를 사용했고, 결과는 시간 초과였다. 메모리 제한 : 256MB시간 제한 : 1초 우선 정점의 수가 최대 20000개이므로 일반 배열, 즉 20000 * 20000의 int형 배열로는 메모리 초과가 난다. 그래서 vector을 이용하여, 간선의 정보가 주어지면 push해주는 방법을 이용했다. 난 단순히 메모리초과만 생각하고 벡터로 한 뒤 ..
BOJ 백준 2644 촌수계산 https://www.acmicpc.net/problem/2644 말 그대로 촌수 계산을 해 주는 문제이다. 입력값으로는 1. 사람의 수2. 촌수를 계산하려는 두 사람3. 부모-자식 관계의 수 4. 부모-자식 관계 이렇게 들어온다. 문제에서 원하는 것은 2번에 입력된 두 사람의 촌수를 출력해주는 것이다. 촌수를 계산하려는 두 사람의 공통되면서 최소인 부모노드를 찾고 찾아낸 부모노드로부터 촌수를 계산해주면 되는, 어렵지 않은 문제이다. vector을 이용해서 두 사람의 부모노드들을 찾아 저장해주고, 비교해주면서 최소 부모 노드를 찾아내는 형태로 풀었으나, 사실 추가 배열 없이 parent[]라는 배열 하나로 문제 풀이가 가능하다. #include #include #define SIZE 101 using n..
BOJ 백준 7569 토마토 https://www.acmicpc.net/problem/7569 이 문제는 한 토마토가 익은 상태라면, 다음 날에는 그 토마토의 앞, 뒤, 왼쪽, 오른쪽, 위, 아래의 토마토가 익게 되는데, 이 때 상자에 있는 모든 토마토가 익는 데에 최소 몇 일이 걸리는 지 계산해주어 출력해주는 문제이다. 모든 토마토를 익게 할 수 없을 시에는 -1을 출력해주고, 처음부터 모든 토마토가 익어있는 경우엔 0을 출력해주면 된다. 하나 하나가 자신의 전후좌우를 전염시켜나가는 문제들과 유사한데, 조금 다른 점은 한 층의 배열이 아닌 여러 층으로 이루어져 상, 하까지 전염시켜주어야 하는 것이다. 3차원 배열을 자주 사용해보진 않았지만, 예를들어 2 x 3 배열이 2개 있다는 것은 2 x 2 x 3으로 생각하면 되므로 int ..
new, delete * C의 malloc과 free의 C++ 버전이다. C에서int *n = (int*)malloc(sizeof(int));free(n); 을 통해 동적할당 및 해제를 했다면, C++에서는 int *n = new int;delete n; 배열의 경우, int *n = new int[array_size];delete[] n; 을 통해 동적 할당 및 해제를 해줄 수 있다. new의 경우, 메모리 할당 실패 시 NULL 포인터를 반환하기 때문에 int *n = new int[4]; if(!n)을 통해 메모리 할당 실패 예외 처리를 해줄 수 있다. 프로젝트의 규모가 크고, 동적 할당이 매우 많은 경우 new의 성공 여부를 계속 검사하는 코드는 성능을 저하시킨다. 따라서 debug 파일을 따로 두어 서비스를 실행하기..
Reference * 이름을 지니는 변수에 대해, 또 다른 이름을 지어주는 것이다. int a = 4 라고 했을 때, 정수 4가 저장되어 있는 4byte 메모리에는 'a'라는 이름이 붙여진다. 여기서, int &b = a; 라고 했을 때, a라는 이름의 메모리 공간에, 또 다른 이름 b가 생기는 것이다. 따라서 이 후에 b = 2 처럼 값의 변경을 시도하게 되면, a의 값이 2로 변경된다. 주의 사항) 1. 반드시 선언과 동시에 초기화를 해 주어야 한다. int &b = a; (o)int &b; b = a (x) 2. int & 와 int 는 생성 시 방법만 다를 뿐 생성된 후에는 완전히 같다. 이 뜻은, 반환형을 int로 해주어도 무방하다는 것이다. 3. 지역변수, 동적할당된 변수를 레퍼런스로 리턴하는 것은 위험하다. ..
inline - 컴파일러에 의해 처리되고, 이는 컴파일러에게 최적화 기회를 제공해 준다. - 매크로의 장점을 가지며 함수 이름 앞에 inline 키워드만 붙여주면 된다. inline은 함수 본문의 복사본을 함수가 호출되는 각 위치에 삽입하도록 컴파일러에게 지시하는 지정자이다. 그러나 컴파일러가 비용, 이익 분석 시에 수익성이 없다면 수행하지 않을 수 있다. 비용, 이익 분석을 재정의하고 프로그래머의 판단에 맡기는, 즉 inline을 강제로 사용하게 하는 _forceinline 키워드도 있지만 이를 무분별하게 사용할 시 코드가 더 커져 성능이 크게 향상되지 않거나, 실행 파일의 페이징 증가와 같은 이유로 성능이 손실될 수 있다. inline int max(int a, int b){ if(a > b) return a; ..