본문 바로가기

CS ﹒ Algorithm

네트워크 (8) 이름이 귀여운 WAS와 Web Server에 대해 알아보자
CS ﹒ Algorithm/(구)Network 2022. 8. 7. 네트워크 (8) 이름이 귀여운 WAS와 Web Server에 대해 알아보자 내가 좋아하는 와스(이름이 귀엽다)와 웹 서버에 대해 알아보자. 웹 서버 (Web Server) 아주 고전적인 역할을 수행하는 서버로써, 클라이언트에서 서버에 정적인 컨텐츠를 요청하면 이를 제공하는 역할을 수행한다. ( HTML, CSS, Image, JS File.. ) 위의 그림에서 볼 수 있듯이 클라이언트의 요청(request)을 가장 먼저 받는 곳이다. 만약 정적 컨텐츠 요청이 들어왔다면 웹 서버에서 바로 응답(response)하고 통신이 끝나지만, 동적 컨텐츠라면 WAS에게 다시 Request를 전달한다. 웹 어플리케이션 서버 (a.k.a 와스, Web Application Server) 동적인 컨텐츠를 제공하기 위해 만들어진 애플리케이션 서버이다. 여기서 말하는 동적인 컨텐츠란 로직 처리가 요..
Java 백준 문제풀이 (36) 연산자 끼워넣기
CS ﹒ Algorithm/Baekjoon 2022. 8. 6. Java 백준 문제풀이 (36) 연산자 끼워넣기 삼성 SW 역량 테스트 기출 문제라고 한다. 맨날 무슨 초등부 중등부 올림피아드 문제들만 있어서 안 풀리면 자괴감 들었었는데, 삼성 코테 기출문제라고 하니 의욕이 더 솟아 올랐다. 문제 자체는 백트래킹만 할 줄 알면 누구나 풀 수 있을 정도로 쉽다. 백트래킹을 할 줄 모르면 당연히 DFS 알고리즘과 백트래킹은 배워와야 한다.. 1. 주어지는 정수와 기호를 배열로 받는다. 2. 기호의 개수가 정해져 있으니 중복순열이 아닌 순열을 구하는 방식으로 백트래킹해야 한다. 3. 백트래킹 + 브루트 포스를 활용하여 모든 경우의 수를 구한 뒤 최소값과 최대값을 출력하면 끝. 다만 늘 그렇듯 더 효율적인 풀이 방법이 있고 비효율적인 풀이 방법이 있다. 나는 풀고나서 다른 사람들의 정답을 보니 쓸데없이 한 바퀴 더 돌아서..
선형 탐색(Linear search)과 이진 탐색(Binary search)에 대해 알아보자 (Feat.JAVA)
CS ﹒ Algorithm/Algorithm 2022. 8. 4. 선형 탐색(Linear search)과 이진 탐색(Binary search)에 대해 알아보자 (Feat.JAVA) 고양이도 배울 수 있을 만큼 쉬운 선형 탐색과 이진 탐색에 대해 알아보자. 선형 검색 알고리즘 ( == Sequential search algorithme, Linear serach algorithm, 순차 검색, 선형 탐색) 가장 원시적인 형태의 데이터 탐색 알고리즘이다. 이것은 리스트에서 찾으려고 하는 값을 맨 앞부터 끝까지 차례대로 찾아 나가는 것이다. 검색할 리스트의 길이가 길면 길수록 비효율적이지만 단순하여 구현이 굉장히 쉽고, 정렬되지 않은 리스트에서도 사용할 수 있다는 장점이 있다. 선형 검색은 데이터를 찾기 위해 데이터를 하나씩 모조리 검사하므로 시간 복잡도는 최악의 경우(worst) O(n)이다. 예시) 어렵게 생각할 게 전혀 없다. 그냥 임의의 배열에서 반복문으로 특정 값을 찾고자 한다..
Java 백준 문제풀이 (35) 15651: N과 M (3)
CS ﹒ Algorithm/Baekjoon 2022. 8. 3. Java 백준 문제풀이 (35) 15651: N과 M (3) 중복 순열을 백트래킹으로 구하는 문제다. 2주 전에 접했을 때는 너무 어렵게 느껴졌었는데, 그래프를 먼저 배우고 와서 다시 보니 어처구니 없을 정도로 쉬운 문제였다. 대체 왜 단계별 알고리즘에 백트래킹을 그래프보다 앞에 둔 건가요 백준.. 백트래킹은 기본적으로 DFS 알고리즘을 조금 보완한 거라서 DFS 알고리즘을 먼저 배우고 와야한다. DFS 배우고 오면 진짜 별거 없음.. 이게 중복 순열을 구하는 알고리즘을 한 컷에 요약한 그림이다. (A,A,A) (A,A,B) (A,A,C) (A,B,A) (A,B,B) (A,B,C).. 백트래킹 알고리즘의 기본 뼈대는 이런 식이다. void 응애_백트래킹(int num) { if ( 만약에 조건에 부합한다면 ) { 값을 리턴해줘 } if ( 이 노드가 내가 찾는 값..
Java 백준 문제풀이 (34) 2609: 최대공약수와 최소공배수
CS ﹒ Algorithm/Baekjoon 2022. 8. 2. Java 백준 문제풀이 (34) 2609: 최대공약수와 최소공배수 최대공약수와 최소공배수는 유클리드 호제법을 이용하면 쉽게 구할 수 있다. 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알..
퀵 정렬(Quick Sort)에 대해 알아보자 (feat. JAVA)
CS ﹒ Algorithm/Algorithm 2022. 8. 1. 퀵 정렬(Quick Sort)에 대해 알아보자 (feat. JAVA) 퀵 정렬(Quick Sort) ? 퀵 정렬은 다른 원소와의 비교만으로 정렬을 수행하기 때문에 비교 정렬에 속한다. 퀵 정렬은 평균적으로 O(n log n)번의 비교를 수행하지만 최악의 경우 O(n²)번의 비교를 수행한다. 원소들 중에 같은 값이 있는 경우 같은 값들은 정렬 이후 초기와 순서가 달라질 수 있기 때문에 불안정 정렬이다. ( 예 : 5₁, 5₂, 3, 2, 1를 정렬하면 1, 2, 3, 5₁, 5₂ 이 된다. ) 실제 임상 자료(real-world data) 정렬 시 가장 빠른 알고리즘이다. * 퀵 정렬은 일반적인 보편적으로 가장 빠른 정렬 속도를 보여주는 분할-정복 알고리즘 중 하나이지만 오름차순, 내림차순 등 이미 정렬되어 있는 배열의 재정열에 사용 시 최악의 성능을 보여주고 일반적으로 우..
Java 백준 문제풀이 (33) 2667: 단지 번호 붙이기
CS ﹒ Algorithm/Baekjoon 2022. 8. 1. Java 백준 문제풀이 (33) 2667: 단지 번호 붙이기 기초적인 그래프 알고리즘 문제를 풀 수 있다면 어려운 문제는 아니지만 배열 4방향, 8방향 탐색을 해보지 않았다면 어떻게 풀어야하는 지 난해하게 느껴질 수 있다. 우선 힌트를 줄테니 한 번 생각해보고 모르겠으면 정답을 보도록 하자. 평소 dfs, bfs 문제 풀 때와 달라진 것은 오직 한 가지 밖에 없다. 10분 고민해보고 모르겠으면 정답을 보자! 너무 오래 고민하는 것도 시간 낭비다. 전혀 어려운 문제가 아니기 때문에 이번 기회에 알아가면 다음부터는 분명히 풀 수 있을테니 걱정하지 않아도 된다. 정답 import java.io.*; import java.util.ArrayList; import java.util.Collections; public class Main { static int[][] map..
Java 백준 문제풀이 (32) 1260: DFS와 BFS
CS ﹒ Algorithm/Baekjoon 2022. 7. 31. Java 백준 문제풀이 (32) 1260: DFS와 BFS 오늘도 날로 먹는 문제로 찾아왔다. 코드스테이츠에서 알고리즘을 과정을 진행하고 있어서 진 빠진다. DFS와 BFS의 기본 코드 작성법을 익히고 차이점을 눈으로 직접 확인하기 좋은 문제이다. 이 문제를 풀려고 시도하는 사람이 DFS와 BFS에 대해 전혀 모를리는 없으므로 기억이 흐릿할 때 보기 좋은 이미지를 첨부하는 것으로 이해를 돕도록 하겠다. 1. dfs public static void dfs(int v) { visited[v] = true; sb.append(String.valueOf(v)).append(" "); // 현재 정점과 연결된 정점 탐색 -> 해당 정점과 연결된 -> 연결된 -> ... for (int n : edges.get(v)) { if ( !visited[n] ) { dfs(n)..

티스토리툴바