본문 바로가기

컴퓨터 공학/알고리즘11

[알고리즘 / Kotiln] 프로그래머스 - 수식 최대화 (2020 카카오 인턴십) 그동안 조금 공부를 게을리했던 것 같아서 다시 의지를 불태우기 위해 오랜만에 책상에 앉아서 프로그래머스를 들어갔다. 새로운 문제를 풀기보다는 예전에 풀어봤던 정확히는 눈으로 보았던 카카오 인턴십 문제를 다시 풀어보기로 했다. 1년 전에는 풀다가 포기한 문제였는데 다시 풀어보려니 왠지 모르게 긴장이 되었다. 이제부터라도 일주일에 최소 1개의 문제 푸는 습관을 들여야겠다. 수식 최대화 문제 설명 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다. 해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어.. 2022. 2. 8.

[알고리즘] BFS(Breadth-First Search) - 너비 우선 탐색 이번 시간에는 DFS에 이어 또 다른 그래프 탐색 방법인 BFS에 대해 정리해보려고 합니다. BFS 너비 우선 탐색(Breadth-First Search) 정의 : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 보통 두 노드 사이의 최단 경로를 찾고 싶을 때 사용합니다. 큐(Queue)를 사용하여 구현합니다. 이때 주의할 것은 어떤 노드를 방문했었는지 여부를 반드시 검색해야 합니다. 보통 모든 depth를 한 번에 탐색하기 때문에 단순 검색 속도는 DFS보다 빠릅니다. 하지만 노드의 수가 많아지고 깊이가 깊어지면 비효율적이라는 단점이 있습니다. 특징을 정리하면 Queue를 사용하여 구현, 이는 탐색할 정점들을 저장함으로써 저장공간이 많이 필요 그래프가 깊지 않고 규모가.. 2021. 12. 13.

[알고리즘] DFS(Depth-First Search) - 깊이 우선 탐색 DFS는 그래프(Graph)를 탐색하는 방법입니다. 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조를 말합니다. 코딩 테스트에서 BFS와 단골로 나오는 개념입니다. DFS 깊이 우선 탐색(Depth-First Search) 정의 : 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 말합니다. 자기 자신을 호출하는 순환 알고리즘이기 때문에 재귀 함수나 스택을 가지고 구현합니다. 이때 주의 사항은 어떤 노드를 방문했었는지 여부를 반드시 검사해야 합니다. 📘 Pseudo Code /** 1. 노드이 갯수 만큼 방문 여부를 위한 배열 생성 후 false로 초기화 (visit 배열) 2. 루트 노드부.. 2021. 12. 1.

[알고리즘 / Kotlin] 프로그래머스 - 큰 수 만들기 큰 수 만들기 문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24]를 만들 수 있습니다. 이 중 가장 큰 숫자는 94입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 1자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 입출력 예 내 풀이 처음에는 단순히 앞부분부터 최댓값을.. 2021. 11. 22.

[알고리즘 / JAVA] 까먹지 않기 위한 기본 정렬 알고리즘 코딩 테스트에서 정렬 문제는 자주 나옵니다. 하지만 보통 정렬 같은 경우에는 언어에 내장된 함수를 사용합니다. 그래서 개인적으로 정렬 알고리즘을 까먹는 부분이 있어서 이번 기회에 알면 좋을 4가지 정렬 알고리즘을 간략히 정리하려고 합니다. 선택 정렬 (Selection Sort) 현재 위치에 들어갈 데이터를 찾아 선택하는 정렬 알고리즘입니다. (시간 복잡도 : O(N^2)) ✏ 과정 정렬할 리스트에서 최솟값을 찾는다. 최솟값을 맨 앞 자리의 값과 교환 - Swap 맨 앞 자리 제외한 나머지 값들 중 최솟값을 찾아 다음 자리 값과 교환 이후 위의 과정을 반복 ✒ 코드 public static void main(String[] args) { int[] numbers = {1,2,5,7,8,11,10}; fo.. 2021. 11. 10.

[알고리즘 / Kotlin] 프로그래머스 - (10주차)교점에 별 만들기 교점에 별 만들기 문제 설명 Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다. 예를 들어, 다음과 같은 직선 5개를 2x - y + 4 = 0 -2x - y + 4 = 0 -y + 1 = 0 5x - 8y - 12 = 0 5x + 8y + 12 = 0 좌표 평면 위에 그리면 아래 그림과 같습니다. 이때, 모든 교점의 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5, 1.0)입니다. 이 중 정수로만 표현되는 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4).. 2021. 10. 17.

이전 1 2 다음

티스토리툴바