프론트엔드 개발자의 기록 공간

백준 그리디 알고리즘 1449번_수리공 항승 난이도 : 실버III 문제 설명 입출력 또다른 입출력 예시: 3 3 4 5 9 답 : 2 7 4 1 2 3 4 10 15 20 답 : 4 문제 풀이 : 좌우 0.5 간격때문에 무지 헷갈렸다. 하지만 그냥 테이프의 길이(L) -1 이라고 생각하면 훨씬 편하다. 구멍난 위치를 기준으로 테이프를 붙이면 구멍난 위치 + 테이프의 길이 -1 만큼이 테이프가 붙여진 길이가 된다.(이를 fix범위라고 지칭) 즉, 테이프가 붙여진 길이안에 포함되어있는 구멍들은 자동으로 수리가 된 셈이다. 이 방식을 이용해서 풀면된다. 우선 구멍난 위치를 순차적으로 해결하기 위해 정렬을 해준다. 이 후, 반복문을 통해 fix범위보다 큰 경우(테이프의 범위를 벗어난 경우) 새 테이프를 추가하여..

백준 그리디 알고리즘 2437번_저울 난이도 : 실버V 문제 설명 입출력 문제 풀이 : 이 문제의 핵심은 병든 나이트의 이동방법이 항상 오른쪽 방향으로 움직인다는 것입니다. 여기서 최대 방문할 수 있는 최대 개수를 구해야합니다. 이동 횟수가 5가지 미만이면 1~4중에 마음대로 사용하면 됩니다. 이동 횟수가 5가지 이상이면 1~4를 모두 최소 1번씩은 사용해야합니다. (여기서 핵심을 적용시켜야한다.) 그럼 횟수가 5가지 이상에서는 1~4를 모두 써야하는데 나이트는 항상 오른쪽 방향으로 움직이니깐 오른쪽의 움직임을 최소화 하기 위해 2칸씩 움직이는 2,3번은 한번만 이동하고 나머지를 1,4번으로 반복해주면됩니다. 즉, 4가지 경우로 분류 1. 세로길이가 1일때 2. 세로길이가 2일때 3. 세로길이 3이상 가..

백준 그리디 알고리즘 2437번_저울 난이도 : 골드III 문제 설명 입출력 문제 풀이 : 약간의 수학적 지식이 필요한 문제인거 같다. 맨처음에 모든 경우의 수를 다 구해서 풀어야하는줄 알았다.. 다른 블로그를 참고하니 그렇게 접근하는 것이 아니였다.ㅠㅠㅠ 우선 추를 오름차순으로 정렬해준다. 그 후 반복문을 현재 추의 무게와 누적합 +1 값을 비교해준다. 누적합 +1 이 현재 추보다 크거나 같다면 이는 누적합 +1 까지 표현이 가능하다는 의미이다. 누적합 +1이 현재 추보다 작다면 이는 표현이 불가능하다는 것을 의미한다. //골드3 저울 function solution(n, list) { //오름차순 list.sort(function(a,b){ return a - b; }) let sum = 0; for..

백준 그리디 알고리즘 4796번_캠핑 난이도 : 실버V 문제 설명 입출력 문제 풀이 : 문제를 쉽게 해석하면 P영업일 동안 L일만 사용할 수 있다. 즉 P가 8, L이 5라고하면 1~8일중 5일만 사용할 수 있고 그다음 9~16일중 5일 사용할 수 있다는 의미이다 즉 영업 쿨타임(?)이 8일이라는 소리이다. 그래서 알고리즘을 휴가일수가 영업일보다 클때까지 휴가일수 - 영업일을 빼면서 사용일수를 카운트 해주면된다. 휴가일수가 영업일 보다 작을때는 휴가일수와 사용일수를 비교하여 더 작은값을 넣어줘야한다. //실버 5 캠핑 function solution(list) { let L = 0; //L일 동안 let P = 0; //P일 중 let V = 0; //휴가 일수 let cnt = 0; //이용 일 수 f..

백준 그리디 알고리즘 1138번_한 줄로 서기 난이도 : 실버IV 문제 설명 입출력 문제 풀이 : 맨 처음에 문제를 읽었을때 이 문제가 골드나 된다고 의심을 품었다. 겉으로 보기에는 너무나 쉬웠다. 하지만 여러가지 고려해야할 사항들이 있다는 것을 나중에 알았다. 고려해야할 사항 : 음수들의 곱셈은 양수가 된다!, 1은 덧셈이 더 큰 결과값이 된다!, 0는 양수와 계산할때는 덧셈, 음수와 계산할때는 곱셈!을 해줘야 최대값이 나온다. 실패한 첫번째 풀이 방법 : 주어진 입력을 큰 수대로 내림차순 정렬후 반복문을 통해 첫번째 수는 tmp변수에 저장하고 두번째 변수가 나오면 tmp와 곱셈, 덧셈을 각각 한 후 큰 값을 result로 넣어주었다. (*리스트의 길이가 홀수인 경우도 처리해주었다.) 이렇게 해서 테스..

백준 그리디 알고리즘 1138번_한 줄로 서기 난이도 : 실버II 문제 설명 입출력 문제 해설 : 이 문제의 핵심은 입력으로 주어지는 순서가 "키의 순서"이다. 그리고 해당 값이 왼쪽에 몇명있는지를 나타내는 숫자이다. 즉 입력예제 2 1 1 0은 키1인 사람의 왼쪽에는 자신보다 큰 두명이 있고 키 2인 사람의 왼쪽에는 자신보다 큰 한명이있고 키3인 사람의 왼쪽에는 자신보다 큰 한명이 있고 키 4인 사람은 자신보다 큰 왼쪽의 사람은 0명이 있다는 의미이다. // 실버2 한 줄로 서기 function solution(n, list) { let result = new Array(n).fill(0); //i는 키 순서를 의미(1부터~) for(let i=1; i

백준 그리디 알고리즘 1080번_행렬 난이도 : 실버II 문제 설명 입출력 문제 풀이 : 행렬 A, B가 주어졌을때 A를 B로 바꾸는 최소 횟수를 구하면 된다. 행렬 변환시는 3*3만 가능하다는것이 중요한 포인트이다. A B C D E 0 0 0 0 F 0 0 1 0 G 0 0 0 0 A~G는 행열을 구분하기 편하게 임의로 지정한것이므로 무시해도 좋습니다. 입출력으로 주어진 예제는 3*4 행렬이다. 하지만 행렬 변환은 3*3이다. 3*3변환을 이용하여 3*4를 행할려면 2번을 수행해야한다. 한번 수행할때 A,E 지점부터 C,G지점까지 가능하다. 그러면 G지점이 아직 수행되지않았다. 그 다음엔 B,E지점부터 D,G지점까지(3*3)을 행하면 두번의 연산이 가능하다. 하지만 문제에서 최소 횟수를 구해야하므로 ..