알고리즘/백준 알고리즘

[백준 14501] 퇴사

글에 개요 백준 알고리즘 14501번 "퇴사" 문제입니다.삼성 SW 역량 테스트의 기출 문제입니다.[백준 14501] 퇴사 : https://www.acmicpc.net/problem/14501 참고할 글[완전탐색] : http://brenden.tistory.com/10[DFS] : http://brenden.tistory.com/13[BFS] : http://brenden.tistory.com/14핵심 내용DFS를 활용하는 문제 기저 사례에 주의하자!입력값 n을 받았을 때, 마지막날이 상담기간이 1일 경우 성립되므로 27 line과 같은 조건이 성립된다.재귀호출을 활용한 완전탐색 문제이다.2차원 배열을 활용해 입력값을 저장한다.해결 방법매개변수에 price, sum을 넣어주는 것에 주의해서 재귀호출 ..

2018. 4. 14. 21:50

알고리즘/백준 알고리즘

[백준 14503] 로봇 청소기

글에 개요 백준 알고리즘 14503번 "로봇 청소기" 문제입니다.삼성 SW 역량 테스트의 기출 문제입니다.[백준 14503] 연구소 : https://www.acmicpc.net/problem/14503 참고할 글[완전탐색] : http://brenden.tistory.com/10[DFS] : http://brenden.tistory.com/13[BFS] : http://brenden.tistory.com/14핵심 내용해당 조건에 맞게 풀면 되는 문제 (BFS를 활용 가능)조건을 걸어주는 부분을 신경써야 된다.좌표를 신경써서 설정해 줘야 문제 풀 때 쉽습니다.해결 방법visited 배열에 로봇이 청소한 구역을 표시하기 위한 변수 설정을 한다.조건 1~ 4번 순서대로 작성한다.방향 관련 함수를 만들어 준다..

2018. 4. 14. 19:57

알고리즘/백준 알고리즘

[백준 14502] 연구소

글에 개요 백준 알고리즘 14502번 "연구소" 문제입니다.삼성 SW 역량 테스트의 기출 문제입니다.[백준 14502] 연구소 : https://www.acmicpc.net/problem/14502 참고할 글[완전탐색] : http://brenden.tistory.com/10[DFS] : http://brenden.tistory.com/13[BFS] : http://brenden.tistory.com/14핵심 내용DFS + BFS를 활용한 문제시간이 오래걸렸던 부분은 바이러스를 찾을 때 새로운 배열에 map[][]을 옮기는 작업을 해야된다.map을 옮기는 작업을 안해줬을 때는(map[][]에 바이러스 퍼짐까지 표시했을 경우) 되돌려주는 작업을 추가해야된다!!map을 복사하는 과정에서 virusMap[][..

2018. 4. 14. 16:38

알고리즘/알고리즘 개념

[알고리즘] 너비 우선 탐색 (Breadth-first search, BFS)

너비 우선 탐색(Breadth-first search, BFS) ① 너비 우선 탐색이란? ▷ 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘입니다.▷ 프림의 최소 스패닝 트리 알고리즘 등이 너비 우선 탐색을 골격으로 하고 있습니다. ▷ 위의 그림을 너비 우선 탐색을 사용하면 H0(단계) -》 H1(단계) -》H2(단계) 순으로 방문합니다.▷ k단계에 방문하는 정점들은 시작점으로부터 최단거리가 k입니다. (H0(단계) : 0단계, H1(단계) : 1단계, H2(단계) : 2단계)▷ 최단거리는 이동하는 데 필요한 최소 개수의 간선으로 보면됩니다.▷ 각 정점을 방문할 때마다 모든 인접 정점들을 검사합니다. 이 중 처음 보는 정점을 발견하면 방문 예정이라고 기록해 둔 뒤, 모든 인접 정점을 검사한 후..

2018. 4. 12. 21:42

알고리즘/알고리즘 개념

[알고리즘] 깊이 우선 탐색 (depth-first search, DFS)

깊이 우선 탐색(depth-first search, DFS) ① 깊이 우선 탐색이란? ▷ 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법▷ 깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않습니다.▷ 깊이 우선 탐색의 중요한 특성은 더 따라갈 간선이 없을 경우 이전으로 돌아간다는 점입니다.▶ 깊이 우선 탐색 구현할 경우 : 스택(Stack)의 성질 활용(방문하는 순서대로 정점을 스택에 쌓고, 방문이 끝나면 스택에서 pop하는 형태로 구현) ※ DFS : 스택(Stack), BFS : 큐(Queue) 를 사용합니다.▶ 알고리즘 해결할 경우 : '재귀 호출'을 이용해 해결 (재귀 호출한 함수가 종료하면 호출한..

2018. 4. 12. 13:47

알고리즘/알고리즘 개념

[알고리즘] 완전탐색

글에 앞서... 재귀적 호출에 대한 개념을 먼저 설명드릴까합니다. 그 이유는 알고리즘에서 해당 호출방식을 자주활용하기 때문입니다. 재귀함수의 기본적인 이해 ** 재귀함수란?: 함수 내에서 자기 자신을 다시 호출하는 함수: 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수 ** 재귀함수 호출방식12345void RecursiveFunction(void){ printf("Recursive function example1 \n"); RecursiveFunction();}Colored by Color Scriptercs ※ 기저 사례 (base case)▷ 더 이상 쪼개지지 않는 가장 작은 작업, 즉 최소한의 작업에 도달했을 때 답..

2018. 4. 11. 21:46

알고리즘/알고리즘 개념

[알고리즘] 기본 정렬 알고리즘 (Sorting Algorithm)

정렬 알고리즘 개요 Name Best Worst (Big-O) Stable Memory 선택정렬 n² n² False 1 버블정렬 n n² True 1 삽입정렬 n n² True 1 합병정렬 nlogn nlogn True n 힙 정렬 nlogn 1 퀵 정렬 nlogn nlogn False 1 1. 선택정렬(Selection Sort) ① 개요 한번 순회를 하면서 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다.최소 선택 정렬(Min-Selection Sort) : 오름차순으로 정렬최대 선택 정렬(Max-Selection Sort) : 내림차순으로 정렬② 기본 로직 정렬 되지 않은 인덱스의 맨 앞부터, 그 이후의 배열값 중 가장 작은 값을 찾아간다.가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔..

2018. 3. 21. 20:20

알고리즘/알고리즘 개념

[알고리즘] 빅오 표기법(Big-O Notation), 시간복잡도, 공간복잡도

시간복잡도와 공간복잡도 시간복잡도 ▷ 속도에 해당하는 알고리즘의 수행시간 분석결과 공간복잡도 ▷ 메모리 사용량에 대한 분석결과 ※ 일반적으로는 중요도는 실행속도가 메모리 사용량보다 중요하다.※ 알고리즘의 성능을 판단하는 데 있어서 중요한 것은 '최악의 경우'이다. 빅-오 표기법(Big-O Notation) ▷ 빅-오는 시간 복잡도 T(n) 에서 가장 영향력이 큰 부분을 따지는 것이다.▷ 데이터 수의 증가에 따른 연산횟수의 증가형태를 나타내는 표기법이다. ex) T( n² + 2n + 1 ) 일 경우 빅-오 표기법으로는 O( n²) 이 된다. 빅-오 표기법의 성능(수행시간, 연산횟수) O( 1) < O( log n)

2018. 2. 1. 15:28