jmmm_25

개인적으로 굉장히 어려웠던 문제였다. 계속 틀리고, 내가 짠 소스가 틀린 소스가 되버리고 조건을 너무 여러개를 생각해서 이것 저것 더 구현하려고 하니 소스만 복잡해지고, 구현도 어려웠다. 결국에는 질문과 구글링의 힘을 빌렸고 문제를 해결할 수 있었다. 다시 한번 꼭 풀어봐야할 문제이다. 0 return 11번 버튼 고장, 2번 버튼 정상 -> return 1두 버튼 다 고장 -> return -1 이런 식으로, 버튼을 누르는 횟수를 리턴한다. 그 후, sol() 함수에서 현재 버튼에서 +, -로 이동하는 횟수인 abs(n - i) 와 btn_cnt_chk에서 반환 된 값을 둘이 더하면 된다. 그 후, 처음에 계산한 값과 sol() 함수의 return 값 중에 최솟값을 찾아 출력시키면 되는 문제이다. 12..

7576번 토마토 문제는 BFS로 해결하였다. 구현이 어려운 문제는 아니지만, 반례가 많아서 정답을 맞추기가 어려웠다. 정답률이 24%인 이유를 알 것 같다. 나도 엄청 틀렸기 때문이다.우선, 다 구현해놓고 틀렸던 점은 조건이 부족했기 때문이다. 처음에, 모든 토마토가 다 익어있으면 0을 출력해야하는 부분에서 한 가지 조건이 있다.토마토 저장소가 모두 -1 즉, 비어있을 경우에도 모두 다 익어있는 상태로 생각하여 0을 출력해야 한다.이 부분을 알지 못해서 많이 틀렸었다. 그리고, 이중 for문을 돌려 하나 하나 bfs를 돌렸었는데, 그렇게 하는 것이 아니라익은 토마토가 있는 위치를 모두 큐에 push 하여 BFS 탐색을 하는 것이었다. 이렇게 고치니 문제를 해결할 수 있었다. 이 문제의 질문 검색을 하면..

1697번 숨바꼭질 문제는 BFS 알고리즘으로 분류되어 있다.이 문제는 런타임 에러가 계속 나서 까다로운 문제였다.아마도 pos * 2를 하는데 있어 isVisited의 배열의 크기를 초과하기 때문인 것 같다. 5 -> 17 로 가는 방법은 여러가지 방법이 있다.그래서 나는 그 방법을 하나씩 다 해봤다. 5 에서 출발하게 된다면 걷기 2가지 / 순간이동 1가지, 총 3방식으로 갈 수 있다. 5 + 1 = 65 - 1 = 45 * 2 = 10 이렇게 움직일 수가 있다는 것이다. 여기서 6, 4, 10을 큐에 저장시켜 두고, 같은 방식을 계속 이어나가면 된다.주의할 점은 런타임 에러가 뜬다는 것이다. 해결을 위해서는 if문 조건에서 pos - 1 , pos + 1, pos * 2의 범위 조건을 잘 맞춰주면 ..

문제에서 주어진 조건처럼 미로 중에 '0'인 곳은 지나갈 수 없고, '1'인 곳만 지나갈 수 있다.그러므로 (1,1) 부터 (N,M) 인 (4,6)까지 BFS 탐색을 하면 된다. BFS 개념만 알고 있다면 단순한 문제이다.소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#includeusing namespace std; struct Info{ int x; int y; int cnt;}; int N, M;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};char map[10..

7568번 덩치 문제는 조건만 잘 이해하면 되는 문제이다.A (x, y) 와 B (p,q)의 덩치를 비교하는데 있어, 조건식은 x > p && y > q 이면 A가 B보다 덩치가 크다고 할 수 있다. 우선 순서대로 (몸무게, 키)를 번호로 지정할 수 있게 벡터에 저장시킨다. 여기서 구조체의 개념이 들어간다.그 후에, i번째 (몸무게, 키)를 나머지 i번 째를 제외한 나머지(몸무게, 키) 와 비교를 한다.만약 비교하였을 때, i 번째 (몸무게, 키)의 덩치가 작다면 미리 만들어 놓은 ranked[i]의 값을 +1 해준다. ranked[i]++ 는 나보다 덩치가 큰 사람이 늘어난다는 것이다. 그 후에, 문제의 조건에서 "만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다." ..

