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

 

1932번: 정수 삼각형

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

www.acmicpc.net

 

문제 해결을 위한 과정

전형적인 다이나믹 프로그래밍 문제였습니다. 이 문제의 경우 숫자의 배열이 삼각형이라는 점이 존재하는데 이를 다음의 표처럼 입력받은 부분을 제외한 영역을 0을 채워주면 보다 쉽게 해결할 수 있습니다. 이 과정을 통해 0번째 열의 경우는 바로 위에 존재하는 숫자를 더해주면 되고 그 외의 경우는 위 행의 좌측 열 값과 위 행의 동일 열 값의 max값을 더해주는 과정을 반복해주면 쉽게 해결할 수 있습니다. 이를 점화식으로 표현하면 다음과 같습니다.

 

array[i][j] += max(array[i-1][j-1], array[i-1][j]) 

(단 열이 0번째가 아닌 경우)

 

1. 입력받은 곳을 제외하고 0으로 채운 상태

7 0 0 0 0
3 8 0 0 0
8 1 0 0 0
2 7 4 4 0
4 5 2 6 5

 

2. 적색 숫자는 0번째 열 이므로 위의 7을 그대로 더함, 청색 숫자는 좌측 위의 7과 위의 0중 최댓값인 7을 더함

7 0 0 0 0
10 15 0 0 0
8 1 0 0 0
2 7 4 4 0
4 5 2 6 5

 

3. 적색 숫자는 0번째 열 이므로 위의 10을 그대로 더함. 청색 숫자는 좌측 위의 숫자와 위의 숫자의 최댓값인 각각 15, 15를 더함

7  0 0 0 0
10 15 0 0 0
18 16 15 0 0
2  7 4 4 0
4 5 2 6 5

 

4. 적색 숫자는 0번째 열 이므로 위의 18을 그대로 더함, 청색 숫자는 좌측 위의 숫자와 위의 숫자의 최댓값인 각각 18, 16, 15를 더함

7 0 0 0 0
10 15 0 0 0
18 16 15 0 0
20 25 20 19 0
4 5 2 6 5

 

5.  적색 숫자는 0번째 열 이므로 위의 20을 그대로 더함. 청색 숫자는 좌측 위의 숫자와 위의 숫자의 최댓값인 각각 25, 25, 20, 19를 더함

7 0 0 0 0
10 15 0 0 0
18 16 15 0 0
20 25 20 19 0
24 30 27 26 24
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input())
array = [[0] * n for _ in range(n)] # 0으로 전부 채워진 이차원 배열 생성
for i in range(n):
  input_data = list(map(int, input().split()))
  for j in range(len(input_data)):
    array[i][j] = input_data[j]
 
for i in range(1, n):
  for j in range(n):
    if j == 0: # 0번째 열 인경우 
      array[i][j] += array[i-1][j]
    else: # 그 외의 
      array[i][j] += max(array[i-1][j-1], array[i-1][j])
 
answer = 0
for i in range(n):
  answer = max(answer, array[n-1][i])
print(answer)        
 cs

 

 

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

백준 알고리즘 18353: 병사 배치하기(Python)  (0) 2020.12.21
백준 알고리즘 14501: 퇴사 (Python)  (1) 2020.12.19
백준 알고리즘 2110: 공유기 설치 (Python)  (0) 2020.12.18
백준 알고리즘 18310: 안테나(Python)  (2) 2020.12.10
백준 알고리즘 16234: 국영수(Python)  (0) 2020.12.09

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

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 이진 탐색으로 해결할 수 있는 문제였습니다. 그러나 일반적인 이진 탐색을 이용한 방법의 경우 start, end를 이용하여 mid값을 잡아주고 찾아야 하는 target이 있는 반면 이 문제는 target이라는 것이 딱히 없습니다.

따라서 target을 설정하는 것이 아닌 이진 탐색의 방법을 응용해야 한다는 것입니다.

문제 해결의 과정은 다음과 같습니다. 

 

1. 집과 집 사이의 거리의 최솟값을 start로 최댓값을 end로 지정한다.

