본문 바로가기

전체 글

 (126)
[프로그래머스] 카펫 ▶문제설명코딩테스트 연습 > 완전탐색 > 카펫https://programmers.co.kr/learn/courses/30/lessons/42842 ▶ 설계brown와 red의 값에 따라서 카펫의 가로, 세로 크기를 리턴해야 하는 함수이다.단순히 가능한 가로, 세로의 길이를 2중 for문으로 완전탐색하면 풀릴 것으로 보인다. ▶ 구현우선 2중 for문으로 가능한 가로, 세로 길이를 모두 탐색하도록 하자. 123456789vector solution(int brown, int red) { vector answer; for(int w=1; w
[프로그래머스] 단어 변환 ▶문제설명코딩테스트 연습 > DFS/BFS > 단어 변환 https://programmers.co.kr/learn/courses/30/lessons/43163 ▶ 설계DFS 탐색으로 문제를 해결해보자. 한 번에 한 개의 알파벳만 바꾸어서 word에 있는 단어 중 하나로 변환할 수 있는지 모든 경우를 탐색해보면 되는 문제이다. 복잡한 것 없이 문제에서 요구하는데로 재귀 함수만 잘 구현하면 간단히 해결될 것으로 보인다. ▶ 구현 우선 재귀함수의 매개변수와 리턴타입을 정해보자. 12345int findWord(string nowWord, const string& targetWord, const vector& words, int cnt){ int answer = 987654321; return answer;}C..
[프로그래머스] 소수 찾기 ▶문제설명코딩테스트 연습 > 완전탐색 > 소수 찾기 https://programmers.co.kr/learn/courses/30/lessons/42839 ▶ 설계number의 길이를 n이라고 하자. n개의 숫자들 중에 1 ~ k 개를 뽑아서 순열을 생성한 뒤 정수로 변환하고 해당 정수가 중복되지 않도록하여 소수인지 아닌지 판별해서 개수를 반환하는 함수를 구현해야 한다. 조합의 경우에는 순서를 고려하지 않고 k개를 뽑아내므로 조합만으로는 풀 수 없다. (간단히 예를 들면 1, 3, 2 를 뽑아낼 뿐이지 132, 123, 213, 231, 312, 321와 같이 순열을 뽑아내는 방법이 아니기 때문이다.) n개의 숫자들 중 k개를 뽑아서 순열을 만들기 위해서 재귀함수를 구현하면 될 것으로 보인다. 123456..
[프로그래머스] 다리를 지나는 트럭 ▶문제설명코딩테스트 연습 > 스택/큐 > 다리를 지나는 트럭 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..
지레짐작하지 말 것 ▶문제 ( [BOJ] 백준. 2891 카약과 광풍 )2890번을 보면 알겠지만, 상근이는 카약 대회를 개최했다. 그런데, 갑자기 엄청난 강풍이 경기장에 불었고, 일부 카약이 부서졌다. 경기는 5분 안에 시작해야 하는 상황이다. 다행히 일부 팀은 혹시 모를 사태에 대비해서 카약을 하나 더 경기장에 들고 왔다. 카약은 매우 무겁고 운반하기 어렵다. 따라서, 자신의 바로 다음이나 전에 경기하는 팀에게만 카약을 빌려주려고 한다. 즉, 팀 4는 여분의 카약을 3이나 5에게만 빌려줄 수 있다. 또, 카약을 하나 더 가져온 팀의 카약이 손상되었다면, 여분의 카약으로 경기에 출전하게되고, 이 카약은 다른 팀에게 빌려줄 수 없다. 카약이 부서진 팀과 하나 더 가져온 팀이 주어진다. 카약을 적절히 빌렸을 때 출발하지 못하..

티스토리툴바