jmmm_25

이분 그래프를 이산 수학을 배울 때 공부를 했었는데, 금방 잊어버려서 다시 공부를 했다. 이 문제를 풀 때 반례가 있다. BFS로 문제를 풀었는데, 그래프가 연결되어 있지 않고 연결 요소가 2개 이상일 수도 있어서모든 vertex를 다 탐색하며 ret 값을 바꿔줘야 한다. 이 간단한 것을 생각 못해서 처음에 계속 틀렸다. 그리고, 2차원 vector인 adj를 초기화하는 과정에서 adj.resize()를 하면 초기화가 되는 것인지 알았는데, 그렇지 않아서 adj.clear()를 먼저 해주고 해야한다.오랜만에 BFS 문제를 풀어서 그런지 약간 헷갈려서 좀 많이 틀렸던 문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404..

1019번 책 페이지의 문제는 입력이 10억이다. 따라서 1억이 1초 이기 때문에, 당연하게 O(n)으로 코드를 작성할 경우 시간초과가 뜰 것이다.그래서 다른 방식으로 접근을 해야한다. 이 문제를 처음 풀었을 때에는 우선 int형 배열 answer[10] 을 만들고, for문으로 1 ~ N ( 10억 ) 까지 돌리면서 각 자릿수의 숫자인 answer[각 자리의 숫자 값]++ 를 해주면서코딩을 하려고 했다. 그러나, 아무리봐도 이는 시간초과가 날 것임이 당연했고 결국 틀렸다. 그래서 다른 방식으로 접근하려 했는데, 생각이 나지 않아 백준의 문제 풀이를 참고했다. 문제의 시작을 바꿔본다. 예를 들어, 책의 시작 페이지가 17쪽이고, 마지막 페이지는 53쪽 이라고 가정하자. start = 17finish = ..

int pos, cnt를 가진 클래스 Info를 만들어주고 BFS 탐색을 하면 된다. 예제 : 10 1 10 2 1 의 경우 건물의 MAX 높이는 10이고, 시작은 1층, 도착해야할 위치는 10층이다.이 경우에는 U U U U U D 이처럼 6번을 누르면 가장 적게 누른 버튼 횟수이다. BFS 탐색을 할 때, isVisited 배열을 만들어 준 후, 그 층에 방문할 수 있다면 true로 저장을 시킨다.탐색 중에 pos와 g가 같은 경우 cnt를 출력시켜 주고, 만약 탐색이 끝났는데 그 층수에 도착하지 못하였다면 58 줄에서 isVisited[g]의 값이 false 이므로, "use the stairs" 를 출력시키고 종료 시키면 된다. 마지막으로, s와 g의 값이 처음부터 같을 경우에는 0을 출력시키면 ..

보물섬 문제는 인접 행렬로 상하좌우를 확인하며 BFS 알고리즘을 사용하면 된다.이중 for문을 이용해서 'L' 일경우에만 BFS 탐색을 시작하여 max 값을 찾아내 출력하면 된다. 소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #include #include using namespace std; class Info {public: int x, y, cnt; Info() {}; Info(int _x, int _y, int _cnt): x(_x), y(_y..

1072번 게임 문제의 경우, 입력 X가 10억보다 작거나 같은 수 이므로 시간 초과가 날 가능성이 높다.따라서, for문으로 1 ~ 10억 까지 증가시키기 보다는, 이분 탐색으로 정답을 출력하는 것이 좋다. 소스는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #define MAX_INF 1000000000using namespace std; long long x, y, z; int main(int argc, char const *argv[]) { long long l, r, mid; while(cin >> x >> y) { long long temp_z = 0; z = 100 * y /..

싱기한 네자리 숫자 문제는 자리 수만 잘 구하면 쉽게 풀 수 있는 문제이다.그리고 아마 싱기한이 신기한의 오타가 아닐까 생각이 든다. 위의 문제에서 예제 출력란의 답은 일부이고 실제로는 9999까지 이므로 출력이 더 나오는게 맞다. 12345678910111213141516171819202122232425262728293031323334#include #define MAXIMUM_INPUT 9999#define MINIMUM_INPUT 1000using namespace std; int main(int argc, char const *argv[]) { int ret_ten, ret_twe, ret_hex; for (int i = MINIMUM_INPUT; i 0; n/=10) { ret_ten += n ..

쉬운 문제라 바로 풀 수 있을 문제일 것이다. 소스는 아래와 같다. 12345678910111213141516171819202122#include using namespace std; int n;int main(int argc, char const *argv[]) { cin >> n; int cnt = 0; n += 1; while (n--) { for (size_t i = n; i > 0; i/=10) { int temp = i % 10; if (temp >= 0) { cnt++; } } } cout

팰린드 롬이란, 앞에서 읽었을 때와 뒤에서 읽었을 때의 문자가 똑같은 경우를 말한다. 이 문제에서 알아야할 센스는 i + 'A' ( 0

이 문제는 DFS 알고리즘으로 해결하였다. 탐색 가능하면 계속 탐색하고, 그렇지 않으면 탐색했던 곳의 알파벳의 Check를 false로 바꿔주어야 한다. 처음에 이걸 생각 못해서 계속 틀렸었다. 그리고 바보같이 방문을 했는지 체크하는 배열을 만들어서 한 번 방문했던 곳을 방문하지 못하게 했다. 그래서 계속 틀렸었다. 질문 검색을 해보니, 몇개의 예제가 있었는데 그 예제를 통해서 결국 답을 맞출 수 있었다. DFS 알고리즘에 약간 응용인 문제인 것 같다. 위에서 말했던 것처럼 이상한 짓을 해가지고 시간이 좀 걸렸다. 나중에 다시 한번 보면 좋을 문제. 알파벳을 체크하는 방식이 있을텐데, 나는 그냥 벡터를 만들어서 for문을 돌려서 소스가 지저분하다. 다른 사람들은 어떻게 이 부분을 체크했는지 알아봐야할 것..

이번 문제는 BFS 문제이다. 문제는 촌수 계산이지만, 노드의 Level을 출력하라는 문제와 동일하다.만약 노드끼리 연결되어 있지 않다면 -1을 출력하면 된다.노드간의 연결이므로 인접 리스트로 문제를 해결하였다. 소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include using namespace std; vector adj(101);bool isVisited[101];int n, m; int bfs(int x, int y) { queue q; isVisited[x] = true; q.push(x); int l..