Programming/알고리즘 (13) 썸네일형 리스트형 백준 토마토문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마 www.acmicpc.net 문제는 토마토상자에 토마토가 있을때 하루가 지날수록 토마토는 주변 토마토를 익힐수 있다. 이 때 4방향 이웃을 익히는데 익힐수 있는 모든 .. 백준 구슬탈출2 https://www.acmicpc.net/problem/13460 최단경로를 찾는 문제는 BFS로 구현해야한다. 그런데 이 문제에서 BFS로 구현하면서 각각의 노드에 대해서 기억해야 하는 정보가 많아서 난항을 겪었다. BFS를 큐를 이용해서 구현하려고 했기 때문인데 생각해보니 큐에 기본 자료형을 넣을 생각만 하고 있었기 때문이다. BFS에 쓰는 큐에 들어가는 자료형을 구조체로 직접 선언하여 필요한 정보를 각각의 노드마다 전부 저장하였다. 다음과 같이 저장했다. BFS를 구현하는데 있어서 자기 마음껏, 재량껏 소스를 구현함에 따라 구현이 가능할 수도 있고 못할 수도 있었다. 전체 해답 소스는 다음과 같다. #include #include #define LEFT 0 #define DOWN 1.. 백준 나무자르기 https://www.acmicpc.net/problem/2110 나무자르기 문제이고 난이도는 Silver 3 이다. 보자마자 풀이가 생각날 정도로 쉬운 문제라고 생각했는데 왜 이게 silver 3 이나 되는지 의아했다. 그러나 보기좋게 fail... 문제를 다시 보니 정답률이 25%밖에 안되는 문제다. 나처럼 쉽게보고 덤볐다가 틀리는 사람이 많은가보다. 정답률이 낮다는건 모든 반례에 대해서 제대로 확인하는게 관건인 문제라고 볼 수 있다. 물론 소스코드를 오차 없이 설계하는것도 중요하다. 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 .. 백준 공유기설치 https://www.acmicpc.net/problem/2110 백준 공유기설치 문제이다. 이진탐색 문제인데 꽤나 신박한 문제였다. 문제를 본 순간 드는 생각은 공유기를 하나하나씩 둬 보면서 경우의 수를 따져보는 것이었다. 다시 말해서 완전탐색으로 풀 수 있는 문제지만 역시 백준문제답게 시간제한이 있으므로 완전탐색보다 빠른 이진탐색을 이용하면 풀 수 있을거라 생각했다. 공유기설치하는 집 사이의 최소거리를 이진탐색으로 찾는것을 생각하는 것이 꽤나 어려웠다. 해결 알고리즘 1. 이진탐색으로 nCurDst를 설정한다. 2. 설정한 nCurDst로 공유기를 다 설치할 수 있는지 확인한다. (CheckDistance()) 3. 공유기를 설치할 수 있으면 더 큰 nCurDst로 다시 탐색하고 해당 nCurDst를.. 백준 유진수 Bronze1 문제. 자기전에 머리 식힐겸 풀어보는 문제로 적당하다. #include using namespace std; int main() { int N = 0; int parsing[11]; int input; cin >> input; if (input < 10)//한자리수 { cout 0) { parsing[N] = input % 10; input /= 10; N++; } // 하나하나 따져보면서 유진수인지 확인 for (int i = 0; i < N - 1; i++) { int left = 1, right = 1; //왼쪽 곱 for (int j = 0; j 이전 1 2 다음
