반응형 개발삽질/SSAFY하는 동안 기록38 [BOJ]2293_동전1(dp) 오늘 오전에 sk패밀리사 코테를 보고 자극을 또 받았다. 그래도 알고리즘 연습을 제대로 한 뒤 처음보는 코테였기에 1차통과를 기대했다. 그러나 사람은 역시 자만하면 안된다 하였던가, 내가 많이 준비하지 않은 유형에서 문제가 나왔고, 준비한 부분은 너무 어렵게 나왔다. 4문제중 2문제를 풀었는데, 그 두 문제도 히든케이스에선 틀릴 수도 있을 것 같다. 첫번째 문제는 dp문제였다. 아니 다이나믹프로그래밍은 코테에 잘 안나온다며ㅠㅠ그래서 잘 안했는데 떡하니 1번부터 나와서 진짜 포기할 뻔 했다. 암튼 1번은 dp(그리디인 것 같기도..), 2번은 오질나게 구현(회오리 그래프에 찍기), 3번은 다익스트라인데 ㄱ꼬은 다익스트라, 4번은 풀긴 했는데 무슨 유형이지..dfs를 활용한 것 같다. 그 와중에 1번 문제랑.. 2022. 3. 12. [BOJ]9370_미확인도착지(특정경로 다익스트라) https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 해석하다 살짝 힘들뻔 했는데, 결국 요지는 한줄이다. "최단경로가 특정경로를 지나는지 구하라." 아니 이걸 어케 하지 막막했다. 일단 최단경로를 구하긴 하는 거니까 다익스트라를 쓰란 거긴한데, 중간에 어딜 들렀는지는 어케 체크하지....하고 일단 내가 기존에 알던 방법대로 진행을 했다. 크게 두가지 방법이 있을 것이다. 1. 경로를 나눠서 일일히 구하고 더한 경로가 최단경로와 같은지 비.. 2022. 3. 9. [BOJ]6603_로또(조합) 며칠간 그래프 문제만 풀었더니 이러다 순열조합을 까먹을 것 같아 얼른 풀고 정리하려고 한다. https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 전형적인 조합문제다. 순서 상관없이 주어진 숫자 중에서 6개를 뽑으면 되는 문제다. 다음은 코드. 나~중에 혹시 조합이 생각안나게 된다면(ㄹㅇ 그러면 자살각) 참고하도록. import java.io.BufferedReader; import java.io.IOException; import jav.. 2022. 3. 9. [BOJ]11724_연결요소의개수(DFS) https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제는 간단하다. dfs를 연습하기 좋다. 간선 정보가 주어지고, 선으로 연결된 뭉텅이? 개수를 구하는 거다. 0. 키포인트는 boolean[] visited를 만드는 것. 굳이 [][]만들 필요는 없음. 1. 일단 전체 mat을 돌면서 원소가 1이라면 dfs()호출! 2. dfs()에서 for문 돌면서 mat[start][i]가 1이.. 2022. 3. 8. [BOJ]4485_녹색 옷 입은 애가 젤다지?(다익스트라) 뭔가 다익스트라가 BFS와 프림을 합쳐놓은 느낌이 들어서 계속 다익스트라만 골라 푸는 것 같다. 암튼 풀었으니 리뷰! 이제 골드문제도 딱히 두렵지 않다. 그냥 풀면 풀리는 것 같다(아직 다양한 유형을 안해봐서 그럴수도ㅋㅋ) https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제의 입력이 행렬로 주어졌다. 이전에 주로 연습했던 다익스트라는 간선정보(from, to, weight)로 주어진 것을 연습해서 행렬을 어떻게 다익스트로 풀.. 2022. 3. 6. [BOJ]2667_단지번호붙이기(bfs) https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 낼모레가 정처기 시험이라 알고리즘 안풀려 했는데, 알고리즘 안푼다고 정처기 공부 더 하는 것 같지도 않다고 느꼈다. 외우는 공부는 이제 나이가 들어서 그런지 집중력 10분을 넘기지 못한다. 그러나 알고리즘 문제는 한시간은 거뜬히 집중할 수 있다는 것을 알기에 걍 이렇게 멍 때리고 유튜브보면서 공부 안할 바에 얼른 알고리즘 문제 하나 더 풀자고 생각했다. 문제는 내가 좋아하는(?) bfs.(물론 bt.. 2022. 3. 3. 이전 1 2 3 4 5 ··· 7 다음 반응형