알고리즘 스터디 2주 차 주제 : 맵과 셋 https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. 홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의..
알고리즘 스터디 2주 차 주제: 맵과 셋 https://school.programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마..
알고리즘 스터디 1주차 주제: 정렬 문제 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 number..
알고리즘 스터디 1주차 주제: 정렬 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 입력 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ ..
알고리즘 스터디 1주차 주제 : 정렬 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 절댓값이 1,000,000보다 작거나 같은 정수 N개가 주어진다. 문제 접근 수 정렬하기 문제와 유사하지만 최대 100만개의 수를 정렬하는 만큼 시간 복잡도가 logN인 알고리즘을 채택해야 합니다. 퀵 정렬은 최악의 경우 O(N^2)의 시간 복잡도를 갖고, 병합 정렬(merge sort)는 메모리가 넉넉하지 않은 환경에서 O(NlogNlogN)의 복잡도를 가지므로 언제나 O(NlogN)을 보장하는 힙 정렬을 선택했습니다. 문제 풀이 C++은 헤더파일에서 다양한 정렬 알고리즘을 제공합니다. 이를 이용해 코드를 짰습니다. 1. 힙을 생성한다. 2. 힙을 정렬한다. 3. 반복자를 이용해..
알고리즘 분류 비트 마스크 solved.ac 티어 silver 3 문제 링크 https://www.acmicpc.net/problem/14889 관련 블로그 포스팅 이 게시글은 코드 플러스 강의 '알고리즘 기초 2/2'의 강의 내용을 기반으로 작성되었습니다. 문제 이해 N 개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분 수열 중에서 그 수열의 원소를 모두 더한 값이 S가 되는 경우의 수를 구하는 문제. 즉, 공집합을 제외한 부분 수열을 구해야 하고 부분 수열의 원소를 더한 값이 S가 되는지 확인해야 한다. 문제 접근 N 개의 정수로 이루어진 수열에서 부분 수열 구하기 수열의 부분 수열은 각 원소의 유무로 표현이 가능하다. 수열의 n 번째 원소를 An이라고 했을 때, 부분 수열을 아래와 같이 표..
