뭘 배웠지?

알고리즘 공부하며 배운내용 백준 2798번 - 변형 블랙잭 N장의 카드를 바닥에 높고, M을 외친다. 플레이어는 N장의 카드에서 3장을 선택해 M을 넘지 않고 제일 가깝게 만들어야한다. 들어오는 값 첫째 줄에 카드 개수 N, 지정값 M 둘째 줄에 바닥에 깔린 카드 예) 5 21 5 6 7 8 9 구하고 싶은 값 M을 넘지 않으면서 M에 최대한 제일 가까운 카드 3장의 합 예) 21 생각 모든 경우의 수를 따져봐야 할 듯 코드 세 번의 for문으로 전체 따져봤다 const fs = require('fs') let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n') let fl = input.shift().split(' ') let tot..

알고리즘 공부하며 배운내용 찍먹 vs 부먹 찍먹과 부먹의 선호도는 -1000부터 1000사이 정수로 표현 수가 작을수록 찍먹 선호, 클수록 부먹 선호 친구를 만날 때 마다 지금까지 만났던 친구의 찍먹과 부먹의 선호도의 중앙값만큼 선호 선호도를 출력 들어오는 값 친구 N명의 선호도가 만난 순서대로 입력 예) 10 -10 5 2 -3 -10 2 구하고 싶은 값 2명째 친구부터 선호도를 순서대로 각 줄에 출력 예) 0 5 3 2 0 2 생각 1. 2개부터 정렬을 해서 중간값을 구할 수 있겠다. 2. 최소값, 최대값으로 중앙값을 구할 수 있겠다. 코드 최소값, 최대값 방법으로 풀려고 하다가 미끄러졌다. 정렬 방법을 마구잡이로 만들었다. // VSCode에서 JavaScript 테스트 하기위한 코드 // 메모장에..

알고리즘 공부하며 배운내용 상대평가 2번의 시험으로 학생들을 선발한다. 그 후 상대평가로 뽑는다. 어떤 학생보다 두 과목 높거나 같은 점수를 받은 학생이 있으면 어떤 학생은 선발이 안된다. 반대로 두 과목 모두 높거나 같은 점수가 없으면 입학한다. 모든 과목의 점수가 같으면 1명만 입학할 수 있다. 예를 들어 3명의 성적이 이렇다면, (700, 800), (800, 800), (700, 700) 세 번째 학생은 불합격이다. 이 데이터를 바탕으로 총 몇 명이 입학할 수 있는지 알아보자 들어오는 값 첫째 줄에 학생수 N이 입력된다. 둘째 줄부터 N줄까지 시험점수 2개가 입력된다. 최소 0점, 최대 1000점 예) 5 100 200 200 300 400 400 300 500 500 300 구하고 싶은 값 합격..

알고리즘 공부하며 배운내용 줄 세우기 가게에서 경품권을 줄 선 순서대로 나눠줬다. 경품권이 잘못돼서 다시 나눠줘야 되는데, 본인들이 몇 번째였는지 기억을 못한다. 근데, 모든 사람이 본인 앞에 키가 큰 사람이 몇 명 있었는지 기억한다. 이를 이용해서 어떤 순서로 서 있었는지 알아보자 들어오는 값 키가 작은 사람부터 자신보다 키가 큰 사람이 몇 명 있었는지 입력 예) 3 1 1 0 제일 키가 작은 첫 번째 사람 앞에는 3명의 키 큰 사람이 있었다. 그다음 키가 작은 사람 앞에는 1명의 키 큰 사람이 있었다. . . . 구하고 싶은 값 키가 작은 사람 순서대로 1, 2 ... n 번호가 있다면, 처음 어떻게 서 있었는지 출력 예) 4 2 3 1 제일 작은 사람 앞에 4, 2, 3 번째 사람들이 있었다. 그 ..

알고리즘 공부하며 배운내용 마라톤 경기 트랙에 N명이 달리고 있다. 모든 선수는 각자 실력인 S가 있고 자신보다 실력이 낮은 사람을 추월이 가능하다 예를 들면 선두에 달리는 선수부터 나타내면 이렇다 1 3 2 4 4 3 5 여기서 실력이 3인 두 번째 선수는, 실력이 1인 첫 번째 선수를 앞질러 1등을 할 수 있다. 하지만 세 번째 선수는 아무리 빨리가도 2등이 최고다 이럴 때, 각 선수가 기록하는 최대 등수를 출력을 해보자 들어오는 값 실력 S가 선두부터 차례대로 입력된다. 예) 1 3 2 4 4 3 5 구할 값 최대 등수를 입력과 같은 순서로 출력 예) 1 1 2 1 2 4 1 생각 바로 생각났던 방법은 for문으로 두 번째부터 앞의 번호와 비교하는 방법 핵심 포인트 병합 정렬(Merge Sort)을..

