본문 바로가기

알고리즘119

[백준] 스타트와 링크 JS풀이 https://www.acmicpc.net/problem/14889 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.N=.. 2024. 4. 25.
[백준] 2493번 탑 JS 풀이 문제링크KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높.. 2024. 4. 25.
[백준] 쇠막대기 https://www.acmicpc.net/problem/10799 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다... 2024. 3. 14.
[백준] 괄호 추가하기 3 JS풀이 문제링크: https://www.acmicpc.net/problem/16639 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계산 해야 한다. 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 41이다. 수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 예를 들어, 3+8×7-9×2에 괄호를 (3+8)×7-(9×2)와 같이 추가했으면, 식의 결과는 59가 된다. 중첩된 괄호도 사용할 수 있고, 괄호 안에 여러 개의 연산자가 들어 있어도 된다. 즉, 3+((8×7)-9)×2, 3+((8×7).. 2024. 2. 26.
[프로그래머스] 가장 긴 팰린드롬 https://school.programmers.co.kr/learn/courses/30/lessons/12904# 풀이 abbc, abcba 인 경우를 잘 살펴보면 첫번째는 b와 바로 다음 b가 같으므로 펠린드롬 시작, 두번째는 b와 다다음 b가 같아서 펠린드롬이 시작한다. 정리하자면 s 왼쪽부터 순회하면서 현재 = 현재의 다음 혹은 현재 = 현재의 다음다음인 경우에만 팰린드롬 가능성이 있는지 확인하면 된다 s.length-2까지 순회하며 펠린드롬이 가능한 경우를 찾는다 현재 = 다음 인 경우 getPalinLen를 구한 뒤 바로 이전의 result와 max 비교 현재 = 다음다음 인경우 getPalinLen + 1와 이전의 result비교한다 (1은 중간에 낀 문자) getPalinLen은 팰린드롬을.. 2024. 2. 22.
[프로그래머스] 단속 카메라 https://school.programmers.co.kr/learn/courses/30/lessons/42884 첫번째 풀이 // 한번은 만나게 최소 몆대 설치해야함? function solution(routes) { // 빨리 나간 순으로 정렬 routes.sort((a, b) => a[1] - b[1]); const camera = [routes[0][1]]; // 첫번째 카메라 for (let i = 1; i < routes.length; i++) { const [start, end] = routes[i]; // 이전의 카메라를 만난적 없음 카메라 추가 if (!isMet(start, end, camera)) { camera.push(end); } } return camera.length; } f.. 2024. 2. 21.

티스토리툴바