분류 전체보기
-
큐 (Queue)전공공부/알고리즘&자료구조 2020. 1. 12. 20:14
큐는 First In First Out 구조이다. 기본 동작으로는 push,pop,size,empty 등이 있다. 이 기본 동작원리는 다음 문제를 통해 구현하였다. 출처:https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 소스코드
-
스택 (Stack)전공공부/알고리즘&자료구조 2020. 1. 12. 20:10
스택은 Last In First Out 구조이다. 기본 동작으로 push, pop, empty, size, top 등의 연산이 있고 다음 소스코드를 통해 어떻게 스택이 동작되는지 보자. 다음은 스택의 동작 구현에 관한 기본적인 문제이다. 출처:https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 소스코드 또한 스택을 활용하는 대표적인 문제는 괄호계산기이다. 다음 문제를 보자 출처:https://w..
-
합병정렬 (MergeSort)전공공부/알고리즘&자료구조 2020. 1. 12. 19:52
합병정렬은 대표적인 분할 정복 알고리즘이다. start==end가 되기 직전까지 분할을 계속 하다가 즉 start,start+1,// end-1,end 와 같이 분할이 단일범위까지 진행되다가 다시 이 단일 범위서부터 분할했던 경로 그대로 역순으로 되돌아가며 정복을 하는 알고리즘이다. 분할 정복을 하는 순서는 항상 다음을 따른다. mid=(start+end)/2를 기준으로 start~mid 부분인 좌측 부분의 분할이 먼저 이루어지고 그다음 mid+1~end까지 분할이 이루어진 후 합병이 시작된다. 즉 큰 틀로보면 왼쪽분할 - 오른쪽분할 - 정복 순서를 원자단위에서부터 차례차례 수행해 나가는 구조이다. 그리고 이를 그림으로 그려보면 다음과 같다. 원자단위로 왼쪽부터 분할 해 나간 후 오른쪽부분을 분할하고 정..
-
투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window)전공공부/알고리즘&자료구조 2020. 1. 12. 18:38
알고리즘 설명 출처: https://m.blog.naver.com/kks227/220795165570 투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09) 조금 성향이 비슷하다고 생각하는 기법 2개를 함께 쓰려 합니다.첫 번째로 소개해드릴 기법은 투 포인터(tw... blog.naver.com 투포인터 혹은 스라이딩 윈도우 기법은 연속적인 구간의 합이나 경우의 수를 구할때 매우 유용하다. 처음에 두개의 포인트 P1,P2를 설정하고 예를들어 배열의 구간 합이 특정 값을 만족할때 그 값을 만족하는 구간의 수를 구하는 문제가 있다. 이떄 배열이 모두 양수라고 가정을 하면 p2가 커질수록 합은 계속 증가하게 된다. 그래서 만약 합이 커..
-
이분탐색 (Binary Search)전공공부/알고리즘&자료구조 2020. 1. 12. 18:20
이분탐색 알고리즘 참고:https://wootool.tistory.com/62 [알고리즘] 이분 탐색 이분 탐색 탐색 기법중에 하나로 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식입니다. 그렇기에 원래의 전부를 탐색하는 탐색 속도에 비해 빠릅니다. 이분 탐색을 하는 방법은 left , right , mid 값으로 탐.. wootool.tistory.com 이분탐색 알고리즘은 주어진 범위 내에서 구하고자 하는 값을 절반씩 줄여나가며 탐색하는 알고리즘이다. 따라서 탐색하는데 걸리는 시간은 1/2씩 좁혀나가므로 O(logN)이 된다. 알고리즘에 대한 상세한 설명은 문제와 소스코드를 분석하며 보자. 백준: 2805 나무자르기 https://www.acmicpc.net/problem/2805 2805번: 나무..
-
#17406 배열 돌리기 4Code/BOJ 2020. 1. 5. 20:38
출처:https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다. 1 2 3 2 1 1 4 5 6 배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 www.acmicpc.net 회전 연산의 개수가 k 개 주어지고 모두 한번씩 사용돼야 한다. dfs를 통해 어떤 회전 연산을 적용시킬 지 순서를 정해..
-
#2718 타일 채우기Code/BOJ 2020. 1. 5. 20:31
출처:https://www.acmicpc.net/problem/2718 2718번: 타일 채우기 문제 4*N 크기의 타일을 2*1, 1*2 크기의 도미노로 완전히 채우려고 한다. 예를 들어 4*2 타일을 채우는 방법은 다음과 같이 5가지가 있다. N이 주어졌을 때, 타일을 채우는 방법의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1,000보다 작거나 같은 자연수이다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 타일의 너비 N이다. N은 자연수이다. N제한은 딱히 www.acmicpc.net 다음 열에서 타일이 놓여져 있을 경우는 다음 그림과 같이 0,1,2,3,4 번 상황으로 표현할 수 있다. 그것이 현재상황이라고 할..