6603번 로또 문제는 부분 집합을 구할 수만 있다면 쉽게 해결할 수 있다.더 간단한 방법이 있겠지만, 문제를 풀 때 vector에 부분 집합을 넣은 후, 사이즈가 6이 되는 것만 출력하게끔 했다.다음에 다른 사람들은 어떻게 문제를 풀었는지, 조금 더 나은 방법이 있는지 확인 해야겠다.문제의 출력과 순서가 동일하게 나와야 맞았습니다가 뜨는 것 같다.같이 푼 친구는 flag 없이 비트 연산으로 부분집합을 구해서 풀었는데, 순서만 나와 다르게 나왔다.순서 때문에 틀린 것인지, 아니면 잘못푼 것인진 잘 모르겠다. 소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#i..

1389번 케빈 베이컨의 6단계 법칙 문제는 백준의 알고리즘 분류상 DFS로 분류 되어 있지만, 나 같은 경우에는 BFS가 더 쉬울 것 같아서BFS로 문제를 해결하였다. 1번부터 5번 노드를 생성한 후, 인접 리스트를 생성한다.문제의 설명은 위의 문제에서 이미 자세하게 설명이 되어있기 때문에 생략해도 될 것 같다. 1번 노드부터 5번 노드까지의 케빈 베이컨의 수를 구하면 된다.그 후, sort를 통해서 번호가 가장 작은 사람을 출력하면 된다. 소스는 아래와 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include#include#in..

이번 문제는 큐와 우선 순위 큐를 잘 활용한다면 쉽게 풀 수 있는 문제이다.우선 순위 큐에 중요도가 내림차순으로 들어간다. 큐에는 각 프린터의 번호와 중요도가 pair로 들어가게 된다.따라서, 큐에 들어 있는 프린터의 중요도가 우선 순위 큐의 중요도와 같지 않으면 큐에서 pop을 한 뒤, 다시 push 해주어 뒤로 보낸다.소스는 아래와 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #define TRY_NUMBER 2 using namespace std; int n, m, order; int main(int argc, const char * argv[]) { int t..

이 문제는 완전 탐색으로 해결한다.여기서 한수란, 양의 정수 X의 자리수가 등차수열을 이루는 것이다.예를 들어, 123 이라는 숫자는 등차 +1인 한수이다.321 이라는 숫자는 등차 -1인 한수이다. 그런데 한 가지 알아야할 것은 1부터 99의 수인 한자리, 두자리의 수는 모두 한 수이다.또한 세자리 수에서는 111, 222, 333, 444, ... 의 3개의 숫자가 중복되는 숫자 또한 한수이다.왜냐하면 등차가 +- 0인 등차 수열이기 때문이다. 나 같은 경우에는 처음에 number라는 배열을 생성시킨 후, 그 세자리 수의 각 자리의 값들을 배열에 저장시켰다.그리고 등차 수열의 경우에는 무조건 + 또는 - 등차를 가지고 있기 때문에 각 자리의 숫자가 증가하거나, 감소하거나 둘 중 하나일 것이다.예를 들..

처음에 이 문제를 풀었을 때 시간 초과가 났었다.아무래도 n이 100000이기 때문이었던 것 같다. 그래서 고치다가 포기를 했었다.그 후, 구글링을 하다가 다른 사람들의 풀이를 봤었다. DFS의 사이클을 찾는 방법은 내가 생각한 방식과는 달랐었다.isVisited 배열 외에 isFinished라는 배열을 하나 더 만들어주면 해결된다. 예제에서 4번 vertex의 경우를 살펴보자.4 -> 7 -> 6 -> 4 -> 7 -> 6 -> 4 ...처럼 4 -> 7 -> 6 이 사이클이 생긴다. 이 경우에는 텀 프로젝트의 조가 이루어진다.여기서 사이클을 어떻게 찾아내냐가 중요한데, isFinished 배열이 그 역할을 한다. 4번 방문 O -> 7번 방문 O-> 6번 방문 O -> 4번 방문여기서 6번 정점이 다..