본문 바로가기

분류 전체보기

 (386)
[boj] 백준 1342 행운의 문자열 [문제] https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net [풀이] 문자열의 길이가 최대 10이어서 전부 확인해도 시간 내 해결이 가능하다. next_permutation 이라는 함수를 이용하는데, 이는 순열을 구하고 싶은 1-2-3-4의 배열이 있다고 가정했을 때 다음 순열인 1-2-4-3로 바뀌고 true를 반환해주는 함수이다. [코드] #include #include #include using namespace::std; int main() { ..
[boj] 백준 1389 케빈 베이컨의 6단계 법칙 [문제] https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net [풀이] BFS로 분류되어 BFS로 풀었으나 Floyd-Warshall Algorithm을 이용하는 방법도 있다고 한다. 이게 더 쉬울 것 같은데 이렇게도 한 번 풀어봐야겠다.. bfs 코드를 그대로 이용하면 되는데, 연결된 다리의 누적합을 구해서 비교해야 하므로 connect 배열에 연결 다리 수를 저장하도록 했다. [코드] #includ..
[c++] 백준 1309 동물원 - 동적계획법 [문제] https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net [풀이] dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] i번째 행에 사자를 배치하지 않는 경우, i-1행에 어떤 식으로 사자를 배치해도 상관없다. dp[i][1] = dp[i-1][0] + dp[i-1][2] i번째 행 왼쪽에 사자를 배치할 경우, i-1행에 사자를 배치하지 않거나 오른쪽에만 배치해야 한다. dp[i][2] = dp[i-1][0] + dp[i-1][1] i번째 행 오른쪽에 사자를 배치할 경우, i-1행에 사자를 배치하지 않거나 왼쪽에만 배치해야 한다. [코드] #in..
[c++] 백준 1263 시간 관리 - 그리디 [문제] https://www.acmicpc.net/problem/1263 1263번: 시간 관리 진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다. 진영 www.acmicpc.net [풀이] 그리디 알고리즘. 가장 늦게 끝내도 되는 시간 순으로 내림차순 정렬을 한다. 그 후 끝내야 하는 시간이 더 작으면 계속 갱신해준다. 예를 들어, 아래 테이블의 경우 가장 늦은 시간은 20시이다. 3 5 8 14 5 20 1 16 해당 일은 5시간이 걸리므로 20-5=15, 즉 적어도 15시에는 시작해야 한다. 만약 그 전 일인 16시까지 끝내야 하는 일을딱 16시에 맞춰서 끝냈다면..
[c++] 백준 1254 팰린드롬 만들기 - 투포인터 [문제] https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net [풀이] 문제를 잘 읽자....문자열 뒤에만 추가할 수 있단다. 그걸 못보고 insert로 중간 삽입해서 풀다가 왜 계속 틀리는 거지??? 멘붕 왔는데...뻘짓했다... 먼저 맨 처음 문자부터 맨 마지막까지 팰린드롬이 되는지를 확인하고 팰린드롬이 되는 첫번째 인덱스를 찾는다. 그럼 전체 문자열 길이+팰린드롬이 되는 첫번째 인덱스 값이 답이 된다. 예를 들어, aabcaa의 경우 마지막 aa만 ..
[c++] 백준 1174 줄어드는 수 [문제] https://www.acmicpc.net/problem/1174 1174번: 줄어드는 수 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는 www.acmicpc.net [풀이] 여러 사람의 코드를 참고해서 풀었는데...이런 생각 도대체 어떻게 뚝딱뚝딱 하는지... 먼저 줄어드는 수 중 가장 최대값은 9876543210이다. 즉 모든 수가 중복될 수 없으므로 경우의 수는 2^10 = 1024 밖에 안된다는 것. 따라서 줄어드는 수에 해당하는 모든 값을 구한 후 정렬하고, n번째에 해당하면 그 수를 출력 그 범위를 넘어서면 -1을 출력하면 된..
[c++] 백준 1106 호텔 - 동적계획법 [문제] https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net [풀이] 동적계획법(dp) 문제이다.(dp에 대한 감을 아예 잃어서 뻘짓만 했다...) dp[i] = i만큼의 비용을 들여 확보할 수 있는 최대 고객 수 라고 해보자. C는 최대 1000이고, 도시를 홍보하는 최대 비용은 100이다. 100에 고객 1명을 확보할 수 있다면 1000명의 고객을 확보하는데 필요한 비용, dp의 최대 크기는 1000*100+1이 된다. 따라서 dp[1000..
[c++] 백준 1052 물병 [문제] https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net [풀이] 2의 거듭제곱은 하나의 물병으로 합칠 수 있는 수이다. 64 = 32+32 = 16+16+16+16 = ... = 1+1+.....+1 이기 때문에 한 병으로 만들 수 있다. 따라서 가능한 최대의 2의 거듭제곱 수를 구한 후 n에서 빼주고 동시에 k도 1씩 감소시켜준다. k가 1이 될 때까지 위의 과정을 반복한 후, k가 1이 되면 남아있는 n이 물병 한 개로 옮길 수 있는 2의 거듭..

티스토리툴바