알고리즘 공부하며 배운내용 크레인 크레인에 달려 있는 줄을 이용해 무거운 물건을 들어올린다. 200kg까지 들어올릴 수 있는 줄을 3개 사용하면 600kg을 들 수 있다. 줄의 강도가 섞이면 약한 줄에 맞춰진다. 100kg 150kg 두 줄을 같이 쓰면 200kg까지 들 수 있다. 가지고 있는 줄이 올릴 수 있는 무게가 들어오면, 들어올릴 수 있는 가장 무거운 무게를 알아보자 들어오는 값 가지고 있는 줄이 올릴 수 있는 무게 예) 100 300 400 보여줄 값 주어진 줄로 올릴 수 있는 최대 무게 예) 600 핵심 포인트 1줄을 사용하면 가장 강도가 센 줄을 사용한다. 2줄을 사용하면 첫 번째로 강도가 센 줄과 두 번째로 센 줄을 사용한다, 무게는 두 번째 줄이 기준이 되겠고 i개를 사용하면 i 번째까..

알고리즘 공부하며 배운내용 문자열 압축 0과 1로 이루어진 문자열이 있다. 다음 규칙으로 압축을 해보자 모든 문자가 1이면 1로 압축 모든 문자가 0이면 0으로 압축 그 외 문자열을 절반으로 나누어 '( + 압축된 왼쪽 문자열 + 압축된 오른쪽 문자열 + )'로 압축 예를 들어 1111 은 1 0000 은 0 1100 은 (10) 들어오는 값 0과 1로 이루어진 문자열 문자열은 짝수 길이로 주어진다 예) 1111000011110000 보여줄 값 압축된 문자열 출력 예) ((10)(10)) 핵심 포인트 재귀함수 접근하면, 1이나 0이 반복될 때 정리해줄 베이스 케이스를 정해두고, 반복이 안될 시 왼쪽, 오른쪽 절반씩 재귀함수로 불러준다 => 이를 분할정복이라고 하나보다 코드 // VSCode에서 JavaS..

알고리즘 공부하며 배운내용 손에 손잡고 올림픽 개막식에 손에 손잡고 공연을 한다. 우선 모든 사람이 옆 사람과 손을 잡을 수 있는지 확인을 하고, 모두와 잡을 수 있으면 얼마나 떨어져 있는지 알아내려고 한다. 각 사람의 위치는 (x, y) 좌표로 표현된다. y 좌표가 같으면 같은 줄에 서있는 거다. 들어오는 값 첫 번째 줄에는 전체 사람 수 N이 입력된다. 두 번째 줄부터는 사람들 차례대로(x, y)가 입력된다. 예) 5 1 3 2 3 3 5 1 5 7 5 보여줄 값 모두가 옆 사람과 손을 잡을 수 있는 경우 SUCCESS 출력, 그 다음줄에 가장 먼 거리를 출력 아니면 FAIL 출력 예) SUCCESS 4 핵심 포인트 전부 다 비교하지 않고, 왼쪽 오른쪽만 비교하면 된다. y좌표가 같으면 x좌표를 비교..

알고리즘 공부하며 배운내용 계단 오르기 계단을 한 칸씩 or 두 칸씩 올라간다. 계단을 오르는 경우의 수를 구하는 문제 입력 계단의 높이 N이 입력된다. 예) 4 출력 N까지 경우의 수 출력 예) 5 계단 높이 4의 경우의 수는 이렇게 되겠다 1칸 - 1칸 - 1칸 - 1칸 1칸 - 1칸 - 2칸 1칸 - 2칸 - 1칸 2칸 - 1칸 - 1칸 2칸 - 2칸 풀이 방법 문제를 보고 이해가 안되는 알고리즘은, 작은 숫자를 대입해보고, 규칙을 찾으려고 해봐야 되는 것 같다. 밑에 풀이 방법을 적어놨지만, 어떻게 이런 방법으로 계단 오르는 방법의 수가 나오는지 이해는 안가고 놀랍기만 하다. 그럼 규칙을 찾아보자 계단의 높이가 1일 때 올라갈 방법은 1 2일 때 올라갈 방법은 1칸 1칸 그리고 한번에 2칸 그래서..

알고리즘 공부하며 배운내용 마트 계산대 마트에는 여러 대의 계산대가 있다. 손님들이 계산을 마치는 데 얼마나 걸리는지 궁금하다. 어떤 계산대는 빨리 끝나고, 어떤 계산대는 오래 걸린다. 그래서 비어있는 계산대로 가는 것보다, 빨리 끝나는 계산대에 기다리는게 더 빠른 경우도 있다. 예를 들어 6명의 손님이 5분, 7분 걸리는 계산대에 있다고 해보자. 5분 계산대가 3명 => 15분 7분 계산대가 2명 => 14분 여기서 남은 1명이 7분 계산대로 가면 21분 1분 기다려서 5분 계산대로 가면 20분에 끝난다. 즉 20분이면 계산이 다 끝난다 입력 두 줄을 받는다. 첫번째 줄: 손님 수 N 두번째 줄: 각 계산대에서 걸리는 시간이 공백으로 구분 예) 6 5 7 출력 모든 손님이 계산이 끝나는 최소 시간 핵심..