반응형 개발삽질52 [알고리즘]인접행렬과 인접리스트에서의 DFS,BFS 입력값으로 간선의 정보들이 주어지는 문제에서 탐색을 요구할 경우 인접행렬 또는 인접리스트로 DFS 나 BFS로 풀게 된다.(나중에 간선정보로 푸는 문제에는 최소신장트리를 구하는 크루스칼 알고리즘도 있지만, 최소신장트리가 아닌 일반적인 그래프에서는 인접행렬 또는 인접리스트로 푸는 경우가 많다) 인접행렬이나 인접리스트 뭐가 절대적으로 좋다라고 말할 순 없지만, 정점의 수가 엄청 많은데 간선은 없는 경우에는 인접리스트가 더 효과적일 것이고, 밀집그래프에서는 리스트는 타고타고타고 가야하니까 시간이 오래걸리므로 인접행렬이 더 나을 것이다. 문제의 정점과 간선 수를 보고 선택하면 된다. 인접행렬에서 DFS, BFS 아래처럼 간선의 0~6까지 7개의 정점이 주어지고, 8개의 간선정보가 주어졌다. 모두 탐색하는 dfs.. 2022. 2. 23. [SWEA] SWEA3234_준형이의 양팔저울_백트래킹 순열과 부분집합을 동시에 적용해야 풀 수 있는 문제이다. 코드를 보면 파바박 할 수 있을 것 같지만, 백지상태에선 막막했다. 게다가 백트래킹(가지치기)를 제대로 하지 않으면 시간초과까지 뜨니 효율성도 고려해야 한다. 결론적으로 순열+부분집합+백트래킹을 연습할 수 있는 good 문제. 문제. 준환이는 N개의 서로 다른 무게를 가진 무게 추와 양팔저울을 가지고 있다. 모든 무게 추를 양팔저울 위에 올리는 순서는 총 N!가지가 있고, 여기에 더해서 각 추를 양팔저울의 왼쪽에 올릴 것인지 오른쪽에 올릴 것인지를 정해야 해서 총 2N * N!가지의 경우가 있다. 하지만 양팔 저울에 갑자기 문제가 생겨서 무게 추를 올릴 때 오른쪽 위에 올라가 있는 무게의 총합이 왼쪽에 올라가 있는 무게의 총합보다 더 커져서는 안 .. 2022. 2. 18. [알고리즘] 그리디 그리디는 정해진 방법이 없다. 해당 문제가 그리디라는 것을 눈치챘다면 순간의 센스가 8할이라고 한다. 그렇다면 패스..하려다가 일단 가장 대표적인 그리디 문제의 유형 하나쯤은 마스터해놓는 것도 나쁘진 않겠다 싶어 정리를 한다. 가장 유명한 예제는 바로 회의실 예약하는 문제이다. 그림을 그려서 푸는게 말로 100마디 하는것보다 훨씬 이해가 잘되니 글은 그림으로 해도 안될때 읽기 바란다. 회의실은 하나인데, 회의는 10개이다. 어느 회의를 회의실에 예약해야 가장 많은 회의를 진행시킬 수 있을까? 구현 시 재밌던 점은 Meeting 클래스를 하나 더 만들고 Comparable을 상속하여 compareTo메소드를 오버라이드 한것이다. 이는 회의실의 종료시간을 기준으로 오름차순 정렬을 해야 하는데, 사용자 정의 .. 2022. 2. 17. [알고리즘] 분할정복!(BOJ1992쿼드트리,BOJ1074Z) 다양한 순,조,부 구현방법을 배웠는데 난 오리지날 방법이 가장 좋다...비트마스킹도 좋지만 내가 게을러서인지 선뜻 쉽게 사용하기 어렵게 느껴진다. 이걸 더 연습해야하나 고민할 찰나에 분할정복 유형 진도를 나가게 되었다. 그래 그냥 순조부는 원래풀던대로 하자. 분할정복을 정복하자! 분할정복은 기본적으로 재귀를 사용한다. 가장 간단한 예시는 거듭제곱 구하기이다. 식만 보면 이해되려나. 지금은 되는데 나중에 다시 볼때 내가 잘 이해할지 모르겠다ㅋㅋ 이진트리를 그려서 보면 이해하기 쉽다. 2^9 = 2^4*2 두개 (여기서 9는 홀수이기에 4 4로 나누고 2를 한번 더 곱해줘야 하는게 포인트!) 2^4 = 2^2 두개 2^2 = 2^1 두개 import java.util.Scanner; public class .. 2022. 2. 17. [알고리즘]순열 - NextPermutation 요즘 블로그 글을 쓰는 주기가 길어진다. 써야지 하는 마음이 있다가도 지금 글을 쓰는게 사치는 아닌지 생각이 든다. 왜냐면 글을 쓰고 정리하는 시간에 문제 하나라도 더 풀고 혼자서 다시 풀어보는게 내 실력에 향상이 될텐데하는 조급합과, 블로그 글 쓸 시간이 있느냐 하는 죄책감....그래도 조금씩은 쓰자ㅠㅠ 오늘은 2차 과목평가도 있었고, 자바반으로 옮긴 후 처음 보는 시험인데 처음부터 떨어지고 싶지 않았기에 긴장하고 공부를 했다. 괜히 블로그 쓴다고 나대다가 떨어지면 너무 잔혹하잖아...그래서 그냥 따로 순열, 조합, 부분집합 혼자서 구현해보고 IM관련 백준을 풀면서 한주를 보냈고, 오늘 시험을 봐서 마음이 조금은 나아졌다. 시험을 본 오늘도 역시나 싸피는 진도를 나갔다. 오늘도 순열을 한다길래, 앗싸 .. 2022. 2. 14. [Java]보조스트림(InputStreamReader, BufferedReader, ObjectInputStream(직렬화) 등등) 보조스트림은 기존 노드스트림에다가 확장해서 연결할 때 씀. 보조스트림 종류 - byte 스트림을 char로 스트림으로 변환 InputStreamReader, OutputStreamWriter - 버퍼링을 통한 속도 향상 - byte기반: BufferedInputStream, BufferedOutputStream - char기반: BufferedReader, BufferedWriter - 객체전송 ObjectInputStream ObjectOutputStream 사용할 스트림 결정해보자 다음 순서로 결정하면 된다. 노드가 무엇인가? -> 타입은 문자열 or 바이트인가? -> 방향은? -> 추가기능은(보조스트림)? 영화 파일을 빠른 속도로 이동시키고 싶다면? File -> byte -> 읽기 -> FileI.. 2022. 2. 6. 이전 1 2 3 4 5 6 7 8 9 다음 반응형
