개념

이진 탐색이란 정렬되어있는 데이터 집합을 이분화하여 탐색하는 방법이다. 이때 정렬된 데이터가 키 포인트인데 정렬이 되어있지 않다면 쓸 수 없다. start, end, mid를 이용하여 target을 탐색을 하는데 여기서 mid는 (start + end) // 2 한 값 즉 중간값이다. 이제 3가지 경우가 존재하는데 각각의 경우는 다음과 같다.

 

1. array[mid] == target 

2. array[mid] > target 

3. array[mid] < target

 

1번의 경우 단순하게 해당 mid값을 return 해주면 된다.

2번의 경우 중간값에 해당하는 값이 찾고자 하는 값 보다 크기 때문에 중간값 좌측의 구간만 다시 탐색을 해주면 된다. 따라서 end = mid - 1

3번의 경우 중간값에 해당하는 값이 찾고자 하는 값 보다 작기 때문에 중간값 우측의 구간만 다시 탐색을 해주면 된다.

따라서 start = mid + 1

구현은 재귀의 경우가 반복문의 경우보다 느리다고 알고 있기 때문에 더 효율적인 반복문의 형태로 구현을 한다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def binary_search(array, target, start, end):
  while start <= end:
    mid = (start + end) // 2
    if array[mid] == target:
      return mid
    elif array[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
  return -1 # target을 array에서 찾지 못한 경우
 
n, x = map(int, input().split())
data = list(map(int, input().split()))
result = binary_search(data, x, 0, n-1)
if result == -1:
  print("찾으시는 숫자가 존재하지 않습니다")
else:
  print(result + 1)
 cs

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

에라토스테네스의 체를 이용한 소수 판별 (Python)  (0) 2020.12.21
가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python)  (0) 2020.12.19
bisect 라이브러리를 이용한 손쉬운 이진탐색 (Python)  (0) 2020.12.15
BFS 너비 우선탐색 (Python)  (0) 2020.12.03
DFS 깊이 우선탐색 (Python)  (0) 2020.11.30
개념

파이썬은 일반적인 이진탐색보다 손 쉽게 이진탐색을 사용할 수 있는 라이브러리인 bisect를 지원합니다. 

물론 이진탐색을 하기 위해서는 리스트가 먼저 정렬이 되어있어야 합니다. 

bisect에는 여러가지 메소드가 있지만 bisect_left(), bisect_right()메소드를 가장 많이 사용합니다.

두 메소드의 장점은 O(logN)의 시간복잡도로 동작할 수 있다는 장점이 있습니다.

 

bisect_left(a, x) :  리스트 a에서 x가 들어갈 가장 왼쪽 인덱스를 반환합니다.

bisect_right(a, x) : 리스트 a에서 x가 들어갈 가장 오른쪽 인덱스를 반환합니다.

 

1 2 3 3 3 4 7

위의 리스트를 a라고 가정했을때 bisect_left(a, 3)이면 2를 반환합니다.

위의 리스트를 a라고 가정했을때 bisect_right(a, 3)이면 5를 반환합니다.

 

이걸 이용해서 bisect_right값과 bisect_left값을 빼면 3 즉 원소의 개수를 파악할 수 있는 count_by_range() 함수를 정의할 수 도 있습니다. 

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
from bisect import bisect_left, bisect_right
 
def count_by_range(array, left_value, right_value):
  left_index = bisect_left(array, left_value)
  right_index = bisect_right(array, right_value)
  result = right_index - left_index
  return result
 
array = [1, 2, 3, 3, 3, 4, 7]
print(bisect_left(array, 3)) # 3이 들어갈 가장 좌측 인덱스
print(bisect_right(array, 3)) # 3이 들어갈 가장 우측 인덱스
print(count_by_range(array, 3, 3))
 cs

 

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

에라토스테네스의 체를 이용한 소수 판별 (Python)  (0) 2020.12.21
가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python)  (0) 2020.12.19
이진탐색 (Python)  (0) 2020.12.16
BFS 너비 우선탐색 (Python)  (0) 2020.12.03
DFS 깊이 우선탐색 (Python)  (0) 2020.11.30

https://www.acmicpc.net/problem/18310

 

18310번: 안테나

첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 몇 가지 예시에 대해서 그림을 그리면 쉽게 해결할 수 있는 문제였습니다. 예시로 2, 2, 2, 8인 경우를 예로 들겠습니다. 문제에서 논리적으로 동일한 위치에 여러 개의 집이 존재하는 것이 가능하다고 하였기에 가능한 예시입니다. 2, 2, 2, 8인 경우 4가지의 값 중 중앙값인 2 그러니까 3번째 2에 안테나를 설치하면 거리는 (0 + 0 + 0 + 6)으로 쉽게 최솟값을 찾을 수 있습니다. 따라서 이 문제는 단순히 입력받은 숫자들 중 중간값을 출력해주면 됩니다.

