본문 바로가기

CS ﹒ Algorithm/Baekjoon

Java 백준 문제풀이 (31) 2606: 바이러스
CS ﹒ Algorithm/Baekjoon 2022. 7. 30. Java 백준 문제풀이 (31) 2606: 바이러스 문제 요약 - 1번 정점에서 탐색할 수 있는 정점 개수를 구하시오. " 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터 수 "라서 1번은 제외하고 카운트한다. dfs, bfs 어떤 방식을 채택해도 풀 수 있지만 나는 코드가 짧은 dfs 알고리즘이 좋다. 이번 문제는 친절하게 그림까지 그려져 있어서 설명하는 척이라도 할만한 건덕지가 없다.. 날로 먹는군. import java.util.*; import java.io.*; public class Main { static ArrayList edgeList = new ArrayList(); static boolean[] visited; static int count; public static void main(String[] args) throws IOE..
Java 백준 문제풀이 (30) 11725: 트리의 부모 찾기
CS ﹒ Algorithm/Baekjoon 2022. 7. 29. Java 백준 문제풀이 (30) 11725: 트리의 부모 찾기 간선만 던져주고 트리의 부모를 찾으라고 한다. IQ 130 이상이면 정보를 구체화해서 머리 속에서 그릴 수 있다던데 나처럼 IQ가 130 미만이라면 직접 손으로 그려보자. 이렇게 생긴 트리였다. 이진 트리 아님. 출력은 2번 노드의 부모 ~ N번 노드의 부모가 나오면 된다. DFS 알고리즘에 대해 떠올려보자 우리가 특정 노드를 탐색하기 위해서는 항상 그 노드의 부모 노드를 거치게 된다. static void dfs(int node) { visited[node] = true; for (int v : edges.get(node)) { if (!visited[v]) { dfs(v); } } } 이게 기본적인 dfs 알고리즘의 재귀함수인데 여기서 node는 각 정점을 의미하고 v는 그곳에서 파생된 자식 node..
Java 백준 문제풀이 (29) 2444: 알고리즘 수업 - 너비 우선 탐색 1
CS ﹒ Algorithm/Baekjoon 2022. 7. 28. Java 백준 문제풀이 (29) 2444: 알고리즘 수업 - 너비 우선 탐색 1 오늘은 너비 우선 탐색이다. 바로 이전 글에 있는 dfs(깊이 우선 탐색)문제를 풀었다면 쉽게 풀 수 있다. 물론 최소한의 이론은 알고 와야 한다. 헷갈릴 때는 이 그림을 떠올려보자. 왜 BFS에서는 Queue를 이용한 반복문을 돌리고 DFS에서는 재귀호출로 처리하는지 이해가 될 것이다. 이 그림을 보고 왜 Queue를 써야하는지 이해가 되지 않는다면 BFS가 아니라 Queue를 다시 공부해야 한다. 어차피 문제에서 기본적인 풀이 방법은 모두 제시하고 있으므로 코드별로 나누어 해당 코드를 작성한 이유를 설명하는 것으로 진행한다. 전체 코드 import java.util.*; import java.io.*; public class Main { static boolean[] visited; static in..
Java 백준 문제풀이(28) 24479: 알고리즘 수업 - 깊이 우선 탐색1 (+24480 깊이 우선 탐색2)
CS ﹒ Algorithm/Baekjoon 2022. 7. 27. Java 백준 문제풀이(28) 24479: 알고리즘 수업 - 깊이 우선 탐색1 (+24480 깊이 우선 탐색2) *24480은 내림차순인 것 외 완전히 동일한 문제라서 제일 밑에 정답만 올려놨다. 언제 한 번 시간내서 배워야 하는데.. 라고 생각하던 그래프 알고리즘을 찍먹하게 되었다. 쩝.. 생각해보면 예약글이라 이 글이 올라갈 때 쯤에는 어차피 코드 스테이츠에서 그래프 알고리즘 배우는 시기랑 맞물릴 것 같은데 그냥 그 때 공부할 걸 그랬나 싶기도 하다. 알고리즘을 처음부터 설명하는 건 너무 오래 걸리고, 이론은 대충 훑고 왔는데 이해 안되는 수준에 맞춰서 글을 작성하였다. 언젠가 그래프 알고리즘에 관한 글도 따로 작성하고 싶다. 바보의 마음은 바보가 아는 법.. static ArrayList list = new ArrayList(); static boolean[] visited; static int[] order..
JAVA 백준 문제풀이(27) 10828:스택, 19258:큐2
CS ﹒ Algorithm/Baekjoon 2022. 7. 26. JAVA 백준 문제풀이(27) 10828:스택, 19258:큐2 오늘은 너무 쉬운 문제라서 차마 이걸로 1일 1백준을 했다고 하기엔 좀 그래서.. 두 문제 풀었다.. 대신 둘 다 쉬운 걸로.. ㅎ.. 저 위에 왜 실패 딱지가 붙어있냐고 묻는다면 나도 모른다. 거슬려서 6번 제출했는데도 실패라고 써있어서 포기했다. stack 자료구조를 대충이라도 알고 있다면 누구나 쉽게 풀었을 문제일 것이다. stack은 LIFO(Last In First Out) 구조로 되어 있어서 가장 마지막에 들어온 데이터를 가장 먼저 반환하고, 처음 들어온 데이터는 모든 데이터가 반환되고 나서야 반환할 수 있다. 우리가 사용하는 자바의 스택 메모리가 이런 Stack 자료구조로 되어있다. 또한 자바 내에서 애초에 stack을 사용할 수 있기 때문에 그냥 stack 사용 해서 해당 메서드들을 그대로..
JAVA 백준 문제풀이 (26) 9996: 한국이 그리울 땐 서버에 접속하지
CS ﹒ Algorithm/Baekjoon 2022. 7. 23. JAVA 백준 문제풀이 (26) 9996: 한국이 그리울 땐 서버에 접속하지 오늘은 두가지 정답을 준비했다. 첫번째는 죽었다 깨어나도 정규식은 못 외우겠다는 사람을 위한 것이고 두번째는 정규식을 이용하는 것이다. 정규식은 분명 굉장히 유용하지만IDE도 못 쓰고 검색도 못하는 대부분의 코딩 테스트 특성상 정말 재수가 없게도 이런 문제를 만난다면 내 기억력에만 의존해야하며 점 하나까지 신경 써야하는 정규식보다 조금 돌아가는 길이 나을 수도 있다. 물론 이 문제를 푸는데 필요한 정규식은 굉장히 쉽기 때문에 '이 문제만 생각하면' 정규식을 외우는 게 더 편하다. 잘 모르겠어서 검색은 했는데 스스로 풀고 싶은 사람이라면 정답을 보기 전에 subString이나 indexOf를 활용해서 푸는 것을 시도해보자. 10분동안 생각해봤는데 모르겠으면 밑으로. BufferedReader || Sca..
JAVA 백준 문제풀이 (25) 2309: 일곱 난쟁이
CS ﹒ Algorithm/Baekjoon 2022. 7. 22. JAVA 백준 문제풀이 (25) 2309: 일곱 난쟁이 가짜 난쟁이를 찾아내는 문제인데 라는 문구가 눈에 띈다. 정답이 여러가지가 나올 수 있으며 무엇이 됐든 정답이면 통과할 수 있다는 의미이다. 상식적으로 생각해봐도 난쟁이들의 키의 합이 100이라는 사실만으로 걸러낸다면 진짜 난쟁이가 걸러질 수도 있겠다. 대다수의 저난이도 문제들이 그렇듯 복잡한 알고리즘이 필요한 문제는 아니지만 동일한 유형의 접해본 적이 없다면 헤맬 수도 있다. 힌트를 줄테니 바로 풀어보자. 주어지는 값으로 합을 구하려하지 말고 합에서 주어지는 값을 빼는 건 어떨까? 10분 고민해보고 답이 안나오면 밑으로 내려가자. static int dwarfs[] = new int[9]; public static void main(String[] args) throws IOException { inp..
JAVA 백준 문제풀이 (24) 11047: 동전 0
CS ﹒ Algorithm/Baekjoon 2022. 7. 20. JAVA 백준 문제풀이 (24) 11047: 동전 0 그리디 알고리즘 첫번째 문제이자 그리디 알고리즘을 전혀 몰라도 풀 수 있는 문제이다. 하지만 우리는 백준 정답 맞추기가 궁극적인 목표가 아니기 때문에 그리디 알고리즘에 대해 간단히 알아보자. 그리디 알고리즘(greedy algorithm)은 그 이름이 굉장히 잘 어울리는 알고리즘으로, 뒷 일은 신경쓰지 않고 무조건 당장 택할 수 있는 최선만을 선택하는 알고리즘이다. 예를 들어 우리가 편의점에서 아르바이트를 하고 있는데 4800원을 받았고, 최대한 효율적으로 돈을 거슬러주려면 어떻게 해야할까? 당연히 천원짜리 네 장, 오백원 한 개, 백원짜리 세 개를 거슬러주면 될 것이다. 그런데 컴퓨터에게 이것을 어떻게 명령할 수 있을까? 무조건 제일 큰 단위의 돈을 택해서 나눌 수 있을 때까지 나누고, 그 다음 단위의..

티스토리툴바