알고리즘/BOJ 썸네일형 리스트형 2667번 2667번 - 단지번호붙이기 BFS 나 DFS 를 이용해서 각 구역에 대한 값들만 잘 지정해주면 되는 간단한 문제였다. 하지만 입력값을 평소처럼 int 형으로 받는게 아니라 나 같은 경우에는 char 형으로 받아서 변환시켜서 넣어주었다. 입력하는 것에서 약간 당황스러웠지만, 좋은 경험이었다. check 배열을 통해 방문하지 않은 곳은 0으로 , 방문한 곳은 그 구역에 따른 번호를 붙여주었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293.. 더보기 2331번 2331번 - 반복 수열 이번 문제는 재귀적인 방법으로 문제를 풀었다. BFS로도 풀 수 있을 것 같다.(코드 올림) 약간 DFS에서 노드를 방문하는 것처럼 그 다음 노드를 방문하는 방식으로 처음에 문제를 풀었다. (사실 문제를 풀때는 노드 방문이라고 생각 안하고 그냥 재귀로 풀었다.) 범위가 N이 9999 이고 P 가 5이기 때문에 최대치 9999 랑 5 를 이용한 값을 구해도 300000이 넘지 않는다는 것을 알았다. 그래서 check 함수를 써서 방문한 곳과 방문하지 않은 곳을 찾아냈다. 방문 하지 않았다면 방문했다는 표시로 바꿔주고 다음 노드의 값을 계산한다. 그리고 vector 에 넣어준다. 이 때도 최대 6자리 이하라는 것을 알았기 때문에 for문에 들어간 방식처럼 할 수 있었다. 그래서 그 .. 더보기 10451번 10451번 - 순열 사이클 1년 전에 이 문제를 풀었는데 그 때 그 코드를 보니 무슨 생각없이 푼 것 같은데 맞았다... 그때는 그냥 무작정 풀었던 것 같다.. 문제 풀때 -> DFS, BFS 안에 있는 for문 안에서 처음에 if (next != start) 이 부분을 빼먹어서 노드 한개가 혼자 순환하는 것을 캐치해내지 못했었다. 디버깅을 통해서 발견했다. 이런 예외적인 부분을 꼼꼼히 생각해서 푸는 연습. 완벽하게 풀기. -> 혹시 dfs 돌렸지만 순환함수를 발견하지 못할 수도 있기 때문에 cnt의 값을 나중에 확인하고 증가시켜 주었다. -> 모든 노드에 대해서 BFS , DFS 를 실행시켰다. 연결 요소가 존재하기 때문에. -> BFS, DFS 를 돌릴 때 세가지 CASE 1. 다음 노드가 한번도 .. 더보기 1707번 1707번 - 이분 그래프 이 문제를 풀때 스스로 이분 그래프의 특성을 구하고 문제를 풀어보려고 했다. 그러다 보니 처음에는 이분코드는 순환하면 안되는 성질이 있구나 라고 생각하고 문제를 풀었는데 계속 오류가 났다. 그래서 구글링해서 찾아보니 이분코드는 홀수개의 노드일 때만 순환이 안되고, 짝수개의 노드일 때는 순환이 되었다... 그래서 그 다음으로는 시작노드를 1이라고 하고 그 다음 방문하는 노드를 2로 해주는 방식으로 이분그래프를 찾았다. 처음 시작값은 모든 노드를 0으로 만들어주고 방문 할때마다 노드에 번호를 붙여주는 식으로 풀었다. 그러다가 자신의 노드 번호와 이웃의 노드 번호가 같을 경우 이분 그래프의 성질을 만족하지 않으므로 isbinary를 false로 만들어주었다. 그리고 혹시 연결 요소가.. 더보기 11724번 11724번 - 연결 요소의 개수 문제를 보자마자 연결요소란 개념을 몰라서 찾아서 풀어야 했다. 연결 요소란 위의 그림 같이 그래프가 다 이어지지 않고 나뉜 경우를 말한다고 한다. 따라서 위에서 연결 요소의 갯수는 2가 된다. 이처럼 연결요소는 BFS 나 DFS 를 각 노드 마다 돌려서 확인하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include#include#includeusing namespace std; int N, M;vector node[1001];bool check[1001];queue q;int ans; int main.. 더보기 1260번 1260번 - DFS 와 BFS DFS와 BFS.. 1년 전에 풀이기록을 보니까 10번 정도 제출해서 못 맞추고 넘어갔지만 그래도 나름 PS 를 조금 풀어보고 난 후에는 풀 수 있었다. 그떄는 DFS 가 너무 어려웠었다. 재귀 개념 자체가.. 근데 지금 완전 탐색, DP를 재귀로 풀면서 그나마 약간 감을 잡은 것 같다. 이런식으로 간선이 연결된 그래프를 풀 때 나는 주로 vector를 사용한다. 그리고 for문으로 항상 그 벡터의 사이즈 만큼 돌려주는 것을 익숙하게 사용하고 손에 익어서 계속 사용하는 것 같다. 노드와 정점을 표현하는 방법은 2가지 정도 있는거 같은데 나는 이게 익숙하다. 인접행렬 표현보다는 vector를 이용한 인접리스트로.. 오랜만에 BFS DFS 라 처음에는 정점 방문 체크를 제대로.. 더보기 11052번 11052번 - 붕어빵 판매하기 D[N] = N개 일때 붕어빵 판매로 얻을 수 있는 최대 이익. 완전 탐색을 통해 푼 뒤 캐시를 이용해 시간을 줄여주면 된다. 붕어빵을 A개 팔았다면 D[N] = D[N-A] 가 되는데 A의 범위가 1~N까지 이므로 그 중에서 최대값을 구하면 된다. 따라서 D[N] = max(D[N],D[N-A]) 가 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include#include#includeusing namespace std;int N;int P[1001];int ans;int D[1001];int go(int n){ if (n == 0) { return 0; } if (D[.. 더보기 2011번 2011번 - 암호코드 문제를 처음 보자마자 살짝 당황. 문제의 조건에서 숫자가 5000자리까지 될 수 있기 때문에 정수형 변수로는 나타낼 수 없었다. 나는 string 같은 경우 함수를 잘 모르기 때문에 구글링을 하면서 풀었다. 이 문제에서 내가 걸린 함정은 10000 같이 중간에 0 이 있는 경우에는 알파벳에서 0을 나타낼 수 있는 문자가 없기 때문에 해석할 수 없는 코드로 답이 0이 출력되어야 한다는 점이었다. ( 문제 질문 게시판에 가보면 이 점을 간과한 사람들이 올린 질문이 수두룩하다.) 이 부분을 간과해서 한참을 헤멨었다. 그리하여 처음에 완전탐색으로 풀었지만 역시나 캐시를 이용하지 않으면 시간 초과가 났다. 두번째로는 5000이라는 값을 이용하여 캐시를 사용하였다. D[N] = N개 문자를 .. 더보기 이전 1 ··· 33 34 35 36 37 38 39 40 다음
