본문 바로가기

CS ﹒ Algorithm

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..
네트워크 (7) HTTP 헤더 - 2 - 쿠키와 캐시
CS ﹒ Algorithm/(구)Network 2022. 7. 26. 네트워크 (7) HTTP 헤더 - 2 - 쿠키와 캐시 쿠키 ( Cookie ) Cookie: Cookie: name=value Cookie: name=value; name2=value2; name3=value3 쿠키란? HTTP 쿠키는 서버가 사용자의 웹 브라우저에 전송하는 작은 데이터 조각이다. 브라우저는 이 데이터 조각들을 저장해놨다가 동일한 서버에 재요청 시 저장된 데이터를 함께 전송한다. 무상태(statless)프로토콜에서 상태 정보를 기억시켜주는 역할을 한다. * 쿠키는 네트워크 트래픽을 추가적으로 유발할 수 있다. * 쿠키는 최소한으로 사용되고, 최소한의 정보만 입력되어야 한다. * 서버에 전송하지 않고 localStoreage, sessionStorage라는 웹 스토리지를 이용하는 방법도 있다. 쿠키의 주 사용처는? > 세션 관리 : 서버에 저..
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 프로그래머스 문제풀이 (3) 소수 만들기
CS ﹒ Algorithm/Programmers 2022. 7. 25. JAVA 프로그래머스 문제풀이 (3) 소수 만들기 그래프 탐색이나 기타 새로운 알고리즘 문제에 도전하고 싶은데 다른 공부도 할 게 너무 많아 원래 알던 범위에서 빙글빙글 돌며 양치기나 하고 있다.. 이러다가 6개월 내내 백준 실버 프로그래머스 1레벨 문제만 풀고 있는 건 아니겠지..? 쩝.. 아무튼 오랜만에 만난 소수 구하기 문제이다. https://7357.tistory.com/104?category=1065986 0부터 n까지의 수 중 소수 구하기 : 에라토스테네스의 체 고대 그리스 수학자 에라토스테네스가 발견한 소수를 구하는 간편한 방법이다. 알고리즘 중에 그나마 쉬운 편에 속한다. (1) 우선 0과 1은 소수가 아니기때문에 제외한다. (2) 소수인 2를 제외한 2 7357.tistory.com 몇 번째 우려먹는 건지 모르겠지만 저난이도의 소수 관..
프로그래머스 문제 풀이 (2) 완주하지 못한 선수
CS ﹒ Algorithm/Programmers 2022. 7. 24. 프로그래머스 문제 풀이 (2) 완주하지 못한 선수 " 배열 두 개 드릴테니까 거기서 다른 값 한 개 찾아내세요. " 라는 문제다. 사실 기본적인 for문을 배웠다면 누구나 풀 수는 있다. 어떤 방법을 택하냐의 문제지. 이 문제의 카테고리가 Hash인 만큼, 시간이 오래 걸리는 문제는 아니기 때문에 완전 단순한 for문과 해시를 사용한 for문 두가지로 나누어 풀고 속도를 측정해봤다. * 문제를 풀고 난 뒤 다른 사례를 찾아봤는데 2중 for문을 사용하는 경우 간당간당하게 통과하거나 실패하는 사례도 있는 것 같다. 어지간하면 다 통과. 1. 기본 for문 import java.util.*; class Solution { public String solution(String[] participant, String[] completion) { Arrays.s..

티스토리툴바