프론트 산악회🌾 프론트 산악회🌾

Problem-Solving

• [프로그래머스] 표현 가능한 이진트리(JavaScript)

  Problem-Solving/Problem 2023. 11. 24. 18:01

  🍀 목차 문제 설계 구현(JavaScript) 최종 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 설계 (1) 표현 가능한 이진트리 경우의 수(h = 1(최소)) 루트 노드가 0일때 루트 노드가 1일 때 (2) 더미 노드를 채워 포화 이진트리로 만드는 부분 높이가 h인 포화 이진트리 노드 수는 2^(h+1) - 1라는 것을 이용한다. 문제를 왼쪽 서브 트리, 루트, 오른쪽 서브 트리로 생각할 수 있다(분할 정복). 구현(JavaS..

• [최소신장트리] 크루스칼(Kruskal) 알고리즘

  Problem-Solving/Algorithm 2023. 10. 29. 03:28

  🍀 목차 크루스칼 알고리즘 같은 목적을 가진 알고리즘 기본 이해 구현(JavaScript) 시간 복잡도 크루스칼 알고리즘 최소 신장 트리 (MST : Minimum Spanning Tree) 알고리즘 중 하나. MST(Minimum Spanning Tree) 모든 정점을 잇는 최소 비용 Spanning Tree를 찾는 것이 목적. 무향 가중치 그래프에서 적용한다. 사이클이 포함되어서는 안 된다(트리는 사이클 없이 모든 정점이 연결되어 있는 그래프 자료구조). 기본적으로 그리디 알고리즘을 바탕으로 하고 있다. 항상 최소 비용을 찾고 탐욕적으로 선택한다. 간선 선택 기반 알고리즘이다. 간선을 가중치(비용) 오름차순으로 정렬하고 Union-Find 알고리즘을 적용하며 사이클 형성 유무를 판단하며 선택해 간다...

• [프로그래머스] 표 병합(JavaScript)

  Problem-Solving/Problem 2023. 3. 6. 04:29

  🍀 목차 문제 설계 구현(JavaScript) 최종 코드 문제 https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 설계 MERGE와 UNMERGE 명령어를 구현하는 데 많은 고민을 했다. 테스트에서는 위의 명령어를 Union-Find로 접근했었으나 구현과정에서 시간이 부족하여 해결하지 못했다. 다시 풀어보니 문제에서 주어진 표의 크기가 50X50으로 크지 않은 편이어서 완전 탐색과 구현으로 해결할 수 있었다. 문제 설명에서 주의 깊게 봐야 할 내..

• [프로그래머스] 등산코스 정하기(JavaScript)

  Problem-Solving/Problem 2022. 9. 7. 17:34

  🍀 목차 문제 설계 구현(JavaScript) 최종 코드 훔쳐보기 문제 https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 설계 코딩 테스트에서 이 문제를 마주쳤을 때는 DFS로 접근했었는데, 테스트 케이스에서 틀리고 시간 복잡도도 엄청났던 코드였다. 몇 개월 뒤 다시 보니 시작 정점에서 목적 정점까지의 최소 거리를 구하는 다익스트라알고리즘으로 접근할 수 있는 문제라고 생각했다. 그러나 몇 시간 동안 헤맸지만 테스트 케이스 3개에서 계속 시간 초..

• [그래프] 유니온-파인드(Union-Find)

  Problem-Solving/Algorithm 2022. 6. 1. 17:09

  🍀 목차 유니온-파인드 알고리즘 기본 이해 구현(JavaScript) 활용 예 시간 복잡도 유니온-파인드 알고리즘 집합을 관리하는 자료구조 유니온-파인드를 활용해 합집합을 찾는 알고리즘이며, Disjoint Set(서로소 집합, 상호 배타적 집합), Merge find Set 알고리즘이라고도 불린다. 유니온-파인드는 루트 노드 밑에 자식 노드들이 엮인 트리 구조를 따른다. 여러 개의 노드 중 선택된 두 노드가 같은 그래프에 속해 있는지 판별한다. 크게 3가지의 과정을 거친다. Initialization(초기화) : 각 노드가 각각의 집합에 포함되도록 초기화하는 과정 Find(찾기) : 특정 노드의 부모를 찾는다. (해당 노드가 속한 집합의 루트를 반환한다.) Union(합치기) : 두 노드 A와 B를 한..

• [프로그래머스] 합승 택시 요금(JavaScript)

  Problem-Solving/Problem 2022. 5. 18. 14:16

  🍀 목차 문제 설계 구현(JavaScript) 최종 코드 훔쳐보기 문제 https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 설계 사실 ..

• [수학] 최대공약수(GCD), 최소공배수(LCM) 알고리즘

  Problem-Solving/Algorithm 2022. 5. 13. 15:20

  🍀 목차 최대공약수, 최소공배수 알고리즘 기본 이해 구현(JavaScript) 시간 복잡도 최대공약수, 최소공배수 알고리즘 최대공약수(Greatest Common Divisor, GCD) : 두 수의 여러 공약수 중 최대인 수. 최소공배수(Least Common Multiple, LCM) : 두 수에 공통으로 존재하는 배수 중 가장 작은 수. A, B의 최대공약수를 구할 때 1부터 시작하여 Math.min(A, B)까지 A와 B가 나누어 떨어지는 최대의 수를 구하면 최대공약수를 구할 수 있지만 이 방법은 시간 복잡도가 O(n)이다. 그래서 최대공약수를 구할 때 유클리드 호제법을 쓴다. 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이다. 나눠가며(log) 구해가기 때문에 훨씬 효율적이..

• [최단경로] 플로이드-워셜(Floyd-Warshall) 알고리즘

  Problem-Solving/Algorithm 2022. 5. 11. 15:18

  🍀 목차 플로이드-워셜 알고리즘 같은 목적을 가진 알고리즘 기본 이해 구현(JavaScript) 그냥 다익스트라를 정점만큼 돌리면 안 되나요? 시간 복잡도 플로이드-워셜 알고리즘 가중 그래프에서 간선 가중치의 합이 최소가 되는 경로를 찾는 최단 경로를 찾기 위한 알고리즘 중 하나. 한 번 실행하여 모든 정점 - 모든 정점 간의 최단 경로를 구할 수 있는 알고리즘. 다이나믹 프로그래밍(DP)을 바탕으로 하고 있다. 음의 사이클이 없는 그래프라면 음의 가중치를 가졌을 때도 사용 가능. (음의 사이클의 존재를 판단할 수 있음.) 같은 목적을 가진 알고리즘 다익스트라 알고리즘 게시글에 정리해놓았다. 기본 이해 모든 정점과 모든 정점 간의 최단 거리를 구해야 하므로 2차원 배열을 생성, 갱신해 나간다. 단계별로 ..