https://www.acmicpc.net/problem/1219(SPFA 연습을 위해 벨만 포드로 풀 수 있는 문제 중 선택을 해보았다.) 민식이는 특정 시작점에서 도착점까지 가는 경로마다 비용이 있고, 노드에 도착하면 돈을 법니다. 문제를 다음과 같이 치환할 수 있습니다. a node -> b node 비용 cost, b node 도착 시 버는 돈 earn : a -> b 갔을 때 버는 금액 = earn - cost도착 지점에 도달했을 때 버는 최종 금액을 최대로 하도록 하여라. 시작점에서도 버는 금액이 포함되는 건지가 햇갈렸는데 test case 5번을 보면 포함됨을 알 수 있습니다. (7만큼 0번에서 번다, 0번에서 0번으로 갈 때는 10의 cost가 든다. => 답 7 => 처음 0번 시작할..
https://www.acmicpc.net/problem/11657(SPFA 공부하고 적용해봤는데 타입 잘 못 잡기 + INF 케이스 오버플로우 방지 안함에 의해 수없이 틀려버렸다....) SPFA 알고리즘은 벨만-포드 알고리즘의 응용으로 벨만-포드 알고리즘이 모든 정점에 대해서 거리를 업데이트하는 것 대신, 거리 업데이트되는 노드를 대상으로만 알고리즘을 진행하는 방식이다. 알고리즘을 진행할 노드를 큐로 관리하며, 큐에 해당 노드가 존재하는 지 체크하는 배열을 별도로 두어 중복 계산을 방지한다. 벨만-포드 알고리즘이 복잡도가 O(VE) 이지만, SPFA는 dense 그래프가 아니면 O(V+E) 수준이므로, 벨만 포드보다 빠르게 음수가 있는 가중치에서도 최단 거리 계산에 접목할 수 있다.그리고 큐에 전체..
Spring Kafka : 카프카를 스프링 프레임워크에서 효과적으로 사용할 수 있도록 만든 라이브러리 (ex. 컨슈머 멀티 스레드 환경 운영 시, concurrency 옵션 추가 등) spring kafka와 kafka client 버전은 아래와 같이 호환됨 spring kafka 2.A.x kafka client 2.A.y 최신 버전은 아래 페이지 참고 (kafka 3.x)https://spring.io/projects/spring-kafka Spring for Apache KafkaThe Spring for Apache Kafka (spring-kafka) project applies core Spring concepts to the development of Kafka-based messaging..
polars vs pandas 비교 테스트
사내에서 데이터 처리를 위해 pandas로 데이터 계산 및 csv 저장 등을 처리하고 있다. pandas가 이미 많이 발전된 라이브러리이지만, 기존 레거시 솔루션을 신규 프로젝트로 컨버팅하는 과정에서 병렬 처리, 비동기 요청에 대해 미지원 등의 이슈가 있어, 핵심적인 계산은 기존과 동일한 상태였다. (물론 컨버팅 과정에서 불필요한 로직 삭제, 불필요한 데이터 제거 등으로 최적화를 꽤 많이 시켰지만 아쉬움이 있는 상태였다.) 최근 kafka를 공부하다가 우연히 polars라는 pandas 대체 라이브러리를 알게 되어 간단히 테스트 결과를 정리하고자 한다. (polars 외에도 dask, modin 등의 pandas 대체 라이브러리 프로젝트가 많은 것도 알게 되었다. 하지만 기존 솔루션의 상황에 가장 적합..
Source Connector : 소스 애플리케이션, 소스 파일로부터 데이터를 가져와 토픽으로 넣는 역할 오픈소스로 제공되는 것도 많지만, 라이센스 문제, 커스텀 기능 등 구현이 필요한 경우도 많음 Kafka 커넥트 라이브러리의 SourceConnector, SourceTask 클래스 이용해 구현을 하면 된다.커넥터 빌드 후, jar 파일을 플러그인으로 추가하여 사용하면 된다. source connector 만들 때 필요한 라이브러리 : org.apache.kafka.connect-api SourceConnector class : 태스크 실행 전, 커넥터 설정 파일 초기화 및 어떤 태스크 클래스를 사용할 것인지 정의 SourceTask class : 소스 애플리케이션, 파일로부터 데이터 가져와 토픽..