소스코드

 

1
2
3
4
5
N = int(input())
data = list(map(int, input().split()))
data.sort()
 
print(data[N//2 - 1])
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1932: 정수 삼각(Python)  (0) 2020.12.18
백준 알고리즘 2110: 공유기 설치 (Python)  (0) 2020.12.18
백준 알고리즘 16234: 국영수(Python)  (0) 2020.12.09
백준 알고리즘 16234: 인구이동(Python)  (0) 2020.12.07
백준 알고리즘 18428: 감시 피하기(Python)  (0) 2020.12.05

https://www.acmicpc.net/problem/10825

 

10825번: 국영수

첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1

www.acmicpc.net

 

문제 해결을 위한 과정

이 문제는 정렬 알고리즘의 방식입니다. 문제에서 여러 가지 조건이 있는데 파이썬이 제공하는 기본적인 sort와 lambda만으로 해결이 가능한 문제입니다. 조건을 보면 다음과 같습니다.

  1. 국어 점수가 감소하는 순서로
  2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
  3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
  4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞에 온다.)

이를 lambda에 넣을 조건이라고 생각하면 국어 점수는 감소하는 순서 즉 내림차순으로 정렬이 되어야 하므로 국어점수를 음수로 바꾸어서.

영어 점수의 경우 오름차순이므로 그대로.

수학점수의 경우 내림차순이므로 음수로 바꾸어서

이름의 경우 사전 순으로 증가하는 즉 오름차순이므로 그대로 lambda에 조건으로 넣어주면 되는 것입니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
N = int(input())
data = []
for i in range(N):
  name, kor, eng, math = input().split()
  data.append((name, int(kor), int(eng), int(math)))
 
data.sort(key = lambda x: ((-x[1]), x[2], (-x[3]), x[0]))
 
for i in range(N):
  print(data[i][0])
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 2110: 공유기 설치 (Python)  (0) 2020.12.18
백준 알고리즘 18310: 안테나(Python)  (2) 2020.12.10
백준 알고리즘 16234: 인구이동(Python)  (0) 2020.12.07
백준 알고리즘 18428: 감시 피하기(Python)  (0) 2020.12.05
백준 알고리즘 14888: 연산자 끼워 넣기(Python)  (0) 2020.12.05

https://www.acmicpc.net/problem/16234

 

16234번: 인구 이동

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 bfs를 이용하여 해결하는 문제였습니다. 배열을 조회하다가 방문하지 않은 곳이 있다면 그 좌표에 한해서 절댓값의 차이가 L 이상 R이하인 곳을 탐색을 한 뒤 각각의 칸들의 평균값을 다시 대입을 해주면 되는 문제였습니다. 단지 까다로웠던 점은 while True: 를 통해 무한 반복할 때마다 visited를 계속 만들어서 계속 반복되게 해야 한다는 점이였습니다. 

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from collections import deque
import sys
input = sys.stdin.readline 
 
N, L, R = map(int, input().split())
graph = []
for i in range(N):
  graph.append(list(map(int, input().split())))
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
def bfs(xPos, yPos):
  q = deque()
  q.append((xPos, yPos))
  visited[xPos][yPos] = 1
  count = 1
  sum = graph[xPos][yPos]
  arr = [(xPos, yPos)]
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      # 그래프의 범위를 벗어나지 않은경우
      if 0 <= nx < N and 0 <= ny < N: 
        # 방문한 곳이 아니고 차의 절댓값이 L, R 사이일때
        if visited[nx][ny] == 0 and L <= abs(graph[nx][ny]-graph[x][y]) <= R:
          visited[nx][ny] = 1
          sum += graph[nx][ny]
          count += 1
          q.append((nx, ny))
          arr.append((nx, ny))
 
  if count > 1: # count가 2 이상인 경우
    ans = sum // count
    for a, b in arr: # 해당 지역에 인구 이동
      graph[a][b] = ans
    return True
  return False
      
      
count = 0
while True:
  visited = [[0]*N for _ in range(N)] # N행 N열짜리 visited리스트
  flag = False # 인구 이동할 칸의 유무를 체크하는 플레그 False로 초기화
  for i in range(N):
    for j in range(N):
      if visited[i][j] == 0 and bfs(i, j) == True: # 방문하지 않았고 bfs의 반환값이 참이라면
        flag = True
  if flag == False: # 인구이동할 칸이 없는 경우
    break
  elif flag == True: # 인구이동한 칸이 있는 경우 count를 하나 증가
    count += 1
 
print(count)
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 18310: 안테나(Python)  (2) 2020.12.10
백준 알고리즘 16234: 국영수(Python)  (0) 2020.12.09
백준 알고리즘 18428: 감시 피하기(Python)  (0) 2020.12.05
백준 알고리즘 14888: 연산자 끼워 넣기(Python)  (0) 2020.12.05
백준 알고리즘 18405: 경쟁적 전염(Python)  (0) 2020.12.05

https://www.acmicpc.net/problem/18428

 

18428번: 감시 피하기

NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 BFS로 해결하기보다는 문제의 조건을 따라서 해결하면 더 쉬웠던 문제입니다. 처음에 그래프입력을 받으면서 x인 곳을 blank라는 리스트에 따로 추가하고 T인 곳을 teacher이라는 리스트에 따로 추가를 해줍니다. 선생님들은 상, 하 , 좌, 우 4곳으로 볼 수 있고 방해물이 없다면 그래프의 끝까지 조회할 수 있으므로 방향 리스트인 dx, dy를 만들고 bfs함수를 정의합니다. 각 방향을 끝까지 조회하면서 빈칸인 경우 T로 방문처리를 해주거나, 방해물이 있는경우 그 뒤쪽은 볼수 없는 경우를 처리해주고, 학생을 찾은 경우 바로 bfs함수에서 False를 return해주면 쉽게 해결할 수 있습니다. 학생을 찾지 못한 경우는 True를 return해주면 되겠습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
from collections import deque
from itertools import combinations
import copy
 
n = int(input())
graph = []
teacher = []
blank = []
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
for i in range(n):
  graph.append(list(input().split()))
  for j in range(n):
    if graph[i][j] == 'T':
      teacher.append((i, j))
    elif graph[i][j] == "X":
      blank.append((i, j))
 
def bfs(): # 학생 찾으면 False 반환
  q = deque(teacher)
  test_graph = copy.deepcopy(graph)
  while q:
    x, y = q.popleft()
    for i in range(4):
      temp_x, temp_y = x, y
      while True:
        nx = temp_x + dx[i]
        ny = temp_y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
          if test_graph[nx][ny] == 'X':
            test_graph[nx][ny] = 'T'
          elif test_graph[nx][ny] == 'S':
            return False
          elif test_graph[nx][ny] == 'O':
            break
          temp_x, temp_y = nx, ny
        else:
          break
  return True
 
check = False
for data in list(combinations(blank, 3)):
  for x, y in data:
    graph[x][y] = 'O'
  if bfs():
    check = True
    break
  for x, y in data:
    graph[x][y] = 'X'
    
if check:
  print("YES")
else:
  print("NO")
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 16234: 국영수(Python)  (0) 2020.12.09
백준 알고리즘 16234: 인구이동(Python)  (0) 2020.12.07
백준 알고리즘 14888: 연산자 끼워 넣기(Python)  (0) 2020.12.05
백준 알고리즘 18405: 경쟁적 전염(Python)  (0) 2020.12.05
백준 알고리즘 14502: 연구소(Python)  (0) 2020.12.05

https://www.acmicpc.net/problem/14888

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 부호에 해당하는 리스트를 따로 만든 후 해당 리스트에서 보호의 순사가 바뀜에 따라 값도 바뀌게 되므로 순서가 중요한 순열로 뽑아야 합니다. 따라서 숫자의 경우 num이라는 리스트를 만들어 넣어주고 부호의 경우 따로 x라는 리스트를 만든 후 permutations를 통해 숫자보다 하나 적게 뽑은 후 ( 3 + 3처럼 부호의 경우 숫자보다 하나 적어야 함) 교차하여 부호와 숫자가 모두 포함이 된 리스트를 만든 후 이를 계산하는 calc함수를 구현하면 쉽게 해결할 수 있습니다.

문제 해결을 위한 팁

저의 경우 isdigit()를 통해서 부호와 숫자를 합쳐진 리스트에서 구별했는데 이때 int형애는 isdigit()을 사용할 수 없기 때문에 str을 이용하여 우선 다 문자 형태로 바꿔준 후에 isdigit()을 이용하였습니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
from itertools import permutations
 
def calc(arr):
  prev = int(arr[0])
  for i in range(1, len(arr)-1):
    if arr[i].isdigit() == False:
      if arr[i] == '+':
        prev += int(arr[i+1])
      elif arr[i] == '-':
        prev -= int(arr[i+1])
      elif arr[i] == '//':
        if prev >= 0:
          prev = prev // int(arr[i+1])
        else:
          prev *= -1
          prev = prev // int(arr[i+1])
          prev *= -1
      elif arr[i] == '*':
        prev *= int(arr[i+1])
  return prev
 
N = int(input())
num = list(map(int, input().split()))
numOfA, numOfB, numOfC, numOfD = map(int, input().split())
 
x = []
while True:
  if numOfA > 0:
    x.append('+')
    numOfA -= 1
  if numOfB > 0:
    x.append('-')
    numOfB -= 1
  if numOfC > 0:
    x.append('*')
    numOfC -= 1
  if numOfD > 0:
    x.append('//')
    numOfD -= 1
  if numOfA == 0 and numOfB == 0 and numOfC == 0 and numOfD == 0:
    break
 
maximum = int(1e9)*-1
minimum = int(1e9)
 
for xx in list(permutations(x, N-1)):
  j = 0
  arr = []
  for i in range(N-1):
    arr.append(str(num[i]))
    arr.append(str(xx[j]))
    j += 1
  arr.append(str(num[-1]))
  result = calc(arr)
  maximum = max(maximum, result)
  minimum = min(minimum, result)
 
print(maximum)
print(minimum)
 
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 16234: 인구이동(Python)  (0) 2020.12.07
백준 알고리즘 18428: 감시 피하기(Python)  (0) 2020.12.05
백준 알고리즘 18405: 경쟁적 전염(Python)  (0) 2020.12.05
백준 알고리즘 14502: 연구소(Python)  (0) 2020.12.05
백준 알고리즘 18352: 특정 거리의 도시 찾기(Python)  (0) 2020.12.04

https://programmers.co.kr/learn/courses/30/lessons/60058

 

코딩테스트 연습 - 괄호 변환

카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴

programmers.co.kr

문제 해결을 위한 과정

이 문제의 경우 재귀를 얼마나 잘 사용할 수 있느냐 그리고 구현 알고리즘을 얼마나 잘 사용할 수 있느냐가 중요한 문제였다고 생각합니다. 문제의 조건을 그대로 꼼꼼하게 코드로 옮기기만 한다면 쉽게 정답을 맞을 수 있는 문제였습니다.

먼저 재귀의 탈출 조건으로 빈 문자열이 들어온 경우 그대로 빈 문자열을 반환하는 것 과

문자열 W를 u, v로 분류하는 것입니다.

이 문제의 경우 균형 잡힌 괄호 문자열을 만드는 함수, 올바른 괄호 문자열인지 확인 하는 함수, solution함수 총 3개의 함수로 구분하여 코드를 작성하면 쉬운 문제였습니다.

균형 잡힌 괄호 문자열로 더이상 분류를 할 수 없게 최소한의 길이를 가진 u를 만들어 낼 수 있도록 균형잡인 괄호 문자열을 만드는 함수 balance함수에서 앞에서부터 몇번째 인덱스에서 최소한의 길이를 가진 균형잡인 괄호 문자열이 만들어지는지를 반환을 해주면 그 반환된 인덱스를 기준으로 리스트를 인덱싱 하여 u와 v를 구분할 수 있습니다.

그 후 u를 다시 올바른 괄호 문자열인지 확인하는 함수 correct를 통해 확인한 후 이 결과에 따라 문제의 조건처럼 재귀를 구현하면 되는 것입니다. 이후 과정은 문제를 소스코드로 그대로 옮기는 것이기 때문에 생략합니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def balanced(p):
    count = 0
    for i in range(len(p)):
        if p[i] == '(':
            count += 1
        elif p[i] == ')':
            count -= 1
        if count == 0:
            return i
        
def correct(u):
    count = 0
    for i in range(len(u)):
        if u[i] == '(':
            count += 1
        elif u[i] == ')':
            count -= 1
        if count < 0:
            return False
    return True
 
def solution(p):
    if p == '':
        return p
    answer = ''
    
    index = balanced(p)
    u = p[:index + 1]
    v = p[index + 1:]
    
    if correct(u):
        return (u + solution(v))
    else:
        answer += '('
        answer += solution(v)
        answer += ')'
        u = list(u)
        u = u[1:-1]
        for i in range(len(u)):
            if u[i] == '(':
                u[i] = ')'
            else:
                u[i] = '('
        answer += ''.join(u)
        return answer
 cs

'알고리즘 > 프로그래머스' 카테고리의 다른 글

가사 검색 (Python)  (0) 2020.12.17
블록 이동하기 (Python)  (0) 2020.12.07
자물쇠와 열쇠 (Python)  (0) 2020.12.03
모의고사 (Level 1 Python)  (0) 2020.11.30
기둥과 보 설치 (Python)  (0) 2020.11.29

+ Recent posts

티스토리툴바