분류 전체보기172 BOJ 1799 - 비숍 (🔄) https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 접근 방법 10초라고해서 기존 백트래킹을 이용했는데 10X10에선 시간초과가 났다. 비숍을 둘 수 있는 곳을 따로 저장하여 recursion 속 for문에서 사용하였는데 , 중복되는 부분이 많았다. recursion을 비숍을 둘 수 있는 곳을 기준으로 도는 것이 아니라 x,y를 기준으로 돌면 좋겠다는 생각을 하루동안 하지 못했다... 따라서, 다른 블로그를 참고하였다. 문제의 핵심은 다음과 같다. 1. p.. 2024. 2. 29. BOJ 16987 - 계란으로 계란치기 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 접근 방법 전형적인 백트래킹 문제이다. 순서대로 계란을 집어, 나머지 계란 중 하나를 치면 되는 문제이다. 이 문제의 핵심은 조건문을 어떻게 작성하냐 이다. 내가 틀렸던 예제는 다음과 같다. 3 1 4 8 1 3 1 // 정답: 2 손에 든 계란 외에 모든 계란이 깨진 경우를 체크해주지 않아 답이 1이 나왔다. 이를 bool flag를 통해 쉽게 수정하였다. 코드 #include #.. 2024. 2. 28. [그리디 #21] BOJ 7570 - 줄 세우기 https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 1차 시도 처음에 이걸 그리디로 해결하기 위해서 다음과 같이 생각했다. 1. 앞으로 옮겼을 때, 뒤쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야한다. 2. 뒤로 옮겼을 때, 앞쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야 한다. 그러나 이것은 금방 틀리다는 것을 알 수 있다. 가령 1,2번이 맞다고 하더라도 순서대로 이어져있지 않으면 문제가 된다. 따라서, 순서를 집중해서 공략하는게 좋겠다고 .. 2024. 2. 27. [그리디 #20] BOJ 2212 - 센서 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 접근방법 저번에 풀었던 행복유치원과 같은 문제이다. 예제 2번을 보면서 한번 살펴보자. 10 5 10 5 20 3 14 6 7 8 18 10 12 15 해당 센서를 오름차순으로 정렬하면 다음과 같다. 3 6 7 8 10 12 14 15 18 20 이 세선들을 몇 개씩 묶어서 총 K개의 묶음으로 만들면 된다. 이때, 문제의 핵심은 센서 사이의 거리가 짧은 것을 위주로 선택해.. 2024. 2. 25. [백트래킹 #1] BOJ 15649 - N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 접근 방법 예전에 풀어봤던 백트래킹이 가물가물해져서 다시 N과 M 시리즈를 풀어보도록 해야겠다. 브루트포스에서 처음부터 시작하는 것 대신, 이전 단계로 복귀하여 행하는 것이다. 코드를 보면 쉽게 이해가 가능하다. https://www.youtube.com/watch?v=Enz2csssTCs 코드 #include #include #include #include #include #include #d.. 2024. 2. 23. [그리디 #19] BOJ 2812 - 크게 만들기 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 방법 심플하면서 어려운 문제이다. n자리 수에서 m개의 수를 제거하여 가장 큰 수를 만드는 문제이다. 예제 3번에 이 문제에 힌트가 있다. 4 1 7 7 2 5 2 8 4 1 에서 4개를 제거하여 775841 를 만들어야 한다. 핵심은 4와 1을 제거하여 7을 가장 높은 자릿수로 만들어야 한다는 것! 예전에 스택을 이용하여 괄호가 포함된 중위 표기법을 후위 표기법으로 고치던게 생각이 났다. 스택에 숫자들을 넣고, 현재 숫자보다 작은 숫자들은 제거하는 방식으로 진행하여 .. 2024. 2. 23. 이전 1 ··· 7 8 9 10 11 12 13 ··· 29 다음
