https://www.acmicpc.net/problem/1325 > n >> m; bool* visited = new bool[n+1]; memset(visited,false,sizeof(visited)); int* ans = new int[n+1]; vector com(n+1,vector()); for(int i = 0; i > a >> b; com[b].push_back(a); } for(int i = 1; i < n+1 ; i++){ BFS(i, com, visited, ans); fill_n(visited, n+1, false); } int max_val = *max_element(ans+1, ans + n+1); for(int i = 1; i < n+1; i++){..

https://www.acmicpc.net/problem/18114 18114번: 블랙 프라이데이첫 번째 줄에 물건의 개수 N과 제시하는 무게 C가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ C ≤ 108, N과 C는 양의 정수) 다음 줄에는 N개의 물건 각각의 무게 w가 공백으로 구분되어 주어진www.acmicpc.net알고리즘 분류에 보면 이분탐색이 들어가 있지만 본인은 투포인터 + 브루트포스로 풀었다.일단 정렬한 배열의 처음과 끝을 투포인터로 잡았다.그리고 투포인터로 잡은 상태에서 브루트포스를 돌려서 변수 3개를 설정했다.x(처음), y(끝), i(for문)투포인터는 고정시키고 for문을 돌려서 각각 하나, 둘, 셋의 합이 C와 같으면 ans = 1로 설정했다.그리고 for문이..

https://www.acmicpc.net/problem/27972 27972번: 악보는 거들 뿐 키위새는 피아노를 잘 치고 싶었지만 악보를 볼 줄 몰랐다. 그러다 동영상 사이트에서 수열만 보고 피아노를 연주하는 동영상을 찾아냈다! 하지만 동영상에서 보여주는 수에 맞는 음을 누르자 www.acmicpc.net 와쿠컵에 출제되었던 문제다. 풀타임으로 하고 싶었지만 교수님께서 중간고사를 2번본다는 말씀을 하셔서 짝수번만 풀다가 음악을 좋아해서 문제 제목보고 풀려다가 한번에 못푼 문제였다. 틀린 문제들 다시 풀다가 이번에 풀었는데, 생각보다 너무 바로 아이디어가 떠올라서 허무했다. 왜 그때 한번에 떠올리지 못했을까...하이튼 그리디문제이고 별로 어려운 문제도 아니라고 생각한다. 풀이는 악보 수열을 받아서 연속..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 평범한 그래프 탐색문제이다. DFS를 사용해도 좋고, BFS를 사용해도 좋다. 본인은 BFS를 사용하여 각 섬의 개수를 탐색하였다. 차이점라고 하기에도 뭐하지만 굳이 뽑자면, 대각선에 있는 섬도 연결되어있는 섬으로 보기 때문에 현재 좌표를 기준으로 주위에 있는 모든 방향(8방향)을 모두 탐색해야한다. 그래프 문제 푼지 오래된거 같아서 오랜만에 간단히 하나 풀었다. 코드는 다음과 같다. imp..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 퇴사를 하기 전까지 최대 수익을 내야하는 문제이다. 실버3이지만 앞에서 미리 포스팅했던 포도주 시식이나 RGB거리 등 다른 Dp문제보다 더 애먹었다. Dp 문제를 접하는 마인드로 일단 어떻게든 다 훑어야지 라고 생각하며 접근했는데...처음 2중for문으로 점화식을 짰는데...예외 상황이 너무 많아서 하나씩 예외처리를 하다보니까 코드가 Greedy하게 변했다. 결국 풀다가 시간이 너무 지나서 작성했던 코드 다지우고 담날에 새로 하자는 마인드로 그냥 잤다 ㅋㅋ 담날에 수업시간에 잠깐 봤는데 어떻게 탐색해야할지 새로운 아이디어가 떠올라서 ..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제를 처음 봤을때 DFS 쓰는 문제인가? 했는데 DFS를 사용해도 답은 나오겠지만 너무 가짓수가 많아서 시간초과에 걸릴게 뻔했다. 숫자들이 규칙이 없는것이 아니라 1차이라는 규칙이 있으므로 그냥 Dp썼다. Dp를 점점 하면서 느낀거지만 문제가 다 똑같다. 물론 아직 Dp애기 수준이라 실버1 언저리 문제만 풀지만, 현재까지 느낀바로는 그렇다. 문제 풀이는 각 자릿수를 정해야하는데 첫번째 자릿수에는 0이 올수 없고, 앞자릿수에 영향을 받지 않으므로 미리 세팅을 해준다. dp[0][0]을 제외하고 나머지를 모두 1..