문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1806 부분합 제출 언어: Swift 알고리즘 분류: 누적 합 두 포인터 풀이 투포인터 알고리즘 1차원 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다 정렬되어 있는 두 list의 합집합에서 사용 (merge sort의 기초) 포인터는 2개로, start-end로 설정하며 초기에는 stard=end=0 이고 항상 start 현재 result값과 end - start(현재 원소의 최소 길이)중 작은 값으로 초기화 temp값(현재 원소의 부분 합)에서 현재 원소 값을 빼준다 start += 1을 해준다 (앞 포인터를 오른쪽으로 한 칸 이동시킨다) case2. 끝 포인터가 배열의 끝에 도달할 경우 while문을 끝..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 1700 멀티탭 스케줄링 제출 언어: Swift 알고리즘 분류: 그리디 알고리즘 * * * 풀이 그리디 알고리즘 `Greedy`는 '탐욕스러운'이란 뜻으로, 선택의 순간마다 당장 주어진 상황중 최선의 solution이라고 판단되는 것을 선택하는 알고리즘이다 - 가장 최선의 solution만을 계산하므로 메모리 사용량이 적다 - 빠르지만 최적의 해 solution을 보장할 수는 없다 -> 각 단계마다 선택한 최적해가 전체 최적해를 만든다는 보장은 할 수 없음 - 동작과정 - 해 선택 : 현재 상태에서 부분 문제의 최적해를 구한 뒤, 이를 부분해 집합에 추가한다 - 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지 확인하고, 문제의 제약 조건을 위..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 14719번 빗물 제출 언어: Swift 알고리즘 분류: 구현 시뮬레이션 문제 2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까? 입력 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다. 따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다. 출력 2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라. 빗물이 전혀 고..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 2504번 괄호의 값 제출 언어: Swift 알고리즘 분류: 구현 자료 구조 스택 문제 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 ..
문제 정보 문제 출처: 백준 온라인 저지 문제 링크: 14888번 연산자 끼워넣기 제출 언어: Swift 알고리즘 분류: 브루스포스 백트래킹 DFS 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들..
문제 [Codility] https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/ A non-empty array A consisting of N integers is given. Array A represents numbers on a tape. Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1]. The difference between the two parts is the value of: |(A[0] + A[1] + ..
문제 준식이는 수열 A[1], A[2], ..., A[N] (N ≥ 3) 을 가지고 있다. 이 수열에서 단 한 개의 수를 제외하고 나머지 수는 모두 같다. 그 수는 수열에서 몇 번째에 위치할까? 입력 첫째 줄에 테스트 케이스의 개수 T 가 주어진다. 각 테스트 케이스의 첫째 줄에 수열의 길이 N (3 ≤ N ≤ 100)이 주어진다. 둘째 줄에 A[1], A[2], ..., A[N]이 주어진다. 수열의 i번째 원소는 정수 A[i] (1 ≤ A[i] ≤ 100)이다. 주어지는 수열에서 단 한 개의 수를 제외하고 나머지 수는 모두 같다. 출력 각 테스트 케이스마다 문제의 정답이 수열에서 몇 번째에 위치하는지 출력한다. // 입력 1 5 1 4 4 4 4 // 출력 : 1 풀이 이번 문제는 배열을 순회하는 간단..
문제 현진이는 길거리를 걸을 때 에어팟으로 노래를 듣는다. 현진이는 자신만의 플레이 리스트가 있기 때문에 집을 나설 때 마다 플레이 리스트의 노래를 순서대로 이어서 듣고, 모든 플레이 리스트를 들었다면 처음부터 다시 반복 재생해서 듣는다. 현진이의 플레이 리스트는 N 개의 곡으로 이루어져 있다. 각각의 곡의 길이(초)를 B[1], B[2], … , B[N] 이라고 하자. 현진이는 집을 나선지 1 초가 지난 시점부터 B[1] 초까지 1 번째 노래를 듣고, B[1] + 1 초부터 B[1] + B[2] 초까지 2 번째 노래를 듣는 식으로 나머지 모든 노래를 듣는다. 예를 들어 현진이의 플레이 리스트에 있는 3 개의 곡의 길이가 각각 3, 1, 2 라고 하자. 현진이가 집을 나선지 1 초부터 3 초까지는 첫 번..
