본문 바로가기

분류 전체보기

 (694)
git 명령어 정리 [1. 개요] git 사용 시, 자주 사용하지는 않지만 간혹 필요할 수 있는 명령어 정리 [2. 예제] --recurse-submodules git clone --recurse-submodules https://github.com/valhalla/valhalla myproject 어떤 project 를 작업 할 때, 해당 project 는 다른 git repository 를 참조해서 구현 할 수 있다. 이 때, 의존성이 있는 git repository 내 모든 파일을 자신의 project 에 전부 저장 한후, git 에 올리는 것이 아니라 url 형태로, (url 링크 만) git 에 올릴 수 있는데, 이 때, 자신의 repository 를 clone 할 때, 의존성이 있는 다른 repository 까지..
go build 옵션 [1. 개요] go 로 코드 작성 후, 컴파일 시 유용한 옵션 정리 [2. 예제] trimpath go build --trimpath go 언어에서 panic() 호출 시, 예외가 발생했을 때, stack trace, source file name, line number 등을 출력해주는데, source file name 이 compile 한 환경의 절대 경로로 출력된다. 이 때, --trimpath 를 사용하면, 절대 경로 대신, source file 이름만 출력된다. # 정확히는 좀 다른데, 쉽게 생각하면 위와 같다.
컴파일 링커 옵션 [1. 개요] g++ 로 컴파일 시, 링킹 시 유용한 옵션 정리 [2.1 예제] 스택 사이즈 변경 g++ -Wl,--stack,1677216 test.cpp 함수 호출 시, 이 함수 내 지역에 선언한 buf 의 크기가 꽤 큰 경우, 함수 호출 시, 바로 segmentation fault 가 발생할 수 있다. 함수 호출을 위해, 컴파일 시, 일정 크기의 스택에 모든 지역 변수를 저장 할 수 있어야 하는데, buf 크기가 이 크기를 벗어나서 문제가 된 것이다. 이 경우 디폴트 스택 크기를 꽤 크게 잡아주면 runtime 오류를 해결 할 수 있다. [2.2 예제] 외부 라이브러리 링킹 g++ main.cpp -lrdkafka++ -L"./" rdkafka 를 사용하는 c++ 코드 컴파일 시, rdfkafka ..
위상정렬. [2056] [1. 문제 설명] https://www.acmicpc.net/problem/2056 [2. 풀이 접근] 일반적인 위상 정렬 풀이로 접근한다. 동시에 처리가능한 작업들이 있으므로, bfs 를 응용하여 처리한다. dfs 로는 "동시에 처리 가능한 작업" 에 대한 처리가 힘들다. 주의 할 점 전체 작업이 끝나는데 걸리는 시간은 가장 마지막에 실행되는 작업에 의존적이지 않다. 가장 마지막에 끝나는 작업에 의존한다. 예를들어, {a -> b}, {d -> e -> f} 가 있을 때, f 가 가장 마지막에 실행 되지만, b 를 처리하는데 걸리는 시간이 다른 작업 보다 월등히 크다면 이러한 접근은 후순위 작업의 실행 시점에도 영향을 준다. => 코드 참조. [3. 코드]
bfs. [16953] [1. 문제 설명] https://www.acmicpc.net/problem/16953 [2. 풀이 접근] bfs 를 이용해서 A -> B 까지 이동하는 최단 길이를 찾는다. B 는 최대 10억 까지 주어지므로, 배열로 visit table 을 잡을 수 없다. => 메모리 제한 map 을 이용해서 visit table 로 사용한다. A -> B 로 가는 단방향 탐색으로도 시간 내에 해결 할 수 있어보이지만, A->B 와 B->A 로 이동하는 양방향 탐색으로 해결해 보도록 한다. 단방향 탐색으로 시간 내 해결 가능해 보이는 이유는 1.) 현재 값에서 2배씩 늘어남. 2.) 현재 값에서 10배 한 다음 +1 한 값으로 늘어 남. 값이 크게 크게 점프하므로, int 를 사용하면 오버플로우 때문에 오답이 발생 ..
최소신장트리. [14621] [1. 문제 설명] https://www.acmicpc.net/problem/14621 [2. 풀이 접근] 그래프 문제 관련 함정 같은 edge 인데, weight 가 다른 edge 가 여러 개가 입력으로 있을 수 있다. 크루스칼 알고리즘 같은 경우는 우선순위 큐를 사용해서, 최소 weight 가 아닌 edge 는 결과적으로 버려진다. 그러나 최소 신장 트리 문제가 아닌 경우에는, 반드시 최소 weight 인 edge 를 사용하도록 데이터 변경이 필요하다. 이번 문제에서 나름 함정(?) edge 를 구성하는 두 노드의 성향이 같은 경우, 이 edge 는 사용해서는 안된다. => 문제 조건이었다. [3. 코드]
bfs - 예제2 [1. 문제 설명] https://algospot.com/judge/problem/read/HANOI4 [3. 코드]
bfs - 예제1 [1. 문제 설명] https://algospot.com/judge/problem/read/CHILDRENDAY [2. 풀이 접근] 먼저 모든 어린이들에게 같은 수의 장난감을 주고, 욕심쟁이 어린이들에게는 원래 가진 것에서 하나 씩 더 주면 1차적인 조건을 만족 시킬 수 있다. 그래서 구하고자 하는 c 는 아래와 같은 조건이 성립한다. n + m 이상이다. c = kn + m 형태로, c 를 n 으로 나눈 나머지는 m 이다. d 에 포함된 숫자로만 구성되야 한다. 위와 같이 여러 조건을 동시에 만족하면서 답을 찾아야 할 때 일부 조건을 없앤 더 단순한 문제를 푼 후, 조건을 하나씩 추가해 가는 전략이 있다. 단, 어느 조건을 무시하고 문제를 푸느냐에 따라 난이도가 달라 질 수 있다. 여기서는 1번 조건을..
bfs [1. 개요] dfs 와 달리 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘 가중치가 없는 그래프에서, 어떤 시작 정점에서 다른 모든 정점까지의 최단 경로를 계산 할 수 있다. 탐색 중, 처음 방문하는 정점이 있다면 방문 예정이라고 체크하고, (발견 여부라고 보는 것이 좀 더 정확?) Queue 에 푸쉬한다. dfs 와 비교하여 bfs 에서 모든 정점은 3가지 상태를 갖는다. 아직 발견되지 않은 상태 발견되었지만, 아직 방문하지 않은 상태 => 정점의 큐에 저장 된 상태 방문된 상태 [2. bfs 와 최단 거리] bfs 는 보통 딱 하나의 용도로 사용되는데, 두 정점 간의 최단 경로 문제이다. 가중치가 없는 그래프에서 사용 가능 어떤 시작 상태에서 타겟으로 하는 상태까지 가장 빨리 도달하는데..
최소 신장 트리. [6497] [1. 문제 설명] https://www.acmicpc.net/problem/6497 [2. 풀이 접근] 함정(?) 입력이 주어지는 방식 => 보통 몇개의 TC 가 있고, TC 개수 만큼 반복 수행 => 이 문제에서는 특정 입력이 들어오기 전 까지가 모두 TC 이다. u -> v 로 가는 경로가 여러 가지 일 수 있다. => 이 때, => 우선순위 큐 사용이 없으면, u v 로 연결되는 edge 의 cost 를 최소 값을 쓰도록 해야한다. => map 을 이용해서, 최소 cost 추적이 필요 함. => 문제에서 node 가 최대 2,000,000 개 이므로, 인접 행렬을 사용 할 수 없다. => 이 문제에서는 mst 를 구해야 하므로, 우선순위 큐를 사용하므로, 위와 같이 할 필요는 없다. [3. 코드]

티스토리툴바