문제https://www.acmicpc.net/problem/9205 풀이최대 20병이 들어가는 맥주 한 박스를 들고 출발하여 50m마다 맥주를 한 병씩 마시면서 가야 할 때, 상근이네 집에서 페스티벌에 갈 수 있으면 "happy"를, 그렇지 않으면 "sad"를 출력한다.편의점 개수 + 3(편의점 개수, 상근이 집 좌표, 페스티벌 좌표 입력) 씩 인덱스를 증가시키면서 테스트 케이스를 입력받는다.한 박스에 20병을 넣을 수 있고, 50m마다 맥주 한 병을 마셔야 하기 때문에 최대 이동할 수 있는 거리는 20x50=1000m이다. 따라서 서 맥주를 채울 수 있는 편의점까지 이동할 때, 또는 도착지인 페스티벌 좌표까지 이동할 때 거리가 1000m가 넘어가면 갈 수 없다.편의점을 무조건 순서대로 방문하는 것이 ..
문제https://www.acmicpc.net/problem/16946 풀이모든 1에서 BFS를 돌면 (NM)^2으로 시간초과벽 주변의 0 묶음의 개수를 더하면 이동할 수 있는 영역이다.따라서 이동 가능한 영역인 0 묶음의 개수를 세어 주변 벽인 1에 더해준다.모듈러 연산의 분배법칙을 생각하고 매번 나눠주는 경우, board 원본 배열의 벽을 증가시키다 10의 배수가 되는 경우 0이 되어 벽으로 인식하지 못하는 문제가 생기므로 유의해야 한다. 시간복잡도: O(NM)class Queue { constructor() { this.data = []; this.head = 0; this.tail = 0; } push(item) { this.data[this.tail++] = item;..
문제https://www.acmicpc.net/problem/15683 15683번: 감시스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감www.acmicpc.net 풀이각 cctv 위치에서 4방향으로 돌면서 cctv 유형에 따라 가능한 칸까지 탐색한다.시작점은 정해져 있기 때문에 DFS는 index만 넘겨준다.탐색(watch)은 cctv 유형에 따라 확인할 방향 dirToWatch를 정하고, 해당 방향으로 벽을 만날 때까지 이동한다. board 자체가 DFS를 돌면서 계속 변경되기 때문에 DFS 전후로 board를 깊은 복사 하여 사용한다. con..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이진 트리를 탐색하면서 양이 늑대에게 잡아먹히지 않도록 하는 양의 최댓값을 구하는 문제이다. 방문한 늑대 노드의 수가 방문한 양 노드 수 이상인 경우 늑대는 양을 모두 잡아먹는다. 트리 전체를 탐색하면서 방문한 양과 늑대 개수를 세야하고 info의 최댓값도 작기 때문에 DFS 문제이다. 하지만 일반적인 DFS와 다르게 노드를 재방문해야 하는 경로가 있기 때문에 어려웠다. 예를 들어, 예..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/43164# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 주어진 항공권을 모두 이용해 여행경로를 짤 때, 방문하는 공항 경로를 구하는 문제이다. 이때 주의할 점은 가능한 경로가 여러 개 있다면, 알파벳 순서가 앞서는 경로를 반환해야 한다는 것이다. 이 조건을 만족하기 위해 tickets 배열을 먼저 정렬해준다. 자바스크립트 sort는 기본적으로 알파벳 오름차순 순서로 배열을 해주고, 2차원 배열의 경우 첫 번째 요소가 같은 경우, 두 번째 ..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 반복해 읽으면서 라이언이 화살을 (어피치 개수 + 1) 또는 0개의 화살을 쏠 수 있을 거라고 생각했다. 이 경우, 화살을 쏘거나 쏘지 않거나의 2가지 경우^최대 레벨 = 10으로 1024가 최대 가지수이므로, DFS를 생각했지만 어려워서 이 블로그를 참고해 이해하였다. 크게 보면, 1. 화살을 쏠 때마다 현재 점수와 정답 배열(점수 당 사용한 라이언의 화살 개수 배열)을 갱신하..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 트럭에 최대 cap개의 택배를 실을 수 있고, 집마다 배달/수거할 택배 상자의 개수가 있을 때, 모든 택배를 처리할 수 있는 최소 이동 거리를 구하는 문제이다. 배달/수거가 필요한 가장 먼 지점까지 이동하고, 이후 초기 지점으로 돌아와야 하기 때문에 이동 거리는 Math.max(배달 최대 거리, 수거 최대 거리)의 2배가 된다. deliveryP와 pickupP는 각각 배송/수거해야하..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/150368?language=javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 function solution(users, emoticons) { /** 1. 이모티콘마다 다른 할인율을 적용했을 때, 유저 이모티콘 구매 비용과 서비스 가입 여부를 확인 2. 전체 구매 비용, 서비스 가입자 수를 확인 3. 서비스 가입자 수가 더 많거나 || (가입자 수는 같고 && 이모티콘 구매비용 더 많으면) 답 교체 */ const disc..
