전체 글 29

백준 28콤보!

취업하고 나서.. 거의 반년은 알고리즘을 놓았었는데. (신입이라 배울게 많았다는 변명..) 알고리즘 문제 풀어보다가 알고리즘 실력이 퇴화한게 너무 보여서 퇴근하고 8시만 되면 앉아서 문제 풀었는데 어느새 목표로 했던 한달이 다되어 간다. SAFFY하면서 알고리즘 공부했던 거 많이 까먹었는데, 매일 풀다보니 그때 감을 찾은 느낌이라 뿌듯하다. 다만! 이제 풀 문제들은 너무 난이도가 높은 것 같고.. 아니면 한문제에 2시간이상 고민해야 하는 문제들이 점점 많아지는 것 같아서 매일 같이 알고리즘 푸는건 고민해봐야 할 것 같다. 회사에서 매일 개발하고있지만, 그래도 따로 공부도 좀 해야겠다는 생각이 요즘 부쩍드는데 퇴근하고나서를 생각해보면 알고리즘 + 책읽기 정도는 가능하지만 알고리즘 + 개발공부+책읽기를 다하..

개발/잡담 2022.06.14

백준 16234 인구 이동

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 시뮬레이션 문제, 재밌는 문제인데 한방에 맞춰서 더 좋았다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import j..

개발/알고리즘 2022.06.14

백준 1865번 웜홀

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 ..

개발/알고리즘 2022.06.04

백준 16946번 벽 부수고 이동하기4

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...

개발/알고리즘 2022.06.02

백준 12851번 숨바꼭질2

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...

개발/알고리즘 2021.06.22

백준 1937번 욕심쟁이 판다

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

개발/알고리즘 2021.06.20

AWS lambda로 Restful API만들기2

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

AWS lambda로 Restful API만들기1

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

백준 1956번 운동

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] ..

개발/알고리즘 2021.06.18

백준 11779번 최소비용 구하기2

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..

개발/알고리즘 2021.06.17