MZ 개발자

2021 Dev-Matching 상반기 1번 문제로 지워진 로또 번호를 가지고 최대 등수와 최소 등수를 구하는 문제이다. 번호는 6개 밖에 안되기 때문에 2중 for문을 돌려도 n^2 즉 36 번밖에 연산을 하지 않는다. #include #include using namespace std; vector solution(vector lottos, vector win_nums) { vector answer; int match = 0; int zeroCnt = 0; for(int i = 0; i < lottos.size(); i++) { if(lottos[i] == 0) { zeroCnt++; continue; } for(int j = 0; j < win_nums.size(); j++) { if(lottos[..

문제를 보는 순간 비트연산이 떠올랐다. 내가 문제를 많이 안풀어봐서 그런가 카카오 문제가 뭔가 독특한거 같다. 비트연산은 해본 경험이 있지만 이를 문자열로 변환하거나 출력해본적이 없었다. 검색의 도움을 받아 "bitset" 이라는 헤더가 있다는 것을 알게 되었고 bitset(숫자) 형식으로 사용하고 to_string을 이용하여 문자열로 변환할 수 있었다. 풀이는 다음과 같다. #include #include #include using namespace std; vector solution(int n, vector map1, vector map2) { vector answer; vector result(n, 0); for(int i = 0; i < result.size(); i++) { result[i] ..

