시뮬레이션 64

[Programmers] 양과 늑대

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 비트마스킹과 백트래킹을 통해 풀 수 있는 문제였습니다. 사실 모든 가능한 상태에 대해 시뮬레이션을 진행하고 이 중 양 개수가 가장 높은 케이스를 찾는 방법이라 별도로 설명할 알고리즘은 없고 비트마스킹을 어떻게 활용할지 간단하게 설명하겠습니다. 노드 개수가 최대치인 17개라고 가정했을 때 처음 상태는 루트 노드만 방문한 상태인 00,000,000,000,000,001 루트 노드와 ..

[PCCP 기출문제] 4번 / 수레 움직이기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/250134 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 재귀함수와 BFS 알고리즘을 통해 풀 수 있는 문제였습니다. 알고리즘은 아래와 같습니다. 1. maze 벡터를 순회하며 빨간색 수레와 파란색 수레가 위치한 좌표를 구하고 해당 좌표를 각각 빨간색과 파란색 수레가 위치했었다고 visited 배열에 표시를 합니다. 2. 각 수레는 상하좌우로 움직일 수도 있고 가만히 서있을 수도 있습니다. 2.1 각 턴마다 두 수레 모두 움직이지 않..

[PCCP 기출문제] 2번 / 석유 시추

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/250136 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단하게 풀 수 있는 BFS 문제였습니다. 시추관을 수직으로 꽂기 때문에 각 x 좌표마다 석유를 얼마나 뽑을 수 있는지 구하면 되는 문제였습니다. 알고리즘은 아래와 같습니다. 1. land 이차원 벡터를 순회하며 BFS 알고리즘을 통해 뽑을 수 있는 석유의 양을 구합니다. 1.1 핵심은 각 x 좌표마다 석유를 얼마나 뽑을 수 있는지를 구하는 것이기 때문에 1번에서 구한 석유의 ..

[Programmers] 2차원 동전 뒤집기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/131703 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 비트마스킹으로 풀 수 있는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 첨부하는 그림에서 볼 수 있다시피 beginning을 target으로 바꾸기 위해 뒤집을 열과 행을 정하는 것이 중요하지 뒤집는 순서는 중요하지 않습니다. 2. 열과 행의 길이가 각각 최대 10이기 때문에 모든 경우의 수를 구해도 O(2^20 * 20)입니다. 따라서 모든 경우의 수를 테스트한 뒤 답을 ..

[Programmers] 과제 진행하기

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/176962 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 스택을 이용한 시뮬레이션 구현 문제였습니다. 알고리즘은 아래와 같습니다. 1. 시작 시간을 쉽게 비교하기 위해 시작 시간을 분 단위로 전처리하고 map 자료구조를 통해 해당 시작 시간에 매칭되는 과제를 매핑합니다. 1.1 이때 가장 빠른 시작 시간도 구해줍니다. 2. 가장 먼저 진행해야 할 과제부터 순차적으로 진행하는데 문제에서 주어진 조건대로 해당 과제를 마무리하기 전 새로운..

[Programmers] 리코쳇 로봇

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 우선순위 큐를 이용한 BFS 문제였습니다. 알고리즘은 아래와 같습니다. 1. 이동한 횟수가 적을수록 우선순위가 큰 우선순위 큐에 로봇의 시작점 좌표와 이동한 횟수인 0을 넣어줍니다. 2. 우선순위 큐가 빌 때까지 혹은 목표점에 도달할 때까지 상하좌우 방향으로 부딪힐 때까지 이동시키며 시뮬레이션을 돌립니다. 2.1 목표점에 도달했다면 이동한 횟수를 반환합니다. 3. 2번 과정에서..

[Programmers] 공 이동 시뮬레이션

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/87391 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 주어진 쿼리의 역순으로 계산하면 AC를 받을 수 있는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 열과 행의 범위를 나타내는 pair 변수를 선언하고 주어진 쿼리의 역순으로 진행합니다. 1.1 역순이므로 문제에서 주어진 방향은 반대가 되어야 합니다. ex) query(0, dx) -> 열 번호가 증가하는 방향으로 이동하는 쿼리로 치환 1.2 또한, 정방향으로 쿼리를 진행했을 ..

[Programmers] 사라지는 발판

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/92345 코딩테스트 연습 - 사라지는 발판 [[1, 1, 1], [1, 1, 1], [1, 1, 1]] [1, 0] [1, 2] 5 [[1, 1, 1], [1, 0, 1], [1, 1, 1]] [1, 0] [1, 2] 4 programmers.co.kr 비트 마스킹을 연습하기 좋은 문제였습니다. 알고리즘은 아래와 같습니다. 1. 주어진 board 정보를 기반으로 boardBit을 생성합니다. -> ex) [[1, 1, 1], [1, 0, 1], [0, 1, 1]]이 주어졌을 경우 boardBit는 111101011을 십진수로 변환한 값 2. 재귀함수 func는 매개변수 {y, x}에 위치한 사람..

[Programmers] [1차] 셔틀버스

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 문제에서 주어진대로 풀면 되는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 예제를 보면 timetable이 정렬되어 있지 않기 때문에 시간 오름차순으로 정렬을 진행합니다. 2. timetable의 크기가 최대 2,000이므로 브루트..