junhwa100 님의 블로그

[프로그래머스] 피로도

1. 문제 이해던전마다 최소 필요 피로도와 소모 피로도가 있다.현재 피로도가 최소 필요 피로도 이상이어야 던전에 입장할 수 있고, 탐험하면 소모 피로도만큼 줄어든다.현재 피로도 k로 탐험할 수 있는 최대 던전 수를 리턴한다. (던전은 최대 8개) 2. 풀이 과정던전을 도는 순서에 따라 결과가 달라지고, 정렬 기준만으로는 최적 순서를 보장할 수 없다.(그리디 방식)그래서 모든 순서를 시도하는 완전탐색(브루트포스)으로 푼다. 던전이 최대 8개라서 가능한 순서는 8! = 40,320가지다.itertools.permutations로 모든 순서를 만들고, 순서마다 피로도를 k로 초기화한 뒤 던전을 차례로 돈다. 현재 피로도가 최소 필요 피로도 이상이면 소모 피로도만큼 빼고 개수를 센다. 모든 순서 중 센 개수의..

[프로그래머스] [1차] 뉴스 클러스터링

1. 문제 이해두 문자열이 얼마나 비슷한지 자카드 유사도로 구하는 문제다.자카드 유사도는 교집합의 크기를 합집합의 크기로 나눈 값이다. 문자열을 두 글자씩 끊어서 집합의 원소로 만든다.이때 영문자로만 이루어진 쌍만 사용하고, 공백, 숫자, 특수문자가 낀 쌍은 버린다. 대소문자는 구분하지 않는다. 같은 쌍이 여러 번 나올 수 있어서 집합이 아니라 다중집합으로 계산한다.교집합은 쌍마다 개수가 적은 쪽, 합집합은 개수가 많은 쪽을 가져간다. 두 집합이 모두 공집합이면 유사도는 1로 정한다. 결과에는 65536을 곱하고, 소수점 아래는 버려서 정수로 리턴한다. 2. 풀이 과정두 문자열에서 두 글자씩 끊은 쌍의 개수를 세기 위해 2개의 defaultdict를 사용한다. i번째와 i+1번째 글자가 모두 영문자일 ..

1. 문제 이해파일명 목록을 규칙에 맞게 정렬해서 리턴한다.파일명은 HEAD, NUMBER, TAIL 세 부분으로 나뉜다.HEAD: 숫자가 아닌 문자들 (최소 한 글자)NUMBER: 연속된 숫자 1~5개TAIL: 나머지 (비어 있을 수도 있음)정렬 기준은 다음과 같다.HEAD를 대소문자 구분 없이 사전순으로 비교한다.HEAD가 같으면 NUMBER를 숫자 크기로 비교한다. (012와 12는 같은 값이다.)둘 다 같으면 원래 입력 순서를 유지한다. 2. 풀이 과정파일명 하나를 HEAD와 NUMBER로 쪼개는 함수를 만들고, 이 값을 정렬 기준으로 쓴다. 숫자가 처음 나오는 위치를 찾아 그 앞을 HEAD로 자른다.그 위치부터 숫자가 이어지는 구간(최대 5개)을 NUMBER로 자른다.TAIL은 정렬에 쓰이지 ..

1. 문제 이해대기실 5개가 주어지고, 각 대기실은 5×5 크기다.칸은 응시자(P), 빈 테이블(O), 파티션(X) 중 하나다.응시자끼리 맨해튼 거리 2 이하로 앉으면 거리두기 위반이다. 단, 사이가 파티션으로 막혀 있으면 괜찮다.대기실마다 거리두기를 지켰으면 1, 어겼으면 0을 담아 리턴한다. 2. 풀이 과정판 전체를 훑다가 P를 만나면, 그 P에서 dfs로 거리 2 이내를 탐색한다. dfs는 X를 만나면 멈추고, 거리 2를 넘으면 더 퍼지지 않는다. 거리 2 이내에서 다른 P를 만나면 위반이라 True를 리턴한다. 시작 칸을 visited에 미리 넣어서, 탐색 도중 시작 칸으로 되돌아와 자기 자신을 다른 P로 착각하는 것을 막는다. dfs가 True를 리턴하면 그 대기실은 0, 끝까지 위반이 없으면..

