반응형 분류 전체보기88 [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. [BOJ]13549_숨바꼭질3(다익스트라) 오늘은 간만에 찾아온 휴일이었다. 삼일절! 그러나 난 불쌍한 취준생이자 이번주 토욜에 정보처리기사를 봐야 하기에 꾸역꾸역 카페에 가서 공부를 하였다. 정처기만 보고 있자니, 알고리즘을 까먹을까봐 한문제만 풀자하고 저녁먹고 풀었다. 다익스트라 마스터가 되려 그러는지 다익스트라를 골라서 풀었다ㅋㅋ https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 여태 연습했던 최다경로 문제와 달리, 이 문제는 그래프 문제가 아니다... 2022. 3. 2. [SWEA]1251_하나로 (크루스칼) 문제를 읽으면 전체 섬들을 다 합치는거다. 그럼 최소신장트리를 이용한 문제란 감이 온다. 근데 좀 짜증나는게 입력값으로 x좌표 따로, y좌표 따로 온다. 아니 이건 인접리스트를 만들어야 되나 인접행렬을 만들어야되나고민이 됐다. 다시 정리해보면, [알고리즘]최소신장트리(크루스칼,프림) 이름부터 무슨 중국말도 아니고 신장트리래. 영어는 더 어려움 수학공식같은 이름.. 그러나 막상해보면 별거아님 또. 이름 지은 사람들 다들 한대씩 맞아야함.ㅋㅋ 위 알고리즘을 쓰는 때는, 그 lovenewthing.tistory.com -인접리스트로 만들어서 푸는거 = 크루스칼 크루스칼 장점 : 좀 더 구현하기 수월함 단점 : 간선들을 정렬해줘야 해서 시간이 쪼오금 더 걸림 -인접행렬로 만들어서 푸는거 = 프림. 암튼, 이렇게.. 2022. 2. 25. 이전 1 2 3 4 5 6 7 8 ··· 15 다음 반응형
