Miscellaneous

https://www.acmicpc.net/problem/2098 해당 문제는 이전에 풀었던 문제였음에도 불구하고, 최근 기업 코테에서 이와 비슷한 유형의 문제를 풀지 못했습니다. 아쉬운 마음에 복습하고자 해당 문제의 풀이를 작성합니다. 해당 문제는 백트래킹으로 구현할 시 O(16!)으로 시간초과가 발생합니다. 이 문제는 외판원 순회라는 well-known 유형입니다. 문제의 조건과 같이 n이 16이하일 때에는 비트마스킹 dp로 해결할 수 있습니다. dp 상태는 아래와 같이 정의합니다.dp[i][j] : 현재 위치가 i이고, 지금까지 j 도시를 방문했을 때의 최단거리n 2^16 = 65536이기 때문에 배열로 충분히 선언할 수 있는 크기입니다. 풀이 코드는 전형적인 비트마스킹 탑다운 dp 코드입..

안녕하세요.올해부터 싸피 15기를 다니게 되었고, 싸피를 통해서 B형 시험에 응시 할 수 있었습니다. 저는 지난 26년 3월 14일(토)에 역량테스트를 볼 수 있었고 다행히 합격하게 되어, 제 경험을 공유하고자 후기를 작성합니다.B형 시험에 관심이 있으신 분들, 추후 B형 시험에 응시하시는 분들께 도움이 되었으면 좋겠습니다. * B형 있는데 왜 또 보셨나요?사실, 저는 이미 B형을 취득했었습니다. (관련 포스팅)이미 있음에도 불구하고 이번 검정에 응시한 이유는, B형 만료기간 때문이었습니다. B형은 2년의 유효기간을 가지고 있습니다. 기존 B형은 2024년에 여름에 취득했었고, 올해 여름에 만료될 예정이었습니다.취준생 신분이라 기회가 될때마다 삼성전자에 지원하고 있는데, 올해 상반기가 B형을 마지막으로 ..

0. 인트로 교내 학술제 프로젝트로 산책 기반 게이미피케이션 봉사 서비스를 기획 및 개발했습니다. 감사하게도 해당 학술제에서 대상을 수상했지만, 시간에 쫓겨 개발한 탓에 코드 품질과 성능에 대한 아쉬움이 남았습니다. 특히 서비스의 핵심 기능인 '포인트 기반 랭킹 시스템'은 데이터가 쌓일수록 성능 저하가 우려되는 부분이었습니다. 이 글은 가상으로 10만 건의 대용량 데이터 환경을 구축하고, 랭킹 조회 API의 병목을 진단하여 응답속도를 1200배 이상 개선한 트러블 슈팅 기록입니다. 1. 기존 환경 설명 기존의 rankings 테이블의 구조와 랭킹 조회 쿼리는 다음과 같습니다. CREATE TABLE rankings ( rank_period int NOT NULL, id bigint NOT NULL ..

서론"4학년되면 취준 진짜 열심히해서 칼취업해야지!" 했던게 엊그제 같은데, 벌써 졸업을 앞두고 있습니다.어느새 연말이 됐고, 당장에 바쁜 것도 다 끝난 김에 작년처럼 회고를 작성합니다. 2025년의 목표는 아래와 같았습니다.1. 자격증 따기 (정처기, SQLD)2. 취업하기 / 외부 교육 프로그램(부캠 etc) 합격하기3. 졸업 학점 올리기4. 알고리즘 동아리 잘 운영하기!5. ICPC 본선 2트 목표 외에, 기록하고 싶은 내용은 아래와 같습니다.1. 교내 학술제2. 운동3. 백준 다이아 회고를 쓰기 전에는 올해는 뭔가 한게 별로 없다고 생각했었는데, 이렇게 적고 나니까 그래도 뭘 하긴 했네요 ㅎㅎ..;1. 자격증 따기 (정처기, SQLD) 취업 준비를 시작하기 앞서서, 정량적인 스펙이 필요함을 느꼈..

글을 작성하기 하루 전인 12월 23일 15:00에 싸피 합격 발표가 났습니다. 해당 포스팅에서는 싸피를 준비하면서 제가 해왔던 것들에 대해서 작성했습니다. 이 글이 싸피를 준비하는 다른 분들에게 도움이 되었으면 좋겠습니다. 지원동기우선 싸피는 보험이었습니다. 저는 졸업을 앞둔 대학생이었고, 싸피 지원 당시 몇몇 기업에 지원했던 상태였습니다.하반기에 취업을 성공한다면 괜찮겠지만, 혹시나 떨어지게 될 때를 대비해서 싸피에 지원했습니다. 괜히 공백기가 생기면 조금 그러니까요..! 그리고 다른 분들도 그렇겠지만, 가장 큰 동기는 돈입니다..!1년동안 매달 100만원 씩 주는 교육프로그램을 소마를 제외하면 제가 알기론 싸피가 유일합니다. 지원금 덕분에 알바 병행 없이 취준에만 집중할 수 있다는 점에서 싸피는 ..

서론취준 스터디에서 싱글톤과 프록시에 대해 공부하던 중, @Configuration 어노테이션이 빈을 관리하는 방법에 대해 조사하게 되었습니다.조사 과정에서 @Configuration의 내부 동작 방식을 깊이 살펴보았고, 빈이 관리되는 과정을 추적하였습니다. 해당 포스트에서는 그 과정을 정리하여, @Configuration이 어떻게 빈을 싱글톤으로 보장하는지 원리를 살펴보겠습니다. 본론@Configurationpublic class AppConfig { @Bean public A a() { return new A(b()); } @Bean public B b() { return new B(); }}위 코드는 간단한 Configuration 클래스..

https://www.acmicpc.net/problem/1034 해당 문제는 흔한 브루트포스 문제랑은 살짝 결이 다른 느낌을 받았습니다. 처음 생각했던 풀이는 2^m가지 경우를 다 돌리는 풀이였습니다.하지만, 스위치를 누르는 횟수 k에 대해서 m 한 스위치를 두번 누르는 것은 안누른 것과 동치이기 때문에 이런 경우에 대해서 따로 예외처리를 해주려고 했으나, 생각해주어야 할 것들이 너무 많아지더라구요. 결국 기존 풀이는 폐기하고, 다른 풀이를 생각해보았습니다. 관찰한 내용은 아래와 같습니다. 1. 만약 두 개의 행 A,B가 동일한 형태를 띈다면, A행이 켜진다면 반드시 B형도 켜질 것입니다. 반대로, A,B가 하나라도 다른 부분이 있다면, 해당 행은 반드시 동시에 켜질 수 없습니다. 2. 한 행에서 켜야..

https://www.acmicpc.net/problem/6525 n*n 행렬에서 각각의 칸들이 서로 다른 행과 열에 속해있도록 n개의 칸을 선택합니다. 이렇게 선택하는 경우의 수는 총 n!개입니다. n!개의 경우의 수에 대해서 n개 원소의 총 합이 모두 같은 지를 판단하는 문제였습니다. 규칙이 있을 것 같은데, 고민해봐도 찾지 못하겠더라구요.그래서 저의 경우에는 랜덤화를 이용하여 해결했습니다. 무작위로 1만개의 수열을 생성한 뒤, 합이 일정한지를 확인했습니다. 문제해결을 하면서 랜덤화를 처음 사용하게 됐는데, 주요 함수는 아래와 같습니다.// 시드값 (time(NULL))에 대한 난수 생성mt19937 rng((unsigned int)time(NULL));// 난수 생성기를 기반으로 배열 셔플su..