1. 문제 이해m x n 크기의 board가 주어진다.같은 모양을 가지는 2 x 2 크기의 블록을 지울 수 있다.이때 블록은 겹칠 수 있고 한꺼번에 지워진다. 블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다. 만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.지워지는 블록이 몇 개인지 리턴한다. 2 풀이 과정 while문 안에서 for문으로 board 전체를 훑으며, 이번 턴에 지울 수 있는 2×2 블록의 좌표를 set에 모아 한 번에 확인한다. 문제에서 board는 ["CCBDE", "AAADE", ...]처럼 문자열 리스트로 주어진다.파이썬의 문자열은 수정할 수 없어서 board[i][j] = 'x'처럼..

1. 문제 이해 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 한다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같다. (1). 속한 노래가 가장 많이 재생된 장르부터 수록 (2). 장르 내에서 많이 재생된 노래부터 수록 (3). 장르 내에서 재생 횟수가 같다면, 고유번호가 낮은 노래를 먼저 수록 문자열 배열 genres와 정수 배열 plays가 주어진다.베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 리턴한다. Ex). genres: ["classic", "pop", "classic", "classic", "pop"], plays: [500, 600, 150, 800, 2500] -> [4, 1, 3, 0] 리턴 2. 풀이 과정이 문..

1. 문제 이해문자열 벡터 전화번호부가 주어진다. 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인한다. 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 리턴한다. 2. 풀이 과정모든 전화번호를 해시맵에 저장한다.해시맵을 순회하며 번호를 선택한다.해당 번호를 한 글자씩 늘려가며 장부에 있는지 조회한다. 3. 전체 코드#include #include #include using namespace std;bool solution(vector phone_book) { unordered_map map; for (string num : phone_book){ map[num] = 1; } for (st..

26.5.2에 치뤄진 ADP 실기 사전점수를 오늘 확인했다.결론적으로 불합격이다. 군대에서 시간을 쪼개서 나름 열심히 준비했는데 아쉬운 결과다.(우리 부대 사지방 컴퓨터는 정말 많은 인내심을 필요로 한다..) 시험 일정에 맞춰 3일간 집중해서 공부하려고 수요일부터 토요일까지 3박 4일 휴가를 썼다.부대에서 강제로 당한(?) 모래주머니 훈련법 덕분인지, 휴가 기간 동안 온전히 내 노트북으로 시험을 준비할 수 있어 행복했다. 시험 전 계획했던 타임 라인(통계 분석: 1시간 -> 기계학습: 각각 1시간 반씩)을 잘 따라 갔으나..1시간 반을 남기고 마지막 문제인 기계학습 2번 문제를 만나게 되고 남은 모든 시간을 쏟았으나 결국 JSON 전처리 를 해결하지 못했다. 전처리 문제를 제대로 풀지 못하면 뒤 문제들을..

1. 문제 이해정수형 벡터가 주어진다. 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 리턴한다. Ex). numbers = [6, 10, 2]라면 result는 "6210" 2. 풀이 과정C++ sort 함수의 커스텀을 이용한다.(정렬 기준 제시) 먼저 compare 함수를 구현한다.bool compare(string a, string b) { return a + b > b + a; } 정수형 벡터를 문자열형 벡터로 변환한다.vector str_numbers;for (int num : numbers) { str_numbers.push_back(to_string(num));} compare 함수를 매개변수로 정렬한다.sort(str_numbers.begin(), str_numb..

1. 문제 이해 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였다.마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어진다. 완주하지 못한 선수의 이름을 return 한다. 2. 풀이 과정먼저 participant와 competion을 먼저 오름차순 정렬하고 비교하는 방법이 있다.#include #include #include using namespace std;string solution(vector participant, vector completion) { sort(participant.begin(), participant.end()); sort(completion.begin(), completion...