mynameiscowjaehoon

카카오 2021 블라인드 테스트 에서도 나왔듯이 카카오 코딩테스트에서는 문자열 문제가 자주나온다. 이러한 유형의 문제를 Java로 풀때 손쉽게 풀 수 있는 replaceAll 메서드와 정규식에 대해서 알아보자. 코드 부터 살펴보면 위 링크에 있는 문제는 다음과 같이 해결하였다. class Solution { public String solution(String new_id) { String answer = ""; String pattern = "[^-_.a-z0-9]"; answer = new_id.toLowerCase() .replaceAll(pattern, "") .replaceAll("[.]{2,}", ".") .replaceAll("^[.]|[.]$", ""); if(answer.equals(""..

이전에 살펴본 서로소 집합 자료구조를 이용하여 그래프의 사이클여부를 판별해보자. 서로소 집합을 이용하면 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있으며 방향그래프의 사이클 여부는 DFS를 이용하여 판별 할 수 있다. 사이클 판별 알고리즘은 다음과 같다. 1. 각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인합니다. 1) 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Union) 연산을 수행합니다. 2) 루트 노드가 서로 같다면 사이클(Cycle)이 발생한 것 입니다. 2. 그래프에 포함되어 있는 모든 간선에 대하여 1번 과정을 반복합니다. 코드로 구현하면 다음과 같다. import java.io.BufferedReader; import java.io.IOException; impo..

서로소 집합 자료구조는 서로소 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조는 두 종류의 연산을 지원한다. 1. 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 2. 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 Union과 Find 두 종류의 연산을 지원한다고 해서 Union-Find 자료구조 라고 불리기도 한다. 여러개의 합치기 연산이 주어 졌을 때 서로소 집합 자료구조의 동작 과정은 다음과 같다. 1. 합집합(Union)연산을 확인하여 서로 연결된 두 노드 A, B를 확인한다. 1) A와 B의 루트 노드 A', B'를 각각 찾는다. 2) A'를 B'의 부모 노드로 설정한다. 2. 모든 합집합(Uni..

플로이드 워셜 알고리즘은 모든노드에서 다른 모든 노드까지의 최단경로를 계산하고자 할때 사용할 수 있는 알고리즘이다. 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행합니다. 다만 매 단계마다 방문하지 않은 노드 중에 최단거리를 가지는 노드를 찾는 과정이 필요하지 않다. 2차원 테이블에 최단거리 정보를 저장하며 2차원테이블에 기록되어 있는 값을 점화식에 따라 갱신한다는 점에 따라 다이나믹 프로그래밍 유형에 속하기도 한다. 각 단계마다 특정한 노드 k를 거쳐가는 경우를 확인하며 a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다. 점화식은 다음과 같다. 자바 코드로 나타내면 다음과 같다. import java.io.BufferedReader..

최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 최단경로 알고리즘에는 다음과같이 세개의 경우가 있다. 1. 한 지점에서 다른 한지점까지의 최단 경로 2. 한 지점에서 다른 모든 지점까지의 최단 경로 3. 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현되고, 지점 간 연결된 도로는 그래프에서 간선으로 표현된다. 이중에서도 다익스트라 최단경로 알고리즘은 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산하는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않는다. 다익스트라 최단경로 알고리즘은 그리디 알고리즘으로 분류된다. 매 상황에서 가장 비용이 적은 노..

탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 탐색알고리즘 중 대표적인 그래프 탐색알고리즘으로 DFS와 BFS가 있다. DFS (Depth-First Search) DFS는 깊이우선 탐색이라고 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택을 이용해서 구현할 수 있으나 재귀함수는 실행되는 과정이 스택과 같이 먼저 호출한 함수가 제일 나중에 실행되는 특징이 있기때문에 대부분 스택보다는 재귀함수를 이용해서 구현한다. 구체적인 동작과정은 다음과 같다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 노드가 하나라도 잇으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접노드가 없으면 스택에..