(문제에서 집 여러 개가 같은 좌표를 가지는 일은 없기 때문에 공유기 사이의 거리의 최솟값은 1, 최댓값은 입력받은 집들의 좌표를 정렬한 후 맨 마지막 원소와 맨 처음 원소 사이의 거리)

 

2. start와 end를 이용해 mid값을 구하고 해당 mid값을 공유기들 사이의 거리의 최솟값으로 정하였을때 C개만큼 설치할 수 있는지 확인한다.

 

3-1. C개만큼 설치할 수 없을 때는 공유기 사이의 거리가 큼. 따라서 end를 mid - 1로 설정하여 2번 과정 반복

3-2. C개만큼 설치할 수 있을 때는 공유기 사이의 거리를 하나씩 증가하여 최댓값을 찾음. 따라서 start를 mid + 1로 설정하여 2번 과정 반복

소스코드

 

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
N, C = map(int, input().split())
data = []
for i in range(N):
  data.append(int(input()))
 
data.sort()
 
start = 1 # 공유기 사이 거리 최솟값
end = data[-1] - data[0] # 공유기 사이 거리 최댓값
ans = []
 
while start <= end:
  prev = data[0]
  mid = (start + end) // 2
  count = 1
  for i in range(1, N):
    if prev + mid <= data[i]:
      prev = data[i]
      count += 1
  if count >= C:
    start = mid + 1
    ans.append(mid)
  else:
    end = mid - 1
 
print(max(ans))
    
        
 cs

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

백준 알고리즘 14501: 퇴사 (Python)  (1) 2020.12.19
백준 알고리즘 1932: 정수 삼각(Python)  (0) 2020.12.18
백준 알고리즘 18310: 안테나(Python)  (2) 2020.12.10
백준 알고리즘 16234: 국영수(Python)  (0) 2020.12.09
백준 알고리즘 16234: 인구이동(Python)  (0) 2020.12.07

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

 

코딩테스트 연습 - 가사 검색

 

programmers.co.kr

문제 해결을 위한 과정

이 문제의 경우 이진 탐색을 이용하여 푸는 문제라는 것을 알 수만 있다면 쉽게 해결할 수 있는 문제였습니다. 가장 먼저 문제의 조건을 보면 "?" 즉 와일드 문자가 들어갈 수 있는 곳은 접두사 즉 맨 앞, 혹은 접미사 즉 맨 뒤에만 존재할 수 있다고 합니다. 이 조건이 키포인트입니다.

 

1. 먼저 10001행을 가진 리스트 array와 10001행 리스트를 가진 리스트 reverse_array를 생성합니다. 그 후 words 리스트를 조회하면서 각 원소의 글자 수에 맞는 행에 array와 reverse_array에 삽입해 줍니다.

ex) frodo의 경우 5글자 이므로 array[5].append(frodo), reverse_array[5].append(frodo)를 수행해 줍니다. 

 

2. 1의 과정을 완료한 후 queries리스트를 조회하면서 원소가 ?로 시작하지 않으면 array의 해당 행에서 몇 개와 매치될수 있는지 찾고 그 값을 answer리스트에 append 해준다. 반대로 ?로 시작하면 해당 쿼리를 뒤집은 후 reverse_array의 해당 행에서 몇개와 매치될 수 있는지 찾는다. (단 이때 찾는 함수는 https://bgspro.tistory.com/27?category=981927 에서 소개한 count_by_range 함수를 이용하고 left_index와 right는 각각 "?"를 a로 치환한, 'z'로 치환한 값으로 설정한다.)

ex) 만약 fro?? 인 경우 ?로 시작하지 않고 5글자 이므로 array[5]에서 count_by_range(array, query.replace('?', 'a'), query.replace('?', 'b')를 수행한다. 

 

3. 위의 과정을 완료한 후 answer리스트를 return 한다.

문제 해결을 위한 팁

리스트를 손쉽게 역순으로 바꿀 수 있는 방법이 있습니다. 바로 인덱싱을 이용하는 방법인데 예시는 다음과 같습니다.

array = [1, 2, 3, 4, 5]의 경우 array [::-1]을 하게 되면 [5, 4, 3, 2, 1]로 바꿀 수 있습니다.]

소스코드

