차곡차곡

탐색이란? 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있는데 이 둘을 이해하기 위해서는 기본 자려구조인 스택과 큐에 대한 이해가 되어야 한다. 자료구조란? 자료구조란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 그중 스택과 큐는 자료구조의 기초개념으로 다음의 두 핵심적인 함수로 구성된다. 삽입(push) : 데이터를 삽입한다. 삭제(pop) : 데이터를 삭제한다. 추가로 스택과 큐를 사용할 때에는 언더플로(underflow)와 오버플로(overflow)를 고려해야한다. 오버플로는 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다. 반면 특정한 자료구조에..

https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 장르별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려고한다. 노래는 고유 번호로 구분되며 노래를 수록하는 기준은 아래와 같다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래 장르를 나타내는 문자열 배열 gen..

https://school.programmers.co.kr/learn/courses/30/lessons/12979 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 아파트 N개가 주어지고 아파트 옥상에 기지국이 설치되어있다. 해당 기지국의 범위가 w로 변경되면서 기지국을 추가로 설치해야하는데, 이때 최소로 설치하는 기지국의 개수를 return해줘야한다. 기지국 설치 아파트기준으로 양쪽으로 w만큼 전달 할 수 있다. ex_) 만약 4번 아파트에 w가 2라면 2,3,4,5,6 번의 아파트를 해당 기지국으로 커버할 수 있다. 접근법 모든..

https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 고속도로를 이용하는 차량들의 경로 routes가 주어진다. routes안에는 차량이 고속도로를 진입하는 지점, 나간 지점이 적혀있다. i 번 째 차량은 routes[i][0]에 고속도로에 들어오고 routes[i][1]에 고속도로에서 나간다. 고속도로를 이용하는 모든 차량이 적어도 한번은 단속 카메라를 만나게 하기 위해서 카메라를 최소 몇대 설치해야하는지 return 한..

https://school.programmers.co.kr/learn/courses/30/lessons/12987?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV3 문제 설명 각 팀원이 숫자를 가지고 있고 상대 팀 팀원과 만나 숫자를 비교했을 때 더 큰 숫자를 내면 승점을 얻는다. 만약 숫자가 같으면 둘다 승점을 얻지 못한다. A팀의 팀원의 숫자와 출선 순서가 공개 되었을 때 B팀이 얻을 수 있는 최대 승점을 return 해야한다. 접근법 A팀 팀원이 낸 숫자보다 B팀에서 낼 수 있는 숫자가 작은 경우 B팀의 큰 ..

그리디 알고리즘 그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 탐욕법이라고도 불리는데 이름에서 알 수 있듯이 단순 무식하게, 탐욕적(현재 상황에서 지금 당장 좋은 것만 고르는 것)으로 문제를 해결하는 알고리즘이다. 매순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 대체로 그리디 알고리즘 문제는 정렬 알고리즘과 짝을 이뤄 출제된다. 그리디 알고리즘 적용 조건 탐욕적 선택 속성 : 앞의 선택이 이후의 선택이 영향을 주지 않는다. 최적 부분 구조 : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. 그리디(탐욕) 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느정도 최적에 근사한 값을 빠르게 도출할 수 있..

복잡도란? 복잡도 (Complexity)는 알고리즘의 성능을 나타내는 척도이다. 복잡도는 크게 두가지로 구분할 수 있다. 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미한다. 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을 수록 좋은 알고리즘이다. 시간복잡도와 공간복잡도는 일종의 거래 관계가 성립한다. 메모리를 많이 사용하는 대신 시간적 이점을 얻을 수 있는 경우가 있는데 이 방법으로 메모이제이션 기법이 있다. 시간 복잡도 시간 복잡도를 표기할 때는 빅오..

백트래킹 재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지 판단하고 위배되는 경우 해당 상태를 제외하고 다음 단계로 나아가는 방식이다. 해를 찾는 도중에 막히면 해당 상태로 더 탐색하지 않고 돌아가서 해를 찾아나가는 방식이다. 이때 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)이라고 한다. 모든 경우의 수를 체크하지 않게 되므로 시간을 단축할 수 있다. 유사한 알고리즘으로 DFS(깊이 우선 탐색)이 있다. DFS와 백트래킹의 차이는 DFS는 모든 경우의 수를 탐색하지만 백트래킹은 DFS와 다르게 백트래킹은 불필요한 탐색을 하지 않는다. 사용 문제 의사결정 문제 최적화 문제 열거 문제 핵심 아이디어 재귀 호출 : 문제를 해결하..

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 시작 단어 begin, 도착 단어 target이 주어지고 변환할 수 있는 단어의 배열 words가 주어진다. 변환할 수 있는 조건은 한번에 한 개의 알파벳만 바꿀 수 있고, words안에 있는 단어로만 변경이 가능하다. 최소 몇단개에 걸쳐 begin의 단어를 target으로 변환 가능한지 Retrun해준다. 만약 변환할 수 없는 경우 0을 Retrun 해준다. 해결법 d..

https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 해야할 일이 works 배열에 각 일에 대한 필요 작업량이 저장되어 있다. 1시간에 작업량 1만큼을 할 수 있다. 퇴근 시간까지 남은시간 n 이 주어진다. 야근피로도는 퇴근 시간 이후 각 일의 남은 작업량의 제곱의 합이다. 가장 적은 야근 피로도를 계산해서 Return 해야한다. 접근 법 야근 피로도를 가장 낮추는 방법은 모든 일의 작업량을 균등하게 낮추는 것이다. 남은..