공부/알고리즘30 그래프 + 그래프 순회 정리 요즘 소소한 알고리즘 스터디를 하고 있다. 매주 주제를 정해서 하루에 하나씩 문제를 풀고 있는데, 이번주 주제가 DFS/BFS였다. DFS/BFS 공부를 할 겸, 그래프와 순회 강의를 들으며 정리한 것을 간략히 기록한다. 강의는 Udemy에 있는 JavaScript 알고리즘 & 자료구조 마스터클래스 이다. 그래프 (Graph) : 노드/점들의 집합으로 구성된 데이터 구조 → 간단히 말해, 노드와 노드 간의 연결(Connection)로 이루어진 구조이다 어디에 사용되나? 그래프는 다양한 곳에 사용된다. 밑의 리스트는 한 번쯤 주변에서 경험해봤을, 그래프의 사용처들이다. SNS: Facebook이나 인스타그램 등. 사용자 간의 팔로우 관계가 그래프로 나타난다. Location Mapping 각종 추천 시스.. 2023. 11. 17. 유클리드 호제법 백준의 정수론 문제를 살펴보다, 유클리드 호제법에 대해 알게 되었다. 어떤 것인지 간단하게 파악하고, 이를 이용해 문제를 푼 것에 대해 짤막히 기록한다. 유클리드 호제법 자연수 혹은 정수 사이의 최대공약수(Greatest Common Denominator: GCD)를 구하기 위한 알고리즘. a와 b의 최대공약수는, a / b의 나머지 r과 b의 최대공약수와 같다. 이를 실제 함수로 구현하면 재귀 혹은 반복을 통해 구현할 수 있다. 나는 아래와 같은 코드를 작성해 문제풀이에 활용하였다. const getGCD = (a, b) => { if (a === b) return a; if (a === 1 || b === 1) return 1; if (b === 0) return a; return getGCD(b, .. 2023. 10. 29. 백준에서 JS로 문제 풀이하기 + 이런저런 메모(+추가: 2023.11.22) 앞서 올린 백트래킹 게시물에서 언급했듯, 얼마 전부터 시간이 날 때 조금씩조금씩 알고리즘 문제 풀이를 하고 있다. 주로 백준에서 문제를 풀고 있는데, 백준에서 문제를 풀 때 어떻게 풀고 있는지 + 문제 풀 때 개인적으로 알아두면 좋을 것 같은 점을 간단하게 기록해두려 한다. 백준에서 JS로 문제를 풀기 위한 세팅 예전에 백준에서 문제를 풀 때는 C++를 사용했는데, 이제는 거의 잊어버리기도 했고 업무를 JS로 하다 보니 JS로 문제를 풀어야겠다는 생각으로 아무 생각 없이 언어 설정을 살펴보았다. 하지만 자바스크립트는 목록에 보이지 않았고... node.js만 덩그러니 있어서 뭔가 싶던 도중 검색을 통해 JS는 node.js를 선택해야 함 + 입력값을 직접 처리해야 함 이라는 정보를 얻게 되었다. JS로의.. 2023. 10. 23. 백트래킹 근래에 꾸준한 공부 습관을 다시금 들이고자 틈틈이 알고리즘 문제를 풀고 있다. 그러던 와중, '백트래킹'에 대해 조금 공부하게 되어 개념과 푼 문제를 간단하게 정리해보려 한다. 백트래킹(Backtracking) 현재 상황에서 탐색 가능한 모든 경로를 다 탐색하다, 조건에 맞지 않는 경로를 탐색하게 될 경우 다시 뒤로 돌아가서 다른 경로를 탐색하는 알고리즘. 이 때 해결하려는 문제는 트리 구조로 표현되며, 이를 탐색하는 데에는 깊이 우선 탐색을 사용한다. DFS와는 달리 조건(한정 조건이라고 하는 듯)에 맞지 않는 해가 나오면 이전으로 돌아가기 때문에 최종적으로 탐색 시간이 줄어든다는 특징이 있음. 백트래킹을 접하며 참고했던 어느 블로그에서 DFS와 백트래킹을 유사점(교차점)이 있는 교집합 관계같다 표현한.. 2023. 10. 15. [~0718] 알고리즘 어쩌다 보니 '프로그래머스'에서 잠시 코딩 테스트 연습을 했었다. 짧은 시간 동안 우다다다 풀은 것이라 조금 난잡하지만 이왕 풀어본 거 이곳에 정리해두기로 했다. 이하의 문제들은 거의 대부분 코딩테스트 고득점 Kit 속 문제들이다. 기능개발 반복문을 돌면서 진도를 나타내는 progresses 벡터에 작업 속도를 더한다. 배포는 progresses에 들어있는 순서대로 진행되기 때문에, 큐의 front 역할을 할 변수 i를 두어 다음에 배포될 기능이 몇 개인지 확인한다. #include #include using namespace std; vector solution(vector progresses, vector speeds) { vector answer; int i = 0, numOfPro = 0; whi.. 2021. 7. 19. [0629] 알고리즘 1018. 체스판 다시 칠하기 그냥 브루트 포스 문제인데, 새삼 이런 알고리즘 문제는 발상을 잘 내야 한다는 것을 실감한 문제였다. #include #include #include int main() { std::cin.tie(NULL); int n, m, num, num1 = 0, num2 = 0, min; std::cin >> n >> m; min = n * m; char c; char chess[n][m]; for (int i = 0; i > c; chess[i][j] = c; } } for (int i = 0; i 2021. 6. 30. 이전 1 2 3 4 5 다음
