티스토리

개발도사무도사

검색하기

블로그 홈

개발도사무도사

gaebaldosamoodosa.tistory.com/m

개발도사(진) 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

[Sliding Window] 백준 2531: 회전 초밥 https://www.acmicpc.net/problem/2531 정직하게, k개의 연속된 초밥을 고르고, 이들을 vector에 넣어 이미 고른 초밥인지 확인하고, 쿠폰 초밥에 대해서도 같은 논리를 적용해서 문제를 풀면 시간 초과가 난다. #include #include #include #include using namespace std;int N, d, k, c;int answer=INT_MIN;int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>N>>d>>k>>c; vector sushies; int input; for(int i=0;i>input; sush.. 공감수 1 댓글수 1 2024. 12. 8.
[재귀] 백준 1780: 종이의 개수 https://www.acmicpc.net/problem/1780 별다른 트릭이나 색다른 접근법 없이 정직하게 재귀함수만 작성하면 되는 문제이다. base case 만 잘 지정해 주면 된다. 종이 크기가 한 장이면, 더 이상 나눌 필요가 없으므로 해당하는 숫자를 더해주고 재귀를 종료한다. if(size==1) { switch(paper[startRow][startCol]) { case -1: minusOneNum++; break; case 0: zeroNum++; break; case 1: one.. 공감수 0 댓글수 0 2024. 11. 29.
[순열,조합] 백준 2529: 부등호 2529번: 부등호 1. 0-9 까지 숫자 중 k+1 개를 골라 만들 수 있는 모든 '조합'을 구한다. 2. 1에서 구한 조합으로 구현 가능한 모든 '순열'을 구한다. 3. 부등호와 맞는지 비교한다. 먼저, 조합을 구하는 코드는 다음과 같이 구현했다. 모든 조합을 구해서, 그 조합들을 다시 vector> 의 vector 요소로 저장하였다.void makeCombination(vector> &combinations, vector &numbers, vector &currentComb, int start, int len){ if(currentComb.size()==len) { vector result; for(int i=0;i 그 다음, 다시 이 모든 조합들을 활용해 순열을.. 공감수 2 댓글수 1 2024. 11. 20.
[BFS] 백준 1012: 유기농 배추 https://www.acmicpc.net/problem/1012 배추흰지렁이는 그냥 문제를 더 풍부하고 재미있게 해 줄 요소일 뿐이고, 결국 '배추 클러스터 개수'를 묻는 문제이다. void bfs(vector> &farm, vector> &isVisited, int x, int y, int &answer){ queue> queue; if(farm[x][y]==1&&!isVisited[x][y]) { isVisited[x][y] = true; queue.push(pair(x,y)); answer++; } while(!queue.empty()) { pair currentCoord = queue.front(); .. 공감수 0 댓글수 0 2024. 11. 18.
[DP] 백준 11726: 2*n 타일 https://www.acmicpc.net/problem/11726 타일을 맞춘다고 표현했지만 결국 문제에서 요구하는 것은 '1과 2를 나열하여 n을 맞추는 경우의 수' 일 것이다. 가로가 2인짜리 블럭을 사용하면 그 아래도 꼼짝없이 같은 블럭으로 채워야지, 다른 경우가 있을 수 없기 때문이다. 맨 처음에 재귀함수를 이용한 시도에서는 (예제의) 정답은 다 맞췄지만 시간 초과가 났다. 그래서 시간을 줄이기 위해 memoization을 사용하기로 했다. 먼저 n=1인 경우는 ㅣ 한 가지 경우의 수밖에 없고, n=2인 경우는 ㅡ 한 가지 경우의 수밖에 없다면,n=3인 경우 ㅣㅣㅣ,ㅣㅣㅡ, ㅣㅡㅣ,ㅡㅣㅣ 4 가지 수가,n=4인 경우, ㅣㅣㅣㅣ,ㅡㅡ,ㅣㅣㅡ,ㅣㅡㅣ,ㅢㅣ 5가지 수가 존재한다. 여기서 f(n) =.. 공감수 0 댓글수 0 2024. 11. 17.
[이분탐색] BOJ 2512: 예산 https://www.acmicpc.net/problem/2512 예산 내에서 지자체가 요구한 예산들 다 커버할 수 있으면 지자체 중 요구한 예산이 가장 큰 지자체의 예산을, 그렇지 않으면 특정 상한선을 정해서 그 위로는 자르고, 전체 예산안을 만족할 수 있는 상한선 중 가장 큰 값을 반환하면 된다. 전자는 그냥 전체 요구 예산의 합이 예산 한도보다 낮으면 최대값을 반환하면 될 것이고, 후자 쪽이 binary search를 통해 상한선의 최대값을 찾아야 하는 문제이다. #include #include #include using namespace std;int answer;void findMaximum(vector &budget, int min, int max, int maxBudget){ if(mi.. 공감수 0 댓글수 1 2024. 11. 6.
[Greedy] 백준 4796: 캠핑 https://www.acmicpc.net/problem/4796 예전에 설탕 문제 풀었던 것을 기억하자. https://gaebaldosamoodosa.tistory.com/79 연속된 P일 중 L일만 사용 가능하다는 것을 일종의 큰 상자로 생각하자. 요컨대 박스 무게는 P이고 안에 포장 빼고 실제 내용물이 L 들어 있는 것이다. 그리고 남는 여분은 작은 상자로 포장된다고 생각하자. 큰 상자를 고르는 것이 다른 상자의 선택에 영향을 미치지 않고, 매 순간 가능하다면 작은 상자 대신 큰 상자를 선택하는 것이 결국 가장 많은 내용물을 가져가는 결과를 도출할 것이다. 다시 말해 한 단계의 선택의 다음 단계의 선택에 영향을 미치지 않고, 매 순간 최적의 해가 문제 전체의 최적의 해가 될 것이기 때문에 Gree.. 공감수 3 댓글수 2 2024. 10. 23.
[이분 탐색] 백준 2805: 나무 자르기 https://www.acmicpc.net/problem/2805 이분 탐색의 기본을 사용하는 문제이다. 먼저, 절단기 높이의 최소값은 0이고, 최대값은 나무들 중 가장 높은 나무의 높이이다. 따라서 초기에 min = 0, max = max(tree) 라고 하자. 우리가 구해야 할 것은 "원하는 만큼 나무를 가져갈 수 있는 절단기의 최대 높이" 이다. 따라서 절단기 높이에 따라 구할 수 있는 나무의 양이 요구치보다 적을 때는 절대 정답이 될 수 없되 절단기를 더 낮추어야 하므로, max = mid-1로 설정하고 다시 이분탐색을 진행한다. 반면 절단기 높이에 따라 구할 수 있는 나무의 양이 요구치보다 많을 때는 정답이 될 수 있되 절단기를 더 높여서도 해당하는 만큼의 나무를 구할 수 있는지 알아봐야 한다... 공감수 0 댓글수 0 2024. 10. 22.
[Simulation] 백준 14719: 빗물 14719번: 빗물 (acmicpc.net) 처음에는 각 column 간의 차이를 위주로 접근하다가, 위에서부터 한 row씩 훑고 내려오면서 연산하는 방식으로 접근을 달리했다. 맨 위 row 부터 순회하면서, 만일 값이 1인 칸을 이미 만난 상태라면 이후 0인 칸을 만날 때마다 값을 더해준다. 만일 다시 값이 1인 칸을 만나면, 해당 값을 정답에 더해주고 0으로 초기화한다. 양 옆이 뚫려 있다고 생각해야 하므로, 다음 row로 내려갈 때 값을 0으로 초기화한다. 이 때 1인 칸을 만났는지 여부를 확인하는 flag(여기서는 isFill)을 false로 초기화 해 준다.#include #include using namespace std;int main(){ ios_base::sync_with_stdio.. 공감수 0 댓글수 0 2024. 6. 8.
[BruteForce] 백준 14888: 연산자 끼워넣기 14888번: 연산자 끼워넣기 (acmicpc.net) 재귀함수 호출을 통한 완전탐색 문제이다. input A_1, A_2, ... , A_n 이 주어졌을 때, 다음과 같은 재귀호출을 통해 답을 구한다. #include #include #include using namespace std;int maxValue = -1000000000;int minValue = 1000000000;void recursion(int currentValue, int numIdx, vector&numbers, vector&operators){ if(numIdx>=numbers.size()) { maxValue = currentValue>maxValue?currentValue:maxValue; .. 공감수 0 댓글수 0 2024. 6. 2.
[수학] 백준 1629: 곱셈 1629번: 곱셈 (acmicpc.net) 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 그냥 (A^B)%C를 연산하면 풀 수 없다. 일단 범위를 벗어난다. 그래서 다음과 같은 modulo 연산의 성질을 이용해야 한다. (X*Y)%Z = ((X%Z)*(Y%Z))%Z 위 성질을 통해 long long int의 범위 내에서 계속 결과값이 형성되도록 관리해 주어야 한다. 이를 반복문을 통해 B번 순회하면서 하고 있으면 O(N)의 시간복잡도에 걸리기 때문에 다음과 같은 지수함수의 성질을 응용한다. X^Y = X^(Y/2)*X^(Y/2) 이를 통해 시간 복잡도를 O(logN) 수준.. 공감수 0 댓글수 0 2024. 4. 4.
[자료구조] 백준 1655: 가운데를 말해요 1655번: 가운데를 말해요 (acmicpc.net) 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 발상의 전환이 필요했다. 솔직히 한 번에 풀지 못했고(테스트케이스는 맞았으나, 시간초과가 남) 다른 사람의 풀이를 구글링하고 난 다음에야 문제를 풀 수 있었다. 처음에는, 매 입력마다 list를 정렬하고, 그 가운데 값을 출력하는 간단한 문제로 생각했다. 그러나 이 경우는 매번 전체 리스트를 순회하며 정렬하기 때문에 비효율적이었다. 그래서 구글링을 통해 알게 된 발상이, input을 받는 자료.. 공감수 0 댓글수 0 2024. 3. 3.
[구현] 백준 23304: 아카라카 팰린드롬 23304번: 아카라카 (acmicpc.net) 23304번: 아카라카 주어진 문자열 $S$가 아카라카 팰린드롬이라면, AKARAKA를 출력한다. 만약 그렇지 않다면, IPSELENTI를 출력한다. www.acmicpc.net 어떤 문자열이 앞으로 읽어도, 뒤로 읽어도 똑같으면 그것을 팰린드롬이라고 한다. 여기에, 해당하는 문자열의 중심을 기점으로 접두사와 접미사 역시 팰린드롬인 것을 '아카라카 팰린드롬'이라고 정의하고, 주어진 문자열이 아카라카 팰린드롬임을 확인해야 한다. 먼저 해당 문자열이 앞으로 읽어도, 뒤로 읽어도 같은지 판단한다. for (int i = 0; i < str.size(); i++) { if (str[i] != str[str.size() - 1 - i]) { return false;.. 공감수 0 댓글수 0 2024. 1. 18.
[구현] 백준 1347: 미로 만들기 1347번: 미로 만들기 (acmicpc.net) 1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net 이 문제에서 찝찝한 점은 처음 시작할 때 미로가 몇 칸짜리인지 미리 알 수 없다는 점이다. 따라서 최악의 경우를 고려해서 미로의 최대 크기를 미리 구해 놓고, 그 중간에서부터 주어진 input에 따라 미로를 그려 나가는 작업을 하였다. 이 경우는 통상적인 정의의 "미로"라고는 할 수 없겠지만, input이 모두 'F'인 경우가 미로 크기가 가장 길어지는 경우일 것이다. input 길이는 50보다 작으므로, 나는.. 공감수 0 댓글수 0 2024. 1. 16.
[BruteForce] 백준 16197: 두 동전 16197번: 두 동전 (acmicpc.net) 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 재귀함수를 이용한 brute force 문제. 동전은 무조건 2개이고, 가능한 입력 방향은 4개이다. 다음과 같은 구조를 생각하면서 재귀함수를 작성하였다. 사실 대단히 어려운 문제가 아니지만 42% 정도에서 계속 오류가 나서 고생을 했는데, 알고 보니 내가 base case 조건을 [버튼을 10번 보다 많이 누를 것]이 아닌 [버튼을 10번 이상 누를 것]으로 오독해서 생긴 문제였다. 재귀함수를 짤 때는 항상 ba.. 공감수 0 댓글수 0 2024. 1. 9.
[BruteForce] 백준 1107: 리모컨 예전에 한 번 리뷰했었던 문제인데, 지금 다시 풀어본 풀이가 좀 더 깔끔하다고 생각되어 다시 포스팅한다. https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 이동하고자 하는 목표 채널(N)을 입력받고, 고장난 버튼들을 입력받아 이 버튼들을 0~9까지의 vector에서 제외해 사용가능한 버튼들의 vector, "usableBtns"를 만든다. // fill usableBtns vector for (int i = 0; i < 10; .. 공감수 0 댓글수 1 2024. 1. 6.
[Greedy] 백준 2839: 설탕 배달 2839번: 설탕 배달 (acmicpc.net) 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 분명히 브루트포스 문제집에서 건진 문제이고 문제에 대한 사족으로 "원래는 수학 카테고리에 있었는데 브루트포스로 옮겼다"고 까지 적혀 있는데 내가 쓴 재귀함수를 이용한 탐색에서는 틀렸다. 정확히는 예시+내가 만들어 본 case에 관해서는 답이 맞게 나왔는데 정작 채점을 돌렸을 때 시간초과가 났다. 문제를 포스팅하기 앞서 Greedy 알고리즘이란, 각 선택 단계마다 그 단계에서 당장 최적인 선택을 하는 것이다. Greedy 알고.. 공감수 1 댓글수 2 2023. 11. 20.
[BruteForce] BOJ1436: 영화감독 숌 1436번: 영화감독 숌 (acmicpc.net) 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 입력 N은 10000보다 작은 자연수이고, 문제에서 제시하는 "종말의 수"는 최소한 1000개에 1개 이상씩은 존재한다. 666이 가장 작은 종말의 수이기 때문에 xxxx~~ + 666 형태인 수는 역시 종말의 수가 되기 때문이다. 따라서 최악으로 치닫더라도 10000*1000으로 1억보다 적기 때문에 그냥 순수하게 0부터 하나씩 키워 가면서 N 번째 종말의 수가 무엇인지 찾아 보기로 하였다. #include .. 공감수 0 댓글수 1 2023. 11. 15.
[BruteForce] 백준 1018 : 체스판 다시 칠하기 1018번: 체스판 다시 칠하기 (acmicpc.net) 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 올바른 체크판이 될 수 있는 경우는 10101010 01010101 10101010 01010101 10101010 01010101 10101010 01010101 01010101 10101010 01010101 10101010 01010101 10101010 01010101 10101010 (흰색이 0, 흑색이 1) 이 두 가지밖에 없기 때문에, 처음에는 입력받은 보드를 순회하면서 8*8 체크보드.. 공감수 0 댓글수 0 2023. 3. 2.
[BruteForce] 백준 15652: N과 M(4) 15652번: N과 M (4) (acmicpc.net) 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 정답률 무려 79퍼. 바빠서 리뷰는 나중으로 미뤄뒀지만 어제 N과 M 1~3을 무난히 통과한 나는 자신감 있게 덤볐지만, 모종의 이유로 잠시 고생을 했다. 기본적으로 N과 M 1~3과 같으나, 정답을 추가할 때 "비내림차순" 조건에 들어맞는지 확인하는 구문을 넣어 주면 된다. static void findAnswer(int[] arr,int depth,int r,int[] answer) throws IOEx.. 공감수 0 댓글수 0 2022. 10. 6.
[BruteForce] 백준 1748: 수 이어 쓰기 1 1748번: 수 이어 쓰기 1 (acmicpc.net) 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 솔직히 이걸 포스팅할지 말지 고민이 잠깐 되었지만 code.plus에 있는 알고리즘 기초 모든 문제를 포스팅하겠다는 것이 나의 야망이기 때문에 일단 하기로 한다. 아직 실골따리 왔다갔다 하는 내가 남에게 PS 훈수를 둘 짬은 아니지만, 인터넷 어딘가에는 브론즈 5 입출력도 막혀서 참담한 심정으로 헤매던 지난해의 나 같은 PS 뉴비들도 있을 것이기 때문이다. 처음 주어지는 수 N의 개수가 최대 100,000,000인 것부터가 대놓고 브루트포스로 하나하나 다 찾아봐도 괜찮아~ 하고 초심자를 위한 힌트를 주는 것이다. 학교 동아리에서.. 공감수 1 댓글수 0 2022. 10. 4.
[BruteForce] 백준 1107: 리모컨 1107번: 리모컨 (acmicpc.net) 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 이동해야 할 채널이 주어지고, 고장난 숫자 버튼이 주어진다. 그럼 수빈이가 목표 채널로 이동하는 경우는 다음 두 가지이다. 1. 정직하게 +/- 버튼만 눌러서 목표 채널까지 이동한다. 2. 현재 가능한 숫자 버튼들의 조합으로 가장 가까운 지점까지 이동한 후, 거기서 +/-버튼을 눌러서 추가로 이동한다. 1. 번의 경우는 단지 현재 채널(100번)과 목표 채널 사이의 절대값이 될 것이다. byPlusMi.. 공감수 2 댓글수 2 2022. 10. 3.
[BruteForce] 백준 14500: 테트로미노 14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 처음에 문제를 보고 숨이 탁 막혔다. 나는 아직도 종이찢어서 칸 채우기, 칠교블록 놓기 비스무리한 문제들... 그런 문제들을 너무 어려워한다. 그런데 문제를 다시 자세히 읽어 보니 보드에 블록 단 하나!!! 를 놓고 그 블록이 점유하는 칸들의 숫자 합이 가장 큰 경우를 찾는 문제였다. 이렇게 되면 사실 어려울 것이 없다. 블록의 첫칸부터 끝칸까지, 각 블록들을 넣어보고 그 블록이 칸에 들어갈 수 있으면 그 칸들의 .. 공감수 2 댓글수 0 2022. 10. 3.
[BruteForce] 백준 6064: 카잉 달력 6064번: 카잉 달력 (acmicpc.net) 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net code.plus에 BruteForce로 분류되어 있지만 나는 "하나하나 다 대입해가며 따져본다!"는 브루트포스의 원래 의미보다 수학적인 센스가 더 필요한 문제라고 느꼈다. 맨 처음 풀 때는 순수하게 하나하나씩 올려가며 테스트했다. import java.io.*; public class BOJ_6064 { static int M,N; static int x,y; static int T; public static voi.. 공감수 4 댓글수 0 2022. 10. 2.
[BruteForce] 백준 1476: 날짜 계산 1476번: 날짜 계산 (acmicpc.net) 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net code.plus에 BruteForce 문제로 분류되어 있기는 한데 난 그것보다는 그냥 간단한 구현 문제 정도로 느꼈다. 여태 엥? 브루트포스로 분류? 하면 기계처럼 갖다대려 용쓰던 재귀호출을 안 써서 그런가. 아무래도 좀 더 유연한 사고를 해야 한다. 함정 하나 정도를 제외하면 간단하다. year=1년부터 계속 무한반복문을 통해 modulo 연산을 통해 year%(각 변수의 크기)의 값이 각각 주어진 값과 같을 때까지.. 공감수 4 댓글수 0 2022. 9. 26.
[BruteForce] 백준 3085: 사탕 게임 피곤해서 일단 자고 내일씀 공감수 0 댓글수 0 2022. 9. 7.
[BruteForce] 백준 16198: 에너지 모으기 16198번: 에너지 모으기 (acmicpc.net) 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 특정 에너지 구슬을 고르면, 해당 에너지 구슬 좌우 값의 곱이 에너지 총합에 추가된다. 한 개의 에너지 구슬을 고르면 해당 구슬은 다음 선택에서 제외된다. 따라서 하나의 에너지 구슬을 고를 때마다 새로 에너지 구슬 배열을 만들어서 재귀호출의 input으로 넣어 주어야 한다. 또한 양 끝단의 에너지 구슬은 선택될 수 없기 때문에, 탈출조건은 양 끝단 두 에너지 구슬만 남았을 때가 된다. 나는 재귀함수의 pa.. 공감수 0 댓글수 0 2022. 8. 2.
[BFS] 백준 16948 : 데스 나이트 16948번: 데스 나이트 (acmicpc.net) 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 1. 양방향 / 일방향으로 이동 가능한(연결된) input이 주어지거나, 각 점으로부터 이동 가능한 점에 대한 규칙이 주어진다. 2. 최단거리, 최단루트를 묻는다 => BFS BFS 문제들을 예전에 몇 개 풀었었지만, 한동안 다른 카테고리의 문제들 위주로 접하다가 오랜만에 BFS 문제를 보니 어떻게 BFS를 구현하는지 잘 기억이 안 났.. 공감수 0 댓글수 0 2022. 8. 2.
[BruteForce] 백준 2309: 일곱 난쟁이 2309번: 일곱 난쟁이 (acmicpc.net) 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 간만에 브론즈 문제. 내가 브루트포스 문제가 많이 약한데 그래도 쉽게 풀 수 있던 문제였다. 9명 중 7명을 고르는 경우의 수는 사실 택도 없이 작기 때문에, 브루트포스를 써도 될지 고민할 필요는 없었다. 먼저, 난쟁이들의 키를 저장하기 위한 배열 dwarf, 해당 난쟁이가 체크되었는지 확인하는 배열 isChecked를 만들었다. static int[] dwarfs = new int[9]; static boolean[] .. 공감수 0 댓글수 0 2022. 7. 28.
[구현] 백준 20061: 모노미노도미노 2 이번 문제도 엄청 길어서 캡처 대신 링크로 갈음한다. 20061번: 모노미노도미노 2 (acmicpc.net) 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 어제 새벽 서너시까지 잡고 풀었는데, 문제가 딱히 되짚을 게 없다... 그냥 빡구현이다. 채워넣고, 조건 맞으면 점수 올리고, 연하게 색칠된 특별 구역에 들어가면 그만큼 내려주고... 만 반복하면 된다. 어차피 빨강 배열은 볼 필요가 없다. 초록 배열, 파랑 배열만 가지고 작업하면 된다. 어떤 블록을 넣어줄지 지정해주는 t, 배열이 들어갈 인덱.. 공감수 0 댓글수 0 2022. 7. 27.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.