Jerry의 기록저장소

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 벨만포드 알고리즘 문제 계속 틀려서 소중한 직장인 주말 2시간을 썼다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import ..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 그냥 bfs, dfs 문제이겠거니 해서 풀었는데 시간초과가 떠서 당황했다. 처음 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util...

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 다른 숨바꼭질 시리즈를 풀어봐서 그런지 풀만했다. 다익스트라 처럼 해당위치에 최소시간을 갱신하며 bfs를 하는 것을 떠올리는게 중요한 관건이었다. 우선순위 큐이기 때문에 목적지에 도달하는 시간보다 더 느린시간을 만난경우 break로 빠져나오도록 해서 시간을 좀 더 단축할 수 있었다. import java.io.BufferedReader; import java...

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net dfs문제. 엄청 쉽게 생각해서 그냥 풀었더니 시간 초과가 나서 dp 이용해서 풀었다. 역시 그냥풀리면 골드3이 아니지.. 판다는 주변에 나무가 더 많은 곳으로 이동, 며칠 갈 수 있는가? 를 묻는 문제 dfs로 탐색 -> 시간초과 이미 지나온 곳은 어디서 접근하든 결과가 같으므로 테이블에 현재 위치 = 다음 위치 + 1 개만큼 더 갔다는 걸 떠올려서 dp테이블 만들기 (안지나 간 곳?-..

자 이번에는 람다를 선택하고 자바로 API를 만들어보고 싶다. (하지만 실패했음) 오잉?.. 자바 코드편집기가 없다고? 코드편집기를 통해 편하게 API코드를 작성할 수 있는데. 자바는 그게 없어서 직접 Zip이나 jar파일을 업로드 해야한다고 쓰여있다. 근데 어떻게 API를 작성해야 하는지 잘모르겠어서 일단 Node.js를 사용해서 다시 만들었다. 자바는 왜 이런 코드편집기가 지원이 안되는 것 인가.. 아무튼 정상적으로 람다를 쓰면 Hello from Lambda를 반환하겠지? 다시 API Gateway로 와서 람다를 사용할 메서드를 생성해보자. 람다 함수 이름을 넣어주면 된다. 람다로 가보면 위처럼 API 게이트웨이가 트리거로 추가되어있다. 테스트 해보니 정상적으로 200 Hello Lambda를 반환..

평소 AWS를 사용해서 개발을 한번 해보고 싶었는데 친구와 사이드플젝을 하기로 한김에 Restful API를 AWS서비스를 이용해서 하자고 해봤다. 개인적으로 AWS를 이용해보고 싶은이유는 Azure사용해서 개발한 경험은 있는데 AWS를 사용해서 개발해본 경험은 없음 AWS가 아무래도 제일 많이 쓰이는 클라우드 서비스 AWS Certified Cloud practitioner 자격증을 취득했는데 약간의 지식 써먹을 겸 해보고 싶었다. 이런식으로.. 클라이언트가 요청을 보내면 aws lambda를 통해 응답하는? API Gateway 뒤에 뭐 여러개가 붙을 수 있는데 일단 테스트용으로 Hello world나 사용자 이름정도 반환해보는 테스트를 하면 될 것 같다. API Gateway 서비스를 사용하겠다. ..

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 플로이드 와샬 연습용문제. 400 x 400 이므로 인접행렬로 풀었음 (생각해보니 플로이드문제중에 인접리스트로 푸는게 있던가?..) 배열 INF값으로 초기화 edge 넣어줌 edges[a][b] = dist; // a -> b는 거리가 dist 플로이드와샬 경출도 (경유지, 출발지, 도착지) edges[a][b] > edges[a][k] + edges[k][a] ..

https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 문제 bfs pq 이용해 최소비용으로 하면 다익스트라라고 하신 민O형의 말씀. 덕분에 다익스트라 방법을 까먹더라도 bfs에 pq 이용해서 푼다는 것을 기억하고 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.u..

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문자열 문제를 풀어보려했으나? dfs였던 문제; 비트마스킹 연습도 되어서 좋았다. (근데 그래도 코테에서는 배열 visit체크로 풀 것 같다. 더 구현이 편함..) 비트마스킹이 손에 덜 익어서 좀 어려웠던 문제. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 알고리즘 스터디에서 못 풀었던 문제를 dp를 공부하고 나니 이제 풀 수 있었다! 30분 컷! 이제 dp문제를 어떻게 풀어야 할지 감은 잡을 수 있을 것 같다. 근데 실버 2인데 왜 실버 1이었던 RGB거리보다 어렵지?. 스티커를 선택하면 변을 공유하는 다른 스티커들은 사용할 수 없다고 한다. 여기서 생각한 점 왼쪽부터 시작해서 윗줄의 스티커를 선택하면 다음엔 아랫줄의 스티커를 선택하면 ..