Written by Jieun

👩🏻‍💻 내 마음대로 Today I Learned

코딩테스트, 알고리즘

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42747 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 제한 사항 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다. 논문별 인용 횟수는 0회 이상 10,000회 이하입니다. 입출력 예 citations return [3, 0, 6, 1, 5] 3 이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다..

2023. 12. 16.

코딩테스트, 알고리즘

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연수입니다. 입출력 예 numbers target return [1, 1, 1, 1, 1] 3 5 [4, 1, 2, 1] 4 2 문제 풀이 깊이 우선 탐색(DFS)를 사용해서 가능한 경우의 모든 수를 탐색하고, target 넘버를 만들 수 ..

2023. 11. 29.

코딩테스트, 알고리즘

그래프란? 정점과 간선으로 이루어진 자료구조로 정점간의 관계를 조직도로 표현한다. 🔎 정점: 여러가지 특성을 가질 수 있는 객체 🔎 간선: 정점들 간의 관계 그래프의 종류 무방향 그래프: 정점간 간선에 방향이 없는 그래프 방향 그래프: 정점간 간선에 방향이 있는 그래프 그래프 알고리즘 너비우선탐색(BFS, Breadth-First Search): 탐색을 시작하는 노드로부터 거리순으로 방문하는 탐색 알고리즘 큐(Queue)로 구현하기 function bfs(graph, root) { const visited = new Set([root]); // 중복 방문 방지 const result = []; // 탐색 결과 저장 const queue = [root]; // 시작 노드로 큐 설정 // 큐가 비어있지 않을..

2023. 11. 28.

코딩테스트, 알고리즘

완전 탐색이란? 가능한 모든 경우를 살펴보는 과정. 주어진 문제에 대한 해결책을 찾기 위해 가능한 모든 경우를 시도하고, 그 중에서의 최적의 해결책을 찾는 알고리즘 모든 가능성을 다 검토하기 때문에 확실한 정확도를 가지지만, 경우의 수가 많은 경우 계산 시간이 길어질 수 있다. 연속 부분 최대합 문제 숫자의 리스트가 있을 때 연속된 부분을 선택할 때 그 최대합 출력하기 1 2 -4 5 먼저 연속된 부분의 길이가 한 칸인 경우는 4가지 (1 / 2 / -4 / 5) 그래서 연속된 부분의 합은 각각 1, 2, -4, 5가 가능하다. 연속된 부분의 길이가 두칸인 경우는 3가지 (1, 2 / 2, -4 / -4, 5) 그래서 합은 각각 3, -2, 1이 가능하다. 연속된 부분의 길이가 세칸인 경우는 2가지 (1..

2023. 11. 26.

코딩테스트, 알고리즘

탐욕적 기법이란? 작은 선택의 순간에 가장 이익이 되는 선택을 내려서 전체적인 결과에서 최적의 해를 구하는 프로그래밍 기법 동적 계획법(Dynamic Programming)으로도 최적화 문제를 해결하기 위한 방법으로 사용할 수 있지만, 동적 계획법은 보다 일반적이고 완전한 최적해를 찾는다면 탐욕적 기법은 간편하고 빠르게 근사해를 구하는데 유용하다. 동전 거스름돈 문제 가게에서 500원, 100원, 50원, 10원짜리 동전을 사용하고 있을 때 손님이 받아야할 거스름돈이 760원이라면 가장 적은 동전의 개수로 거스름돈을 주려면 어떻게 해야할까? 값이 가장 큰 동전부터 사용할 수 있는지 확인하면 된다. 가장 큰 동전 500원이 760원보다 작기 때문에 500원부터 차례대로 살펴보기 동전 개수 남은 돈 500원..

2023. 11. 17.

코딩테스트, 알고리즘

동적계획법(Dynamic Programming, DP) 이란? 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 푸는 방법 동적계획법은 재귀적인 방법이지만, 중복 계산을 피하기 위해서 메모이제이션(Memoization) 또는 반복적인 방법을 사용하여 구한다. 메모이제이션은 계산한 값을 저장해두고 필요할 때 불러와서 중복계산을 피하는 방식 동적계획법 문제의 특성 중복되는 부분 문제(Overlapping Subproblem): 작은 하위 문제들이 중복되어 나타난다. 최적 부분 구조(Optimal Substructure): 전체 문제의 최적해결 방법을 부분 문제의 최적해결 방법으로 구할 수 있다. 피보나치 수열 피보나치 수열이란? 이전 두 항의 합이 다음 항이 되는 수열을 말한다. 재귀를 통한 피보나치 수열..

2023. 11. 16.