문제 설명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. 입력이 빈 문자열인 경우, 빈 문자열을..

문제 설명동빈이는 n × m 크기의 직사각형 형태의 미로에 갇혀 있다.동빈이의 위치는 (1, 1), 미로의 출구는 (n, m)이고, 한번에 한 칸씩 이동할 수 있다.미로에서 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어있을 때, 동빈이가 미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오.(칸을 셀 때는 시작칸과 마지막칸을 모두 포함해서 계산한다.) 입력조건첫째 줄에 정수 N, M다음 N개의 줄에 각각 M개의 정수로 미로의 정보출력조건최소 이동 칸의 개수입출력 예시입력예시출력예시5 610101011111100000111111111111110 문제 풀이최소 칸의 개수를 구하기 위해서 BFS 알고리즘 사용시작 지점에서 가까운 지점부터 차례대로 탐색하면서 값이 1일 경우queue에..