■ 알고리즘 문제 풀이 (74) 썸네일형 리스트형 [프로그래머스] 다리를 지나는 트럭 ▶문제설명코딩테스트 연습 > 스택/큐 > 다리를 지나는 트럭 https://programmers.co.kr/learn/courses/30/lessons/42583 ▶ 설계트럭을 구조체로 관리하자. 그리고 다리 위에 있는 트럭들을 queue 자료구조로 관리하자. 여러 대의 트럭이 한 시간에 동시에 다리 위로 올라가는 경우는 없으니 도착할 시간이 중복되는 경우는 없다. 시간을 1초씩 증가시키면서 모든 트럭들이 다리를 지날 때까지 반복하면 될 것으로 보인다. commingTrucksQ의 front에 있는 트럭이 도착할 시간이 되었을 때 하나씩 pop해주자. 그러기 위해서 구조체에 도착 시간을 나타내는 arrivedTime이 필요하다. 또한, 다리 위에 올라와있는 트럭이 빠져나갈 때 그 트럭의 무게를 알아야 현.. [프로그래머스] 여행경로 ▶문제설명코딩테스트 연습 > 깊이/너비 우선 탐색 > 여행경로 https://programmers.co.kr/learn/courses/30/lessons/43164 ▶ 설계재귀 함수를 잘 구현하면 해결할 수 있을 것 같다. 재귀 함수의 종료 조건은 모든 티켓을 다 사용했을 경우이다. 전역변수 N에 티켓의 개수를 저장하자. 12345678bool findPath(vector& answer, vector tickets, string city, int cnt) { if(N==cnt) return true; return false; }Colored by Color Scriptercs 문제에서 경로가 여러개인 경우 사전순으로 빠른 경로를 출력하라고 했으므로 sort(tickets.begin(), tickets.e.. [프로그래머스] 기능개발 ▶문제설명코딩테스트 연습 > 스택/큐 > 기능개발 https://programmers.co.kr/learn/courses/30/lessons/42586 ▶ 설계0%로 시작하고 하루에 1%를 채울 수 있는 작업이 있다면 100일이 필요하다. 그러므로 100번 반복하는 루프문 안에서 구현을 이어나가면 되겠다. 완료된 작업이 있는지 확인하기 위한 구간을 begin과 end로 나타낸다. [begin, end) 매일 begin에서부터 연속되어 있는 진행률 100% 이상의 작업들을 확인하고 answer에 추가한 뒤, begin을 업데이트 해주자. ▶ 구현 하루가 지날 때마다 입력으로 주어진 모든 작업들을 주어진 속도에 맞추어 진행률을 업데이트했다. 그리고 begin에 위치한 작업이 100% 이상이 된 경우에 beg.. [BOJ] 백준 15683. 감시 ▶문제설명[BOJ] 백준 15683. 감시 https://www.acmicpc.net/problem/15683 ▶ 설계NxM 크기의 사무실에 K개의 CCTV가 설치되어있다. (1 [BOJ] 백준 17143. 낚시왕 ▶문제설명[BOJ] 백준 17143. 낚시왕https://www.acmicpc.net/problem/17143 ▶Hint[삼성전자 상시 SW역량테스트-A형] 시뮬레이션 문제이다. 1. 낚시왕을 오른쪽으로 한칸 이동시킴2. 상어를 낚음3. 상어들이 움직임 1~3 과정을 C번(문제에서 주어진 열의 크기만큼) 수행하면 답을 구하게 되는 문제이다. 상어 구조체를 만들고 상어들의 상태와 위치를 2차원 배열로 관리했다. 3번에서 상어들이 움직일 때 예를 들어, 상어의 속력이 5인 경우 5번에 걸쳐 이동시키면서 매번 상어가 범위를 벗어났는지 파악하여 상태를 변경하는 방법으로 구현했다. 문제 해결에 있어 핵심이 되는 부분에 대해 설명하고자 한다. [구조체 선언]1234struct Shark { int s, d, z;}.. [BOJ] 백준 17471. 게리맨더링 ▶문제설명[BOJ] 백준 17471. 게리맨더링 https://www.acmicpc.net/problem/17471 ▶Hint 조합과 DFS를 이용한 부르트포스 문제이다. 문제 해결에 핵심이 되는 두 부분에 대해 설명하고자 한다. 1. 구역 번호 1~N을 두 개의 선거구로 나눈다.[구역 번호를 두 개의 선거구로 나누는 모든 경우의 수]구역 번호 1~N에서 1개를 선택해서 선거구 A라고 하고 나머지 구역 번호 N-1개를 선거구 B라고 한다. (nC1가지 경우) 구역 번호 1~N에서 2개를 선택해서 선거구 A라고 하고 나머지 구역 번호 N-2개를 선거구 B라고 한다. (nC2가지 경우) 구역 번호 1~N에서 3개를 선택해서 선거구 A라고 하고 나머지 구역 번호 N-3개를 선거구 B라고 한다. (nC3가지 경.. [BOJ] 백준 16234. 인구 이동 ▶문제설명[BOJ] 백준 16234. 인구 이동 https://www.acmicpc.net/problem/16234 ▶Hint DFS, 시뮬레이션 문제이다. 인구 이동이 일어났다는 것은 한 시점에 인구 수 변동이 한 번 이상 있었다는 것을 의미한다. 한 번에 모든 연합이 동시에 인구이동을 실시하기 때문에 순차적으로 인구이동을 시키지 않도록 주의한다. [입력]3 5 10 10 15 20 20 30 25 40 22 10이런 입력이 들어왔다고 했을 때 인구 이동이 한 번 일어난 뒤의 상태는 아래와 같다. 20 20 20 20 20 20 40 20 10 ▶SolutionDFS 알고리즘을 이용해 각 연합의 전체 인구 수와 연합을 이룬 칸의 개수를 구해서 평균 값을 구한다. DFS를 수행하면서 좌표 값을 저장해두면.. [BOJ] 백준 1722. 순열의 순서 ▶문제설명[BOJ] 백준 1722. 순열의 순서 https://www.acmicpc.net/problem/1722 ▶Hint 조합론 & DP 문제이다. 입력으로 주어지는 N의 범위가 최대 20이다. 20! = 2,432,902,008,176,640,000 따라서 브루트포스로 접근할 경우 TLE가 발생하며, 결과 값이 int 자료형 범위를 넘어간다. 문제를 해결함에 있어서 중요하게 봐야 할 조건은 순열이 사전 순으로 정렬되어 있다는 것이다. 이 조건 덕분에 우리는 모든 경우를 확인해보지 않고도 K번째 순열을 찾아내거나 주어진 순열이 몇 번째 순열인지를 알아낼 수 있다. N이 4인 경우를 예로 들어보겠다. 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2.. 이전 1 2 3 4 5 6 ··· 10 다음