알고리즘 & 자료구조

총평: 별로입니다. 일단 과제 테스트를 시작하면 건드릴 건 핸들러, 서비스, 레포지토리 정도입니다. ArgumentResolver를 구현하기도 합니다. 이미 구현되어 있는 코드를 보고 스타일을 맞춰가면서 코딩하면 편합니다. 개인적으로 apache - commons-lang3 라이브러리 사용은 처음이었는데 편하고 좋았습니다. getter나 setter를 구현하고 constructor를 구현할 때에는 vscode의 [소스 작업..] 을 잘 활용하는게 좋습니다. Lombok이 없기 때문에 시간을 아껴야 하기 때문이죠.... 혹시나 테스트 코드에서 Order가 에러를 뿜으면 import 문제입니다. junit order를 명확하게 import 해주면 해결됩니다. JdbcTemplate을 사용할 때 JPA만 썼어..

https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 처음에 2차원 DP + DFS로 접근했지만 2차원으로는 해결할 수 없는 문제가 있었다. 그래서 해당 접근은 보류하고 처음부터 다시 생각했고, 방향에 따라서 간선의 가중치가 달라진다는 점과 최단 거리를 구해야한다는 점을 토대로 다익스트라 알고리즘을 사용해서 문제를 풀었다. 이 문제는 진행 방향에 따라서 도로 건설 비용이 달라질 수 있음을 고려해주어야 한다. 아래는 문제에서 설명을 위해 첨..

트라이(Trie)는 컴퓨터 과학에서 탐색 트리의 일종이다. Trie란? Trie는 문자열을 저장하고 효율적으로 탐색을 수행하기 위한 탐색 트리의 일종입니다. 검색엔진, 자연어 처리와 같은 빠른 문자열 탐색이 필요할 때 주로 쓰이는 자료구조입니다. 트라이는 문자열을 저장할 때 위 그래프처럼 문자 단위로 쪼개어 저장합니다. 위에 보이는 TRIE는 현재 CAT, CUT, CUTE, TO, B를 저장하고 있는데요, CUT과 CUTE의 경우를 보면 두 문자열이 접두사를 공유하고 있음을 알 수 있습니다. 따라서 TRIE는 접두사와 연관된 단어를 띄워주는 연관 검색어 기능에 활용할 수도 있습니다. TRIE의 시간 복잡도 만약 가장 긴 문자열의 길이가 m이라고 한다면 삽입에는 총 O(m)의 시간이 소요됩니다. 그리고 ..

[주간 모의 코테 1주차 후기] 오늘은 3시간을 목표로 카카오 2022 양궁대회, 양과 늑대 외 한 문제까지 총 세 문제를 풀고자 했다. 양궁대회는 처음에 떠올린 완전 탐색이라는 아이디어로 1시간 35분 동안 풀었으며, 25개 케이스에서 2개 케이스만 틀리는 나쁘지 않은 점수를 얻을 수 있었다. (하지만 그 두 개의 케이스가 killer case인 듯했다) 아직도 직감에 의존해서 시간 복잡도를 분석하려고 하는데, 정확하게 시간 복잡도를 구하는 연습이 필요할 것 같다. 익숙해지자. 이후 양과 늑대 문제를 푸는데 적절한 알고리즘을 적용하지 못했다. 풀이가 진행될수록 난잡해졌으며, 명확한 알고리즘 선정의 부재라는 문제점이 눈에 보였다. 결국 풀지 못하고 다른 사람들의 접근법을 참고하였고 스스로 풀이를 작성해보..

세그먼트 트리는 sum, sub 연산 말고도 min, max, gcd, lcm과 같은 다양한 연산이 가능한 자료구조이다. Segment Tree 주어지는 연속된 데이터에 대한 구간 연산(Update, query)을 O(logn) 시간에 할 수 있는 자료구조이다. 다음과 같은 배열이 있다고 하자. (index는 왼쪽부터 0이다) SUM 연산을 위한 세그먼트 트리는 위 배열을 다음과 같이 표현한다. 표현 방식은 굉장히 간단한데, 각 노드의 자식 노드를 더해서 해당 노드의 값으로 표현한다. 즉 루트 노드는 전체 원소의 합이라고 볼 수 있다. 전체 원소의 합이라는 것은 전체 원소를 cover 한다는 뜻으로 생각하면 된다. 즉, root에서 leaf로 내려갈수록 cover 범위가 줄어든다고 보면 된다. 그리고 루..

풀이 만약 a, b, p, q 가 다음과 같다고 한다면 [3, 9, 2, 3] a(3) : b(9) = p(2) : q(3)를 만족해야 한다. (여기서 a, b의 값은 재료의 질량이다) 즉 pb * x == qa * y를 만족해야 한다. 그럼 (lcm은 최소공배수, gcd는 최대공약수이다) x = lcm / pb = (qa * pb) / gcd / pb = qa / gcd = 1 y = lcm / qa = (qa * pb) / gcd / qa = pb / gcd = 2 위처럼 x, y를 구할 수 있다. 그런데 이때 x, y에 최대공약수가 존재할 수 있다. 우리는 최소가 되는 결과값을 원하기 때문에 최대공약수가 있다면 해당 값으로 나누어줘야 한다. 따라서 x, y의 gcd를 구하여 나누어준다음 다른 비율들..