IT,프로그래밍/알고리즘

    탐욕법 (greedy) 이란?

    Greedy란? 카테고리가 탐욕법이라고 되어있는데, 이 탐욕법에 대해서 먼저 알아보자. 탐욕법이란 DP(Dynamic Programming)과 상호보완하며 사용되는데, 이번에는 탐욕법에 대해서만 알아보자. 탐욕법이란 기본적으로 현재의 최선을 반복해서 선택하는 해결방법이다. 아래의 이미지를 한번 살펴보자 위의 트리에서 실제 가장큰수는 99이다. ,하지만 탐욕법으로 하면 가장큰수는 12 이다. 왜냐하면 탐욕법은 첫번째 분기에서 1과 9중에 큰 9를 고르고, 그다음에는 3과 12중에 12를 고르기 때문이다. 이렇듯이 탐욕법은 최선의 해결법이 되지는 않지만, 빠른 결과를 산출해 낼수있는 장점이 있다. 탐욕법의 적절한 예 탐욕법의 적절한 사용순간은 언제일까? 탐욕스러운 선택 조건(Greedy choice prop..

    [프로그래머스]-lv.1 체육복

    탐욕법 (greedy) 이란? Greedy란? 카테고리가 탐욕법이라고 되어있는데, 이 탐욕법에 대해서 먼저 알아보자. 탐욕법이란 DP(Dynamic Programming)과 상호보완하며 사용되는데, 이번에는 탐욕법에 대해서만 알아보자. 탐욕법이 burning-camp.tistory.com 아래의 풀이를 보기전에 위의 탐욕법 알고리즘을 먼저 보고 오시면 이해가 빠릅니다! 문제설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있..

    [프로그래머스] - lv.1 이상한문자 만들기

    문제설명 문자열 s는 한 개 이상의 단어로 구성되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 리턴하는 함수, solution을 완성하세요. 제한 사항 문자열 전체의 짝/홀수 인덱스가 아니라, 단어(공백을 기준)별로 짝/홀수 인덱스를 판단해야합니다. 첫 번째 글자는 0번째 인덱스로 보아 짝수번째 알파벳으로 처리해야 합니다. 입출력 예 s return try hello world TrY HeLlO WoRlD 입출력 예 설명 try hello world는 세 단어 try, hello, world로 구성되어 있습니다. 각 단어의 짝수번째 문자를 대문자로, 홀수번째 문자를 소문자로 바꾸면 TrY, HeLlO, ..

    [leetcode] 136. Single Number 해설

    136. Single Number https://leetcode.com/problems/single-number/ Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory? Example 1: Input: nums = [2,2,1] Output: 1 Example 2: Input: nums = [4,1,2,1,2] Output: 4 Example 3: Input: nums = [1] ..

    [leet code]169. Majority Element (최다 요소)

    https://leetcode.com/problems/majority-element/ Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array. Example 1: Input: nums = [3,2,3] Output: 3 Example 2: Input: nums = [2,2,1,1,1,2,2] Output: 2 이 문제는 배열내의 최대다수 를 구하는것이 문제이다. 여기서 중요한점은 The majority ..

    [프로그래머스] 깊이/너비 우선 탐색(DFS/BFS) - 네트워크

    참고 자료 [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) ※ 그래프의 개념 - 정점과 간선으로 이루어진 자료구조의 일종. G = (V, E) ※ 그래프 탐색 - 하나의 정점으로부터 시작하여 차례대로 모든 �� yunyoung1819.tistory.com 나의답 function solution(n, computers) { // n: 컴퓨터 개수 // computers[i][j] // i칸의 수와 같은 j 는 무조건 1임. -> 자기 자신이기 때문에 // 한쪽이 연결되면 반대쪽은 반드시 연결되어있음 -> 2번찾을 필요없음 let answer = 0; const check = (computers, root, n) =>{ fo..