[문제링크] 문제 접근 Dyanamic Programming으로 접근하였다. 참고한 슈도 코드는 다음과 같다. if i == 0 or j == 0: # 마진 설정 LCS[i][j] = 0 elif string_A[i] == string_B[j]: LCS[i][j] = LCS[i - 1][j - 1] + 1 else: LCS[i][j] = ...

[문제링크] 문제 접근 다익스트라로 접근하였다. 코드 분석 1. Global parameters #define MAXSIZE 100001 vector<vector<pair<int, int>>> vec(MAXSIZE); int N, M; 간선의 정보를 담을 vec을 전역 변수를 선언하였다. 문제에 따르면 Di...

[문제링크] 다익스트라 다익스트라를 사용하면 된다. 처음에는 일반적인 bfs를 사용했는데 안풀렸다. 찾아보니까 weighted Edge를 가진 그래프 문제에서는 bfs를 사용하면 최적 해를 보장할 수 없다는 것이 생각났다. 아… 자료구조 시간에 배웠던 기억이 난다. Lessssgo 접근 반드시 거쳐야하는 하는 정점의 id는 A와B라고 가정하...

간단한 entity를 만들고 Mysql과 연동하여 테스트를 했다. package com.sung_1.back_front.dto; import jakarta.persistence.*; import lombok.AllArgsConstructor; import lombok.Getter; import lombok.NoArgsConstruc...

[문제 바로가기] 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리...

[문제 바로가기] 문제 단순한 BFS문제였던거 같은데 푸는데 시간이 좀 걸렸다. 처음에 풀었던 방법과 개선한 방법의 코드 2개를 작성해보았다. 좌표 저장 처음 문제를 풀때 board의 탐색을 최대한 피하고 싶었다. board를 탐색할때마다 O(N^2)시간이 발생하기 때문에 좀 더 효율적으로 정보를 저장하는 방법을 생각해보았다. ...생략 v...

코딩테스트에 자주 나오는 개념인 순열을 파헤쳐보았다. 나는 dfs를 이용하여 순열을 구현했다. 알고리즘 목표 주어진 배열의 원소들의 조합을 모두 구하고, 총 개수를 출력해라. 입력 int array 와 r 값 (단 r<=array의 길이) 출력 nPr의 모든 경우의 수를 출력하고, 순열의 총 개수 또한 출력 나는 이해하기 쉽...

[문제링크] [C++ 순열 구현] 직전에 올렸던 순열 알고리즘을 적용해보는 문제이다. vector<int> v; int solution(string numbers) { for(char c : numbers){ v.push_back(c-'0'); } return answer; } 우선 먼저 solu...

[문제링크] 레벨 1문제이기도 하고 쉽게 풀어보자 했는데 은근히 오래걸렸다. 패턴들을 분석하여 간결하게 코드를 짜보고자 했는데 더욱 더러워졌다. 처음 짠 코드이다. #include<iostream> #include<vector> #include<algorithm> #include<map> using nam...

[문제링크] 이번 문제도 지난 포스팅과 완전히 같은 유형이다. DFS를 통해 루트(vid=1)에서 가장 먼 정점을 찾고, 가장 먼 정점에서 다시 한번 DFS를 진행하면 된다. #include<iostream> #include<cstring> #include<vector> #define MAXSIZE 10000 + 1...