Algorithm 썸네일형 리스트형 BFS & DFS 구분하자! BFS & DFS (그래프 알고리즘) BFS & DFS. 삼성 SW 역량테스트에 핵심 주제이다.하지만, 이것만 잘 알고 코드를 구현한다고 테스트 케이스가 다 통과하는가? 답은 "아니다." 이유는 재귀 함수는 쉬운 것이고, 이와 관련된 코드를 구현하는 것, 시뮬레이션 작업이 더 어렵기 때문이다. 그렇다면 왜? 탐색 알고리즘에 집중해 있는지 알아보자. 탐색 알고리즘은 순회를 모두 하는 경우이기에, 연산량이 많고 그에 따라, 컴퓨터 활용이 많아진다.따라서, 기업에서 SW개발 직군을 뽑을 때, 컴퓨터 연산량을 잘 관리하고 효율적으로 코드를 짜는 사람을 뽑으려 하므로 탐색 알고리즘이 코드 구현에 핵심 요소라고 할 수 있다. 기본적으로 탐색은 컴퓨터 연산량을 극대화하는 작업이기에, 사람이 코드를 구현하고 디버깅하면.. 더보기 슬라임문제_삼성DS준비 안녕하세요! 오늘은 삼성전자 S직군 대비 슬라임 문제를 가지고 왔습니다. 2018 하반기 SW 역량테스트 중 SDS 문제와 비슷한 유형인데, 내가 이동하는 위치와 나의 위치값 차이를 비교하여 범위 내에 있을 경우 평균 값으로 대체하면서 재귀 진행을 하는 것입니다.문제는 아래와 같습니다. 비슷한 유형 문제 중에서는 많이 꼬지를 않아서 어려운 문제는 아니었다. 그렇지만 처음 접했다면 분명 당황했을 문제이므로 반드시 정리하자 핵심은 현재 노드에서 상하좌우 노드 값을 먼저 체크하고 (노드 == 슬라임) 차이를 비교해서 범위 안에 들어가는지 먼저 체크합니다.범위에 들어간다면, 해당 노드의 값을 합칩니다. (기존에 시작 노드는 값에 넣어놓은 다음에 시작할 예정)이렇게 상하좌우 모든 값을 비교해서 차이가 범위 내의 .. 더보기 Spiral Algorithm 달팽이 알고리즘이라고 부르는 이 나열형 배열 알고리즘은 푸는 방법은 다양합니다.탐색으로 풀 수도 있고 반복문을 넣어서 푸는 방법이 있습니다.저는 반복문을 통해서 답을 구해보겠습니다.반복문을 써서 푸는 이유는 알고리즘을 구현할 때 for문에 i를 배열의 인덱스로 가져가는 경향이 많아 문제 해소가 안되는 경우가 많습니다. 이러한 사고를 바꾸고 싶어서 다음과 같이 구현하였습니다.반복문은 말그대로 반복하는 횟수입니다.단순히 그렇게만 이해하면 될 것 같습니다. import java.util.Scanner; public class Spiral { private static Scanner scanner;private static int N;private static int board[][]; public static.. 더보기 SW_EXPERT 1861 정사각형 방 정사각형 방 문제 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE 문제 무단 배포를 막기 위해서 링크로 포스팅 하였습니다. 이번 문제는 전형적인 탐색입니다. 동서남북으로 이동할 수 있으며, 본인보다 값 1이 더 큰 방만 이동할 수 있다.이동할 경우 가장 방을 많이 방문하는 횟수와 그 출발 방을 구하시오.단! 횟수가 같을 경우 방 번호가 더 작은 값으로 출력해야 합니다. [전체 코드] import java.io.BufferedReader;import java.io.FileInputStream;import.. 더보기 SW_EXPERT_3234_준환이의 양팔저울 문제 링크는 아래 있습니다. 무단 복제가 허용되지 않기 때문에 링크로 걸어둔 점 양해바랍니다. https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWAe7XSKfUUDFAUw&categoryId=AWAe7XSKfUUDFAUw&categoryType=CODE 이 문제는 순열로 풀어도 되고 탐색으로도 되는데, 저는 탐색으로 풀었습니다.탐색할 때 중요한 것은 첫 번째 숫자를 집어 넣을 당시에 left에 먼저 넣어두고 다시 방문하지 않도록 체크하는 것입니다.가령, 예제에서 1 2 4 를 다루고 있으니 가져와서 설명하자면, LEFT 1 2 4 RIGHT 이런 식으로 LEFT에 먼저 값을 넣어주고 생각해야지, RIGHT에 먼저 .. 더보기 NN단 알고리즘 문제 핵심 아이디어는 이거다... 정말 충격이였다. 아니.. 정말 소름돋았다.N이 예제 입력처럼 3이라고 한다면 나올 수 있는 값은 아래와 같다. ----------1*1 = 11*2 = 21*3 = 3----------2*1 = 22*2 = 42*3 = 6----------3*1 = 33*2 = 63*3 = 9---------- 1 2 3 1 1 2 3 2 2 4 6 3 3 6 9 여기서 최소값은 1이고 최대값은 9입니다. 이걸 가지고 이진탐색을 하는 것입니다. 1부터 9사이의 값들 1,2,3,4,5,6,7,8,9 중 mid값을 구합니다. 중앙값을 구한 다음에 중앙값을 넘어가는 값은 (N*N단의 결과값 중) N으로 치부한다. 따라서 1~9사이의 mid값은 5이며, N(3)을 넘지 않는 것은 그 값 그대로 가.. 더보기 합병정렬 알고리즘 합병정렬 알고리즘은 퀵정렬과 마찬가지로 O(nlogn)의 시간복잡도를 가지며, 방법은 퀵정렬과 반대되는 느낌으로 풀면 됩니다. 퀵정렬은 본래의 배열을 피벗에 의해서 나눈 뒤, 왼쪽 배열과 오른쪽 배열로 나눠서 인덱스를 각각 구한 다음에, 피벗을 다시 설정하고 인덱스를 기준으로 초기의 배열을 재정의합니다.재정의한 배열은 인덱스로, 왼쪽 배열과 오른쪽 배열로 각각 나누어 다시 QuickSorting을 진행합니다.(재귀적) 다음은 합병정렬입니다. 합병정렬은 하나의 배열을 중앙값(인덱스)으로 나눈 뒤에, 각각 재귀적으로 합병정렬을 진행합니다. 아래 예시를 들어보겠습니다. 1 5 3 4 2 7 8 9 이 배열의 중앙을 반으로 나눕니다.[1 5 3 4] [2 7 8 9] 나눈 다음에 각각의 요소를 먼저 오름차순으로.. 더보기 퀵정렬알고리즘2 퀵정렬 알고리즘 두 번째 코드로 준비했습니다. 퀵정렬 알고리즘은 최선의 시간 복잡도 O(nlogn)을 가지며, 최악은 O(n^2)을 갖는 경우로, 재귀함수를 이용한 알고리즘의 표준이라 생각하면 됩니다. 그렇다면, 재귀함수를 이용한다고 하였기 때문에 먼저 재귀적 디자인을 해야합니다.함수의 역할을 직접 말로 표현해야하며, 기저조건으로 수렴하는지를 체크해야합니다.또한, 함수가 여러번 돌기 때문에, 원활하게 진행될 것이라 생각하고 구현해야합니다. 퀵정렬을 구현할 함수의 역할을 우선 말로 표현하자면 아래와 같습니다. 1. 기준이 될 Pivot을 정한다.2. Pivot 이하의 값을 갖는 요소들을 왼쪽 배열에, Pivot 초과의 값을 갖는 요소들을 오른쪽 배열에 저장한다.3. 각 배열은 1과 2 과정을 반복한다 (재.. 더보기 이전 1 2 3 4 ··· 6 다음