문제를 어디서 많이 봤다고 생각했는데 작년에 실제로 테스트 봤던 문제였다. 당시에는 Python으로 문제를 풀었었다. 당시 작성했던 코드가 있는데 지금 보면 어떻게 풀었는지 알수가 없다. (뭔가 알고리즘 없이 맨해튼 거리로만 푼거 같은데 도저히 이해 불가능) def solution(places): answer = [0,0,0,0,0] for place_num,place in enumerate(places): person_location = [] flag =True for i,row in enumerate(place): for j in range(len(row)): if row[j]=="P": person_location.append((i,j)) for i in range(len(person_locatio..

입력으로 영어와 숫자가 포함된 문자열이 들어오면 문자열을 원래 숫자로 치환하는 문제이다. 개발은 Java로 하는데 알고리즘은 C++로 푸는 것이 편해서 오랜만에 풀다보니 문법을 다 까먹었다. 처음에는 s.length() 만큼 반복하면서 알파벳을 누적하고 누적과 동시에 해당 문자열이 숫자로 치환 가능한지 체크하는 함수를 만들어 풀려고 시도 했다. 그냥 삽질했음.... std::string 의 메소드를 잘 알지 못해서 이런 이상한 짓을 하였다. 사실 Python에는 replace함수를 매우 간단히 쓸수 있어 C++은 외우지 않았다.... (std::string에 replace가 있다니... 심지어 to_string 도 내장... WOW) 풀이는 다음과 같다. #include #include using nam..

문제에서 '최고만을 지향하는' 이라는 힌트를 통해 그리디(Greedy) 알고리즘을 사용하는 것을 유추할 수 있다. 따라서 서류심사 성적, 면접 성적 순위중 하나를 잡아 1등부터 나열한후 첫번째 부터 선택을 해 나간다. 예를 들어 서류 심사 기준으로 정렬했다고 가정해보자. 테스트 케이스를 정렬하였을 경우 각각 다음과 같이 된다. a b //a=서류 b=면접 1 4 2 3 3 2 4 1 5 5 a b //a=서류 b=면접 1 4 2 5 3 6 4 2 5 7 6 1 7 3 이미 서류 기준으로 정렬 하였기 때문에 A지원자 (1 4) 와 B지원자 (2 3) 을 비교하면 B지원자는 무조건 A지원자의 면접 순위보다 높아야 합격 할 수 있다. 즉 위의 정렬한 예시에서는 이후 지원자가 이전 지원자의 면접 최고 순위 보다..

하나의 회의실을 여러 회의가 사용하는데 각각의 시작 시간과 끝나는 시간이 주어진다. 회의를 잘 스케쥴링 하여 회의실을 사용할때 최대 몇개의 회의가 회의실을 사용할수 있는지 구하는 문제이다. 처음에 어렵게 꼬아 생각하여 시작 시간이 빠른 순서대로 정렬하고 끝나는 시간이 빠른 순서대로 정렬하여 두개를 어떻게 지지고 볶아 비교하려고 하였다.(생각해보면 다음 회의 시작 가능 여부는 이전 회의의 종료 시간에 따라 결정된다.) 따라서 끝나는 시간을 기준으로 정렬 하여 제일 일찍 끝나는 회의를 기준으로 다음 회의 시작 시간을 결정하면 된다. 한편 문제에서 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의 시작시간과 끝나는 시간이 같을 수도 있다. 라고 주어졌기 때문에 다음과 같은 반례가 생길 수 있다..

문제를 읽어보면 OS 스케쥴링에서 SJF 알고리즘인것을 확인할 수 있다. 기존 1번 방식으로 모든 사람이 돈을 인출하는데 걸리는 wating time은 FIFO 스케쥴링에 의해 39 분을 기다려야 한다. 반면 SJF 는 가중치(P)가 가장 작은 순서 우선으로 처리한다. n=[2,5,1,4,3] p=[1,2,3,3,4] 일때 일을 끝내는데 걸리는 시간은 다음과 같다 2= 1 5= 1+2 1= 1+2+3 4= 1+2+3+3 5= 1+2+3+3+4 위의 결과를 다 더하는것이 답이므로 다음과 같은 식을 구할 수 있다. i=n result += i*p[n-i] #include #include #include using namespace std; int main() { ios_base::sync_with_stdio..

알고리즘 시간에 체스판 문제는 비숍 또는 퀸 문제인데 이 문제는 그보다 조금 쉬운 룩 문제이다. 처음에 문제를 제대로 읽지 않아 n-queen의 prunning 문제인줄 알았는데 알고보니 가로 세로에 같은 룩을 배치하면 안되는 문제이다. 문제에서 제시한 조건은 총 2가지이다. - 룩은 정확히 8개의 룩이 있어야 한다. - 모든 룩은 서로 공격할 수 없어야 한다. 즉, 서로 다른 두 룩은 같은 열에 있거나 같은 행에 있으면 안 된다. 때문에 1차원 백터 하나와 2차원 벡터(입력) 이 두개로 해결 가능하다. #include #include #include using namespace std; int main(int argc, char** argv) { int test_case; int T; cin>>T; f..

알파벳 소문자(a-z)로 구성된 문자열 N개가 주어졌을때 문자열을 알파벳을 순서대로 보면서 앞에서부터 몇 개의 알파벳이 순서에 맞게 적혀 있는지 구하는 프로그램이다. 각 케이스마다 문자열을 input 이라고 놓았을경우 input[0]은 문자열의 첫번째 문자가 되고 input[1]은 문자열의 두번째 문자가 된다. i=0 부터 current = input[i], next = input[i+1] 에서 next - current 가 항상 1이 나오면 알파벳 순서도 나열되있다고 알 수 있다. 한편 문제에서 "순서는 a부터 순서대로 일치하는 알파벳 개수를 계산하여야 한다". 라는 조건이 있기 때문에 input[0]이 a가 아니면 0을 반환한다. #include using namespace std; int main(..

단순 문자열 파싱 문제이다. 무지성으로 그냥 if -else 때려 넣고 시도했다가 시간초과.... 너무 쉽게 생각한거 같다. 생각해낸 아이디어는 for문을 돌때마다 해당 symbol의 value를 넣고 그 symbol의 바로 앞 symbol이 I,X,C일 경우 x2를 해여 빼준다. 이렇게 해결한다면 O(n) 만에 값을 구할 수 있다. class Solution { public: int getValue(char symbol){ int value=0; switch (symbol){ case 'I': value =1; break; case 'V': value =5; break; case 'X': value =10; break; case 'L': value =50; break; case 'C': value =1..