본문 바로가기

성장 일기/알고리즘

성장 일기/알고리즘 2021. 8. 24. [2021 KAKAO] 신규 아이디 추천 (JAVA) 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 문제 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프로그램을 개발하는 것입니다. 다음은 카카오 아이디의 규칙입니다. 아이디의 길이는 3자 이상 15자 이하여야 합니다. 아이디는 알파벳 소..
성장 일기/알고리즘 2021. 8. 17. [JAVA]이진 탐색(Binary Search) 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 1/2씩 줄여가며 데이터를 탐색하는 방법. * 이진 탐색을 수행할 때는 탐색 범위를 명시해야한다. 따라서 시작점과 끝점 그리고 중간점을 이용하여 탐색한다. 예를 들어보자, 다음 정렬되어 있는 리스트에서 있는 5를 탐색하는 경우는 다음과 같다. 중간 인덱스 값은 리스트의 길이의 1/2 값을 사용한다. 리스트의 길이가 홀수라면 1/2값에서 소수첫째자리에서 버림한 값을 사용한다. 다음은 리스트에 없는 값인 2를 탐색하는 경우이다. 없는 값을 탐색하는 경우 더 이상 남은 항목이 없으면 탐색 실패로 -1를 리턴해준다. 이제 이진탐색의 코드를 확인해보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 2..
성장 일기/알고리즘 2021. 8. 8. [JAVA] 정렬 알고리즘(선택정렬) 정렬(Sorting) : 데이터를 특정한 기준에 따라 순서대로 나열하는 것 * 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용됨. 1. 선택 정렬 정렬이 완료되지 않은 데이터 중 가장 작은 (혹은 가장 큰) 데이터를 선택해 맨 앞에 (혹은 맨 뒤에) 있는 데이터와 바꾸는 것을 반복하는 알고리즘. * 마지막에 남은 숫자의 경우 정렬을 수행하지 않아도 된다. 수행 과정을 보면, 정렬이 되지 않은 숫자들을 하나씩 비교해가며 최소 값(최대 값)을 찾고 이를 정렬하는 과정을 반복한다. 따라서 이중 반복문을 사용하여 구현할 수 있다. ▶시간복잡도 : O(n^2) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import java.util.*;..
성장 일기/알고리즘 2021. 7. 12. [JAVA] 그리디 알고리즘(Greedy) 그리디 알고리즘(탐욕법) : 최적의 해를 구하는 방법으로, 그 상황에서 가장 좋은 것만을 고르는 방법을 의미한다. *그리디는 정당성 분석이 중요* 문제가 요구하는 최적의 해를 구할 수 있는지를 검토해야 한다. 일반적으로 최적의 해를 구하지 못하는 경우가 더 많다. 예를 들어보자, 위 그림처럼 생긴 트리의 경우 그리디 알고리즘을 이용해 최적의 해를 구하면 주황색과 같이 72라는 결과가 나온다. 하지만 위 트리의 경우, 최적의 해는 다음 그림의 파란색으로 110이다. 이와 같이 그리디 알고리즘을 이용해 최적의 해를 구하면 최적의 해가 아닐 수 있기 때문에 꼭 검증이 필요하다. 그리디 알고리즘 예 - 거스름 돈 주기 거스름 돈 문제의 최적의 해는 가장 큰 화폐 단위부터 거슬러주면 되기 때문에 그리디 알고리즘을..
성장 일기/알고리즘 2021. 5. 19. [JAVA]Dynamic Programming(동적 계획법) Dynamic Programming(dp) : 복잡한 문제를 풀기위해서 간단한 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 목적에 도달하는 방법. *배경 피보나치 수열은 다음과 같이 짧은 수학적 공식으로 표현된다. int Fibonacci(int n) { if(n
성장 일기/알고리즘 2021. 4. 13. [백준][자바(java)][dfs] #4963 섬의 개수 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. [입력] 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의..
성장 일기/알고리즘 2021. 4. 12. [백준][자바(java)][dfs] #11724 연결 요소의 개수 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. [입력] 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. [출력] 첫째 줄에..
성장 일기/알고리즘 2021. 4. 6. [JAVA(자바)] 깊이 우선 탐색(DFS) 그래프에서 모든 정점을 방문하는 방법에는 대표적으로 두가지가 있다. 1. 너비 우선 탐색(BFS: breath-first Search) 2. 깊이 우선 탐색 (DFS: depth-first search) 오늘은 깊이 우선 탐색에 대해 공부하고자 한다. 깊이 우선 탐색 : 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른방향으로 다시 탐색을진행한다. dfs(v){ v를 방문했다고 표시; for all u ∈ (v에 인접한 정점) do if(u가 아직 방문하지 않았다면) then dfs(u) } 그림과 같은 그래프가 있다. 시작 지점은 1이라고 하자. (여기서 갈래가 두개 이상이라면 가장 작은 수를 선택한다.) *한방향으로 갈 수 있을 때까지 ..

티스토리툴바