문제 설명고정점이란, 수열의 원소 중에서 원소 값 = 원소의 인덱스 인 원소를 말한다.예를 들어 수열 a = {-15, -4, 2, 8, 13}이 있을 때, a[2] = 2로 고정점은 2가 된다.하나의 수열이 N개의 서로 다른 원소를 포함하고 있고 오름차순으로 정렬되어 있을 때, 이 수열에서 고정점을 출력하는 프로그램을 작성하세요고정점은 최대 1개만 존재하고, 만약 없다면 -1 출력시간복잡도 O(log N)으로 알고리즘을 설계하지 않으면 '시간초과 판정' 입력조건첫째 줄에 N둘째 줄에 N개의 원소출력조건고정점 출력. 없으면 -1입출력 예시입력예시출력예시5-15 -6 1 3 737-15 -4 2 8 9 13 1527-15 -4 3 8 9 13 15-1 문제 풀이이진탐색을 수행해서 고정점을 찾는다.im..

문제 설명N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있을 때, 이 수열에서 x가 등장하는 횟수를 계산하세요.예를 들어 수열 {1, 1, 2, 2, 2, 2, 3}이 있을 때 x=2라면, 4를 출력시간복잡도 O(log N)으로 알고리즘을 설계하지 않으면 '시간초과 판정' 입력조건첫째 줄에 N과 x둘째 줄에 n개의 원소출력조건수열에서 값이 x인 원소의 개수값이 x인 원소가 없다면 -1입출력 예시입력예시출력예시7 21 1 2 2 2 2 347 41 1 2 2 2 2 3 -1 문제 풀이 시간복잡도 O(log N) 로 설계해야하기 때문에 순차 탐색으로는 풀 수 없다. → 이진탐색으로 풀이x가 처음으로 등장하는 위치와 마지막 위치를 찾아서 빼주면 x의 개수를 구할 수 있다.firstIndex()..

이진탐색(Binary Search)정렬된 데이터에서 탐색 범위를 절반씩 줄여나가면서 검색 값을 찾는 알고리즘탐색할 때마다 원소의 개수가 절반으로 줄어들기 때문에 속도가 빠르다시간복잡도 - O(log N)배열의 중간값(mid)을 구한다.중간값과 검색 값(target)을 비교한다. - 중간 값과 검색 값이 같으면 종료(mid == target) - 중간 값보다 검색 값이 크면 중간 값 기준 오른쪽 구역을 탐색(mid - 중간 값보다 검색 값이 작으면 중간 값 기준 왼쪽 구역을 탐색(mid > target)예제 1) 부품찾기전자 매장에 부품이 N개 있고, 각 부품은 정수 형태의 고유한 번호가 있다. 어느날 손님이 M개 종류의 부품을 대량으로 구매를 요청해서 견적서를 작성해야할 때, 가게 안에 부품..

[문제 링크]https://www.acmicpc.net/problem/10026문제 설명적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못해서 적록색약이 아닌 사람이 보는 그림과 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나누어지며, 하나의 구역은  상하좌우로 인접해있는 같은 색상일 경우 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)예를 들어, 그림이 아래와 같은 경우에RRRBBGGBBBBBBRRBBRRRRRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록..

[문제 링크]https://www.acmicpc.net/problem/2583문제 설명눈금의 간격이 1인 M×N 크기의 모눈종이 위에 K개의 직사각형을 그릴 때, K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 M, N, K둘째줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 두 꼭짓점의 x, y값(직사각형의 왼쪽 아래 꼭짓점, 오른쪽 위 꼭짓점)출력분리되어 나눠지는 영역의 개수각 영역의 넓이입출력 예시입력예시출력예시5 7 3 0..

[문제링크]https://school.programmers.co.kr/learn/courses/30/lessons/60058문제 설명개발자 "콘"은 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 한다.균형잡힌 괄호 문자열 - '(' 개수와 ')'의 개수가 맞을 경우올바른 괄호 문자열 - '('와 ')'의 괄호 짝도 모두 맞을 경우ex) "(()))(" 는 균형잡힌 괄호 문자열이지만 올바른 괄호 문자열은 아니다. "(())()"는 균형잡힌 괄호 문자열이면서 올바른 괄호문자열이다. '('와 ')'로만 이루어진 문자열 w가 "균형잡힌 괄호 문자열"이라면, 다음과 같은 과정을 거쳐서 "올바른 괄호 문자열"로 변환할 수 있다.1. 입력이 빈 문자열인 경우, 빈 문자열을..