answer.append(ans)</div><div

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
from bisect import bisect_left, bisect_right
 
def count_by_range(a, left_value, right_value):
    left_index = bisect_left(a, left_value)
    right_index = bisect_right(a, right_value)
    return right_index - left_index
 
def solution(words, queries):
    answer = []
    array = [[] for _ in range(10001)]
    reverse_array = [[] for _ in range(10001)]
    
    for word in words:
        array[len(word)].append(word)
        reverse_array[len(word)].append(word[::-1])
        
    for i in range(10001):
        array[i].sort()
        reverse_array[i].sort()
        
    for i in queries:
        if i[0] != "?":
            ans = count_by_range(array[len(i)], i.replace('?', 'a'), i.replace('?','z'))
        else:
            ans = count_by_range(reverse_array[len(i)], i[::-1].replace('?','a'), i[::-1].replace('?','z'))
        answer.append(ans)
    return answer
 cs

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

신고 결과 받기(Python)  (0) 2022.02.20
실패율 (Python)  (0) 2021.01.11
블록 이동하기 (Python)  (0) 2020.12.07
괄호 변환 (Python)  (0) 2020.12.05
자물쇠와 열쇠 (Python)  (0) 2020.12.03
개념

이진 탐색이란 정렬되어있는 데이터 집합을 이분화하여 탐색하는 방법이다. 이때 정렬된 데이터가 키 포인트인데 정렬이 되어있지 않다면 쓸 수 없다. 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://programmers.co.kr/learn/courses/30/lessons/60063

 

코딩테스트 연습 - 블록 이동하기

[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7

programmers.co.kr

문제 해결을 위한 과정

이 문제의 경우 해결을 하기는 했는데 너무 복잡하게 해결해서 인터넷에서 간결한 코드를 찾다가 나동빈 님의 코드가 너무 간단명료하게 되어있고 set을 이용하는 저로서는 생각도 못해본 기발한 방법을 사용하셨기에 해당 코드를 아주 약간 변환해서 업로드합니다. 아직 멀었다는 것을 느끼며 포스팅합니다.

소스코드
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
from collections import deque
 
def can_move(pos, graph):
    next_pos = []
    pos = list(pos)
    lx, ly, rx, ry = pos[0][0], pos[0][1], pos[1][0], pos[1][1]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    for i in range(4):
        nlx, nly, nrx, nry = lx+dx[i], ly+dy[i], rx+dx[i], ry+dy[i]
        if graph[nlx][nly] == 0 and graph[nrx][nry] == 0:
            next_pos.append({(nlx, nly), (nrx, nry)})
    if lx == rx: # 가로인 경우
        for i in [-1, 1]:
            if graph[lx+i][ly] == 0 and graph[rx+i][ry] == 0:
                next_pos.append({(lx,ly), (lx+i, ly)})
                next_pos.append({(rx, ry), (rx+i, ry)})
    elif ly == ry: # 세로인 경우
        for i in [-1, 1]:
            if graph[lx][ly+i] == 0 and graph[rx][ry+i] == 0:
                next_pos.append({(lx, ly), (lx, ly+i)})
                next_pos.append({(rx, ry), (rx, ry+i)})
    return next_pos
 
def solution(board):
    n = len(board) + 2
    m = len(board)
    graph = [[1]*n for _ in range(n)]
    for i in range(m):
        for j in range(m):
            graph[i+1][j+1] = board[i][j]
    q = deque()
    visited = []
    pos = {(1, 1), (1, 2)}
    q.append((pos, 0))
    visited.append(pos)
    while q:
        pos, cost = q.popleft()
        if (m, m) in pos:
            return cost
        for next_pos in can_move(pos, graph):
            if next_pos not in visited:
                q.append((next_pos, cost+1))
                visited.append(next_pos)
    return 0
 
 
 cs

 

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

실패율 (Python)  (0) 2021.01.11
가사 검색 (Python)  (0) 2020.12.17
괄호 변환 (Python)  (0) 2020.12.05
자물쇠와 열쇠 (Python)  (0) 2020.12.03
모의고사 (Level 1 Python)  (0) 2020.11.30

+ Recent posts

티스토리툴바