jamnn_424.log

Ubuntu 개인 서버 만들기

Fri, 04 Oct 2024 19:57:17 GMT

앞으로 진행할 프로젝트는 개인용/기업용 서버가 필요하다.

필요한 이유:

기업의 보안 자료들을 NAS로 관리하기 때문에 연동하기 용이
Cafe24 내 서버와 통신할 웹앱 서비스를 제작하기 위한 HTTPS 자체서버 존재의 유무

Ubuntu 이미지 USB 만들기

https://ubuntu.com/download/desktop#how-to-install 사이트에 접속하여 이미지 파일을 다운 받은 후 USB에 이미지 파일을 만들었다.

Ubuntu Server 와 Ubuntu Desktop의 차이

같은 쉘을 사용하기 때문에 GUI가 있고 없고의 차이이며 추후 NAS연결과 사용성을 고려해 Desktop으로 설치

Ubuntu 설치가 후

카페 24 API를 HTTPS 테스트 서버를 구축하여 테스트 할 예정

[백준] 단축키 지정 (1283번)

Sat, 28 Sep 2024 21:26:34 GMT

난이도 : Silver2 Link : https://www.acmicpc.net/problem/1283 Tag : 구현, 문자열 풀이일자 : 2024년 9월 29일

📌 문제 탐색하기

N : 옵션의 개수 Word : 옵션 이름 Words : 두 단어 이상 일 때 첫 문자를 우선시 하기 위해 만든 배열

이 문제는 단축키를 지정하는 문제이다.

첫 글자가 이미 단축키로 지정되어 있지 않다면 단축키로 지정
모든 단어의 첫 글자가 이미 단축키라면 왼쪽부터 차례대로 지정
어떠한 것도 지정할 수 없다면 그대로 놔두기 + 대소문자 구분 x

해당 조건들을 만족시키면 되는 문제이다.

가능한 시간복잡도

N(1 ≤ N ≤ 30) 옵션의 개수는 최대 30개이고 하나의 옵션은 5개 이하의 단어이며 10개 이하의 알파벳 이므로 한 옵션의 최대치는 10 x 5 x 30 이므로 시간 복잡도 상 문제는 없어보인다.

📌 문제 접근 방법

해당 문제는 별다른 알고리즘은 떠오르지 않아 구현 스타일로 접근할 예정이다. 먼저 단어들의 첫글자가 우선이 되어야 함으로 단어들의 첫글자들을 먼저 탐색해서 바꾸는 작업을 진행할 것이다. 그 뒤로 첫 글자들이 바뀌지 않았다면 처음 문자부터 차례대로 바꿔나가는 방법을 사용할 것이다.

📌 코드 설계하기

N을 입력받는다.
단축어로 지정한것을 저장하는 hotkey 배열을 만든다.
정답을 출력할 것들을 저장할 배열 answer을 만든다.
n만큼 반복하며 옵션들을 입력받는다.
옵션의 단어 개수가 여러개일 수 있기 때문에 words를 통해 분리시킨다.
단어들의 첫 글자들을 먼저 검사한다.
- 만일 단어들의 첫글자가 hotkey에 배정되지 않았다면 배정시키고 break시켜버린다.
- 모든 단어들을 탐색한뒤 배정을 했다면 setting을 true로 바꿔준다
  1. setting이 false라면 왼쪽부터 차례대로 글자들을 배정한다.
  2. answer을 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

n = int(input())
hotkey = []
answer = []

for i in range(n):
    word = input()
    words = word.split()
    setting = False
    for j in range(len(words)):
        first_char = words[j][0]
        if first_char.upper() not in hotkey:
            hotkey.append(first_char.upper())
            words[j] = '[' + first_char + ']' + words[j][1:]
            answer.append(' '.join(words))
            setting = True
            break

    if not setting:
        for char in word:
            if char.upper() not in hotkey and char != ' ':
                hotkey.append(char.upper())
                tmp = '[' + char + ']'
                index = word.index(char)
                answer.append(word[:index] + tmp + word[index + 1:])
                setting = True
                break
    if not setting:
        answer.append(word)

for i in answer:
    print(i)

[백준] 점프점프 (11060번)

Sat, 28 Sep 2024 09:33:56 GMT

난이도 : Silver2 Link : https://www.acmicpc.net/problem/11060 Tag : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이일자 : 2024년 9월 28일

📌 문제 탐색하기

N : 미로의 크기 grid : 미로칸마다 점프 할 수 있는 값

이 문제는 각 칸의 숫자만큼 점프를 할 수 있으며 마지막 칸에 도달할 수 있는지 확인하는 문제이다. 마지막 칸으로 도달할때는 최소 점프 갯수를 구해야 한다.

가능한 시간복잡도

N(1 ≤ N ≤ 1,000) grid(0 ≤ grid ≤ 100) 이므로 각 모든 칸의 점프 할 수 있는 경우의 수를 전부 구하는 것은 시간 복잡도 상 문제가 있을것으로 보여 BFS를 통해 처음으로 마지막 칸에 위치하는 곳이 가장 적은 점프를 통해 도달한 것이므로 BFS를 통해 문제를 접근 하고자 한다.

📌 문제 접근 방법

BFS는 최소 경로를 찾는 데 적합한 알고리즘이기 때문에, 처음으로 도달할 수 있는 끝 칸에 도착하면 그것이 최소 점프 횟수가 된다.

따라서 이 문제는 BFS를 통해 문제를 접근한다.

📌 코드 설계하기

N과 grid를 입력받는다.
queue에 현재 위치, 점프 횟수를 추가한다.
vistied 배열에 방문한 위치를 추가한다.
answer를 -1로 초기화 한다.
BFS 알고리즘을 진행한다.
- 현재위치와 점프 횟수를 queue에서 꺼낸다.
- 만약 현재 위치가 마지막 칸이라면 반복문을 종료하고 answer = step으로 업데이트한다.
- 그렇지 않을때 해당칸에서 갈 수 있는 곳들을 체크한다.
```
for i in range(1, grid[now]+1):
  can_jump =  now + i
  if can_jump < N and can_jump not in visited:
      queue.append((can_jump, step + 1))
      visited.append(can_jump)
```
  1. answer를 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

from collections import deque

N = int(input())
grid = list(map(int, input().split()))

queue = deque([(0, 0)]) #위치, 점프횟수
visited = [0]
answer = -1

while queue:
    now, step = queue.popleft()
    if now == N - 1:
        answer = step
        break

    #현재칸에서 갈 수 있는 곳 체크
    for i in range(1, grid[now]+1):
        can_jump =  now + i
        if can_jump < N and can_jump not in visited:
            queue.append((can_jump, step + 1))
            visited.append(can_jump)

print(answer)

[백준] 정수 a를 k로 만들기 (25418번)

Wed, 25 Sep 2024 11:40:19 GMT

난이도 : Silver3 Link : https://www.acmicpc.net/problem/25418 Tag : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이일자 : 2024년 9월 25일

📌 문제 탐색하기

A : 주어진 양의 정수 K : 만들 정수

연산 1번 : A + 1 연산 2번 : A * 2 본 문제는 A에서 1번 연산방법과 2번 연산방법을 이용하여 최소 연산으로 K를 만들어내는 문제이다.

가능한 시간복잡도

1 ≤ A < K ≤ 1,000,000 이므로 최대한 적은 연산의 모든 경우의 수를 탐색하려고 했을때 연산 2번을 통해 A와 K의 격차를 크게 줄일 수 있으므로 시간 복잡도 상 문제는 없을 것으로 보인다.

📌 문제 접근 방법

이 문제를 보는 순간 접근 방법은 두가지로 떠올랐다. 첫번째 방법은 DP 방법으로 연산 1번 2번의 경우들을 저장하면서 A가 K랑 같아지는 경우를 찾는경우이다. 두번째 방법은 BFS 방법으로 방문 노드를 확인하고, 방문한 적이 없다면 연산을 진행하여 만들 수 있는 정수들을 찾고 K와 같아졌을 때 값을 찾아내는 것이다.

첫번째 방법으로 본 문제를 풀려고 접근했으나, 각 연산 방법을 정할때마다 2가지 경우로 나눠지는 것을 생각했을 때 배열의 크기가 너무 커질 것이라 생각이들어 두번째 방법으로 문제를 접근하였다.

📌 코드 설계하기

a, k를 입력받는다.
queue에 a값과 연산 횟수를 deque로 추가한다
visited 배열에 a 값을 집합형식으로 저장한다
- 배열 형식으로 했을 때 찾는 시간복잡도 보다 집합 형식의 시간복잡도가 적게 걸리기 때문이다.
queue값이 있을때 까지 BFS 탐색을 진행한다.
- now에 현재값을 answer에 연산 횟수를 저장한다.
- 만약 now값이 k와 같을 경우 반복문을 종료하고 answer값을 출력한다.
- 만약 now+1값이 visited에 없고 k보다 작거나 같으면 queue에 now값과 연산횟수 answer를 업데이트 한다.
- 만약 now*2값이 visited에 없고 k보다 작거나 같으면 queue에 now값과 연산횟수 answer를 업데이트 한다.

📌 시도 회차 수정 사항

📌 정답 코드

from collections import deque

a,k = map(int,input().split())

queue = deque([(a,0)]) #a값, 연산횟수
visited = set([a])
answer = 0
while queue:
    now, answer = queue.popleft()

    if now == k:
        break
    if (now + 1) <= k and (now + 1) not in visited:
        visited.add(now + 1)
        queue.append((now+1, answer+1))
    if (now * 2) <= k and (now * 2) not in visited:
        visited.add(now * 2)
        queue.append((now*2 , answer + 1))


print(answer)

[백준] 용액 (2467번)

Tue, 24 Sep 2024 00:14:12 GMT

난이도 : Gold5 Link : https://www.acmicpc.net/problem/2467 Tag : 구현, 이분탐색, 두 포인터 풀이일자 : 2024년 9월 24일

📌 문제 탐색하기

N : 용액의 개수 list : 용액 특성값 리스트

본 문제는 두 용액을 더해서 0과 가장 가까운 용액을 만드는 것이 목표이다.

가능한 시간복잡도

용액의 수인 N은 2 <= N <= 100,000 이며 각 용액의 특성값은 -1,000,000,000 이상 1,000,000,000 이하이다. 최악의 시간복잡도에서 N = 100,000일때, 구할 수 있는 조합의 개수는 100,000 x 99,999이므로 시간복잡도상 문제가 발생할 수 있다.

따라서 본 문제는 투포인터 기법과 이분탐색을 통해 접근해야 한다.

📌 문제 접근 방법

투 포인터를 사용할 것으므로 두가지 포인터를 잡아야 한다.

여기서는 이미 정렬된 배열을 주기 때문에 start포인터는 가장 작은 용액 특성, end포인터는 가장 큰 용액 특성으로 잡고 시작한다.

그 다음 이분탐색을 이용하여 두 포인터의 위치를 변경해줄 예정이다. 이분탐색을 진행하면서 절대값중 가장 작은 값을 answer에 저장한다.

📌 코드 설계하기

n과 list를 입력받는다.
answerdp 초기값 abs(list[0]+list[-1])를 저장한다.
answer_index_start 포인터와 answer_index_end 포인터를 생성한다
이분탐색에 사용될 start와 end를 설정한다.
이분탐색을 진행한다.
- tmp에 이분탐색하면서 answer와 비교할 용액을 저장한다.
- 만약 절대값 tmp가 answer보다 작다면 answer를 abs(tmp)로 업데이트 한다.
- answer_index_start와 answer_index_end를 start와 end로 업데이트 한다.
- 만약 tmp < 0 라면 , start의 위치를 바꿔 이분탐색을 진행한다.
- 만약 tmp > 0 라면, end의 위치를 바꿔 이분탐색을 진행한다.
- 만약 tmp = 0 라면, 반복문을 종료한다.
합친 용액 두개를 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

n = int(input())
list = list(map(int, input().split()))

answer = abs(list[0]+list[-1])
answer_index_start = 0
answer_index_end = n-1

start = 0
end = n-1
while start < end:
    tmp = list[start]+list[end]
    if abs(tmp) < answer:
        answer = abs(tmp)
        answer_index_start = start
        answer_index_end = end

    if tmp < 0 : #음수일 경우 시작점 index+1
        start = start + 1
    elif tmp > 0: #양수일 경우 끝점 index-1
        end = end - 1
    else: #0일 경우 종료
        break
print(list[answer_index_start], list[answer_index_end])

[백준] 나무 자르기 (2805번)

Sun, 22 Sep 2024 17:00:52 GMT

난이도 : Silver 2 Link : https://www.acmicpc.net/problem/2805 Tag : 이분탐색, 매개 변수 탐색 풀이일자 : 2024년 9월 23일

📌 문제 탐색하기

N : 나무의 개수 M : 가져갈 나무의 길이 tree : 나무의 높이

가능한 시간복잡도

N의 크기는 1,000,000 이며 M의 크기는 2,000,000,000 이므로 나무의 개수대로 1부터 자를 수 있는 모든 조건을 계산하는 것은 시간복잡도상 문제가 발생한다.

따라서 이분탐색을 통해 자를 수 있는 조건을 탐색하는 횟수를 줄여야 한다.

📌 문제 접근 방법

이분탐색을 통해 자를 경우의 수를 구해야한다. 자를 높이인 시작점을 start 자를 높이의 마지막 점을 end로 만든다. start와 mid의 중간지점을 자르는 높이라고 가정하고 이분 탐색을 시작한다.

주어진 문제에서 집에 필요한 나무를 딱 맞춰서 가져갈 필요는 없기 때문에 mid 범위에서 잘랐을때 설정된 높이가 큰 값을 answer로 저장하면 된다.

📌 코드 설계하기

N, M을 입력받는다.
tree를 입력받고 sort하여 정렬한다.
find_height 함수를 생성한다.
- 이 함수에서 이분탐색이 진행된다.
- start = 0 end = tree[-1] 로 지정한다.
- start와 mid의 중간값을 mid로 설정한다.
- mid로 설정된 절단기로 모든 나무들을 잘랐을때 값이 M보다 크거나 같다면 answer에 저장하고, start = mid + 1로 업데이트 한다.
- mid로 설정된 값으로 잘랐을때 그 외 경우라면 end = mid -1로 업데이트한다.
answer를 출력한다.

📌 시도 회차 수정 사항

틀렸습니다. (시간초과)

문제에서 적어도 M미터의 나무를 가져가기 위해서 설정한 높이를 구해야 하는데 높이를 딱 맞춰서 갈 수 있겠금 if문을 작성하여 딱 맞추는 경우가 불가능할때 무한 루프에 빠지는 모습을 볼 수 있었다.

📌 정답 코드

import sys
N,M = map(int, sys.stdin.readline().split())
tree = list(map(int, sys.stdin.readline().split()))
tree = sorted(tree)

def find_height():
    start = 0
    end = tree[-1]
    while start <= end:
        tmp = 0
        mid = (start + end) // 2
        for i in range(N):
            if tree[i] - mid > 0:
                tmp += tree[i] - mid
        if tmp >= M:
            answer = mid
            start = mid + 1
        else:
            end = mid - 1
    return answer

print(find_height())

[백준] 선분 위의 점 (11663번)

Sun, 22 Sep 2024 13:26:26 GMT

난이도 : Silver 3 Link : https://www.acmicpc.net/problem/11663 Tag : 이분탐색, 정렬 풀이일자 : 2024년 9월 22일

📌 문제 탐색하기

N : 점의 개수 M : 선분의 개수 grid : 점 좌표

본 문제는 주어진 점과 선분에서 시작점과 끝점이 주어졌을 때 주어진 점이 몇개 있는지 구하는 문제이다.

가능한 시간복잡도

주어진 점을 정렬하는 시간O(nlogn) M개의 선분을 이분 탐색으로 처리하는 시간 O(mlogn) 따라서 전체적인 시간복잡도는 nlogn + mlogn 이다.

📌 문제 접근 방법

먼저 주어진 점의 좌표를 정렬하여 이분탐색 할 수 있는 상태로 만들 것이다. 그리고 매번 주어지는 시작점과 끝점의 위치를 탐색하기 위해 이분탐색을 도입할 것이다. 이분탐색을 통해 시작점과 끝점에서 포함되는 점의 개수를 출력하면 끝이다.

📌 코드 설계하기

n,m을 입력받는다.
grid를 입력받고 정렬한다.
find_start 이분탐색 함수를 만든다.
- start = 0으로 초기화
- end = n-1로 초기화 하여 시작과 끝의 인덱스를 나타낸다.
- while start <= end 를 통해 시작점과 끝 인덱스가 작거나 같을때 까지 진행한다.
- mid 중간 인덱스를 (start+end)//2 를 통해 지정한다.
- if grid[mid]
- 그렇지 않다면 a값이 mid값보다 작으므로 end = mid-1로 지정한다.

find_start 이분탐색 함수를 위와 같이 만든다.

m번 동안 a,b를 입력받아 find_end - find_start를 한뒤 +1을 해줘 점의 개수를 구한다.

📌 시도 회차 수정 사항

틀렸습니다. (시간초과) input를 사용했을때 시간초과가 발생하였다. import sys를 통해 시간초과를 해결했다.

📌 정답 코드

import sys
n,m = map(int, sys.stdin.readline().split()) #n:점 m:선분 개수
grid = list(map(int, sys.stdin.readline().split()))
grid = sorted(grid)

def find_start(a):
    start = 0
    end = n - 1
    while start <= end:
        mid = (start + end) // 2
        if grid[mid] < a:
            start = mid + 1
        else:
            end = mid - 1
    return end + 1

def find_end(b):
    start = 0
    end = n - 1
    while start <= end:
        mid = (start + end) // 2
        if grid[mid] > b:
            end = mid - 1
        else:
            start = mid + 1
    return end

for i in range(m):
    a,b = map(int, sys.stdin.readline().split())
    print(find_end(b)-find_start(a) + 1)

[백준] 어두운 굴다리 (17266번)

Sat, 21 Sep 2024 11:30:21 GMT

난이도 : Silver 4 Link : https://www.acmicpc.net/problem/17266 Tag : 구현, 이분탐색 풀이일자 : 2024년 9월 21일

📌 문제 탐색하기

N : 굴다리의 길이 M : 가로등의 개수 locate : 가로등의 위치 height : 가로등 높이

이 문제는 주어진 굴다리 길이에서 가로등으로 비출 수 있는 최소 높이로 모든 곳을 비추게 하는 것이 목표이다.

가능한 시간복잡도

가로등이 없는곳에서 - 첫번째 가로등 가로등과 가로등 마지막 가로등에서 - 가로등이 없는 길

이렇게 3가지로 나눠 3가지 거리중 가장 큰 값을 비출 수 있는 최소 높이를 구하게 되면 문제를 해결할 수 있다. 따라서 가로등의 개수의 따라 시간복잡도는 달라지므로 O(m)이 된다.

📌 문제 접근 방법

가로등이 없는곳 - 첫번째 가로등 가로등과 가로등의 거리 마지막 가로등 - 가로등이 없는곳

3가지 거리를 구하고 3가지 거리중 가장 큰 값을 비출 수 있는 가로등의 최소 높이를 구할 것이다.

이때 거리를 구할때 가로등과 가로등 사이의 거리가 홀수인 경우에는 가로등 사이 거리를 구해 나누기 2를 해준 값에서 +1을 해주어야 한다.

📌 코드 설계하기

n,m,locate를 입력받는다.
height를 0으로 초기화 한다.
height의 값을 가로등이 없는곳에서 첫번째 가로등까지의 거리로 초기화 한다.
가로등과의 거리중 가장 긴 거리를 비출 수 있는 높이로 height를 업데이트 한다.
마지막 가로등과 마지막 길까지의 거리와 현재 가로등 높이와 비교하여 비출 수 있는 가장 작은 높이로 업데이트 한다.

📌 시도 회차 수정 사항

틀렸습니다. (8%) 가로등 사이의 거리가 홀수인 경우 내림이 발생하여 빈곳이 발생함

📌 정답 코드

n = int(input()) #굴다리 길이
m = int(input()) #가로등 개수
locate = list(map(int, input().split())) #가로등 위치

#가로등 높이
height = 0

height = max(height, locate[0])
for i in range(1,m):
    if (locate[i]-locate[i-1]) % 2 == 0:
        height = max(height, (locate[i] - locate[i-1])//2)
    else:
        height = max(height, (locate[i] - locate[i-1])//2+1)
height = max(height, n - locate[-1])

print(height)

[백준] 트럭 (13335번)

Fri, 20 Sep 2024 10:32:45 GMT

난이도 : Silver 1 Link : https://www.acmicpc.net/problem/13335 Tag : 구현, 자료구조, 시뮬레이션, 큐 풀이일자 : 2024년 9월 20일

📌 문제 탐색하기

N : 트럭의 개수 W : 다리의 길이 L : 다리 최대 하중

본 문제는 트럭의 무게가 순서대로 주어지고, 다리를 최단 시간으로 건널 수 있는 시간을 구하는 문제이다.

가능한 시간복잡도

다리의 길이와 트럭의 개수가 가능한 시간복잡도에 영향을 준다. N은 1000이하 W는 100 이하 이므로 최악의 시간복잡도는 1000 * 100이므로 시간복잡도 상 문제는 없어 보인다.

📌 문제 접근 방법

deque를 이용하여 왼쪽방향과 오른쪽 방향에서 0과 트럭의 무게를 추가해주고 빼주면서 다리의 최대 하중을 넘지 않는지 확인하려고 한다.

경우의 수는 다음과 같다.

트럭이 다리 위에 올라 갈 수 있는 경우 - 차가 그저 추가되는 경우 - 차가 빠지고 차가 추가되는 경우 - 다리 위에 차가 지나갈때까지 기다리는 경우 - 추가되는 차는 없고 다리위에 차가 지나갈때 까지 기다리는 경우

다음과 같은 경우의 수들을 if문을 통해 걸리는 시간을 체크하려고 한다.

📌 코드 설계하기

n,w,l을 입력받는다.
car배열에 트럭의 무게를 저장한다.
bridge배열에 w길이만큼 0을 저장한다.
car_deque와 bridge_deque에 car와 bridge배열을 추가한다.
while문을 반복한다 (car_deque에 원소가 없거나 or birdge_deque에 모든 값이 0일때까지)

앞서 말한 조건들을 추가한다.

if len(car_deque) != 0:
     if sum(bridge_deque) + car_deque[0] <= l:
         bridge_deque.append(car_deque.popleft())
         bridge_deque.popleft()
         answer += 1
     else: #지나갈때 까지 차가 다리에 추가 못하는 경우
         bridge_deque.append(0)
         bridge_deque.popleft()
         answer += 1
         # 차가 빠져나가면서 차가 추가되는 경우
         if sum(bridge_deque) + car_deque[0] <= l and bridge_deque[-1] == 0:
             bridge_deque[-1] = car_deque.popleft()
 else: #추가될 차는 없고 다리에 차가 있을경우
     bridge_deque.append(0)
     bridge_deque.popleft()
     answer += 1

answer를 출력한다.

📌 시도 회차 수정 사항

틀렸습니다. (1%) 조건을 잘못 맞췄다.

📌 정답 코드

from collections import deque
n,w,l = map(int,input().split()) # n: 자동차 개수 # w : 다리 길이  # l : 최대 하중
car = list(map(int,input().split()))
bridge = [0] * w
car_deque = deque(car)
bridge_deque = deque(bridge)

answer = 0

while car_deque or sum(bridge_deque) != 0:
    #다리 위에 올라 갈 수 있는 경우 (1.차가 추가 2.차가 빠지고)
    if len(car_deque) != 0:
        if sum(bridge_deque) + car_deque[0] <= l:
            bridge_deque.append(car_deque.popleft())
            bridge_deque.popleft()
            answer += 1
        else: #지나갈때 까지 차가 다리에 추가 못하는 경우
            bridge_deque.append(0)
            bridge_deque.popleft()
            answer += 1
            # 차가 빠져나가면서 차가 추가되는 경우
            if sum(bridge_deque) + car_deque[0] <= l and bridge_deque[-1] == 0:
                bridge_deque[-1] = car_deque.popleft()
    else: #추가될 차는 없고 다리에 차가 있을경우
        bridge_deque.append(0)
        bridge_deque.popleft()
        answer += 1
print(answer)

[백준] 오목 (2615번)

Thu, 19 Sep 2024 11:45:18 GMT

난이도 : Silver 1 Link : https://www.acmicpc.net/problem/2615 Tag : 구현, 브루트포스 알고리즘 풀이일자 : 2024년 9월 19일

📌 문제 탐색하기

본 문제는 오목에 대한 기초적인 문제이다. 어떤 플레이어가 이겼는지 확인하는 문제이다.

1, 2는 플레이어의 색을 의미한다.

가능한 시간복잡도

오목판의 크기는 19 x 19 이므로 모든 오목판을 탐색하면서 1또는 2가 있을때 연속해서 몇개의 돌이 있는지 계산하면 되므로 시간 복잡도상의 문제는 없을 것으로 보인다.

📌 문제 접근 방법

오목판을 탐색하여 1 또는 2가 존재했을 때 오목이 될 수 있는 방향대로 5개의 오목알이 존재하는지 확인할 것이다.

또한 출력 조건에서 다섯개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로 일경우 가장 위) 라는 조건을 충족 시키기 위해서 탐색하는 과정에서 8방향으로 탐색하는것이 아니라 4방향으로 탐색하여 중복 탐색되는 것을 막고 출력할 조건을 만족할 예정이다.

📌 코드 설계하기

grid를 입력받는다. (바둑판 상황)
omok 플래그를 False로 설정한다.
중복을 제외하고 출력 형식을 맞출 탐색 방향 4가지를 추가한다.

dx = [1, 1, 1, 0] # 오른쪽, 오른쪽 아래, 아래, 왼쪽 아래 dy = [0, 1, -1, 1] # 방향에 따른 y 변화
grid를 탐색하여 1또는 2인것을 찾는다.

찾았다면 4방향으로 탐색하여 갯수를 센다.

     if grid[i][j] != 0:  # 바둑알이 있는 경우
         player = grid[i][j]
         for m in range(4):  # 4방향 탐색 (반대방향은 하지 않음)
             cnt = 1  # 현재 위치에서 시작
             nx, ny = j, i  # 현재 위치

             # 5개의 돌이 연속적으로 있는지 확인
             for k in range(4):  # 최대 4칸 더 탐색 (총 5칸)
                 nx += dx[m]
                 ny += dy[m]
                 if 0 <= nx < 19 and 0 <= ny < 19 and grid[ny][nx] == player:
                     cnt += 1
                 else:
                     break

돌의 개수가 5개라면 6목인지 아닌지 판단한다.

# 5개의 돌이 연속되는 경우
             if cnt == 5:
                 # 6목인지 확인 (앞쪽 돌이 같은지)
                 prev_x = j - dx[m]
                 prev_y = i - dy[m]
                 if not (0 <= prev_x < 19 and 0 <= prev_y < 19 and grid[prev_y][prev_x] == player):
                     # 6목인지 확인 (뒤쪽 돌이 같은지)
                     next_x = nx + dx[m]
                     next_y = ny + dy[m]
                     if not (0 <= next_x < 19 and 0 <= next_y < 19 and grid[next_y][next_x] == player):
                         print(player)  # 승리한 돌 색 출력
                         print(i + 1, j + 1)  # 시작 좌표 출력 (가장 왼쪽/위쪽 돌 좌표)
                         omok = True
                         break

omok플래그가 false라면 0을 출력한다.

📌 시도 회차 수정 사항

틀렸습니다. (8%) 시작좌표를 출력하는데 문제점이 있었다. 가로 방향과 세로방향을 신경쓰지 못해 출력하는 방향을 재 지정하였다.
틀렸습니다. (18%) 시작좌표를 출력하는데 문제점이 있었다. 대각선일 경우 위에 있는 것을 출력해야하는데 중복된 탐색 때문에 아랫부분을 출력하는 경우도 존재하였다.
틀렸습니다. (25%) 아직 승부가 결정되지 않았을 경우 0을 출력해야하는데 이에 대한 조건을 추가하지 않았다.

📌 정답 코드

grid = []

for i in range(19):
    grid.append(list(map(int, input().split())))

dx = [1, 1, 1, 0]  # 오른쪽, 오른쪽 아래, 아래, 왼쪽 아래
dy = [0, 1, -1, 1]  # 방향에 따른 y 변화

omok = False

for i in range(19):  # i는 y좌표
    if omok:
        break
    for j in range(19):  # j는 x좌표
        if omok:
            break
        if grid[i][j] != 0:  # 바둑알이 있는 경우
            player = grid[i][j]
            for m in range(4):  # 4방향 탐색 (반대방향은 하지 않음)
                cnt = 1  # 현재 위치에서 시작
                nx, ny = j, i  # 현재 위치

                # 5개의 돌이 연속적으로 있는지 확인
                for k in range(4):  # 최대 4칸 더 탐색 (총 5칸)
                    nx += dx[m]
                    ny += dy[m]
                    if 0 <= nx < 19 and 0 <= ny < 19 and grid[ny][nx] == player:
                        cnt += 1
                    else:
                        break

                # 5개의 돌이 연속되는 경우
                if cnt == 5:
                    # 6목인지 확인 (앞쪽 돌이 같은지)
                    prev_x = j - dx[m]
                    prev_y = i - dy[m]
                    if not (0 <= prev_x < 19 and 0 <= prev_y < 19 and grid[prev_y][prev_x] == player):
                        # 6목인지 확인 (뒤쪽 돌이 같은지)
                        next_x = nx + dx[m]
                        next_y = ny + dy[m]
                        if not (0 <= next_x < 19 and 0 <= next_y < 19 and grid[next_y][next_x] == player):
                            print(player)  # 승리한 돌 색 출력
                            print(i + 1, j + 1)  # 시작 좌표 출력 (가장 왼쪽/위쪽 돌 좌표)
                            omok = True
                            break
if omok == False:
    print(0)

[백준] 숫자야구 (2503번)

Tue, 17 Sep 2024 23:04:30 GMT

난이도 : Silver 3 Link : https://www.acmicpc.net/problem/2503 Tag : 구현, 브루트포스 알고리즘 풀이일자 : 2024년 9월 18일

📌 문제 탐색하기

N : 질문의 개수 num : 질문한 숫자 strike : 위치,숫자 맞은 개수 ball : 숫자만 맞고 위치는 틀린 숫자 개수

가능한 시간복잡도

정답이 가능한 개수는 1~9까지 숫자로 만들 수 있는 3가지 순열 방식이므로 10P3이 된다. 따라서 경우의 수는 720가지이다. 숫자에 대한 질문을 할때마다 경우의 수는 작아지므로 시간 복잡도 상 문제는 없을것으로 본다.

📌 문제 접근 방법

먼저 가능한 정답을 만들어줄 예정이다. 가능한 정답과 질문한 숫자로 만들 수 있는 숫자의 경우의 수들을 비교해서 strike와 ball 의 개수를 비교하여 실제로 맞을 수 있는 답안을 answer에 업데이트 해줄 예정이다.

📌 코드 설계하기

n을 입력받는다.
answer을 초기화 한다
- answer에는 답이 될 수 있는 경우의 수를 저장한다.
- permutations를 이용하여 1~9까지 숫자로 3개를 골라 만들 수 있는 순열을 배열로 저장한다.
n번 만큼 반복하는 for문을 생성한다.
num, strike, ball을 입력받는다.
correct 배열을 생성한다.
- correct배열은 정답이 될 수 있는 수를 업데이트 시켜줄 배열이다.
될 수 있는 정답 answer와 질문으로 만들 수 있는 답의 경우의 수 guess를 비교하여 tmp_strike와 tmp_ball을 구한다.
tmp_strike와 tmp_ball이 strike와 ball과 같다면 correct 배열에 추가한다.
answer배열을 correct배열로 업데이트 하여 될 수 있는 정답을 줄인다.
correct배열의 개수를 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

import itertools

n = int(input())
answer = list(itertools.permutations(list(range(1,10)),3)) #정답 가능한 것

for i in range(n):
    num, strike, ball = map(int, input().split())
    guess = list(map(int,str(num)))

    correct = []
    for k_answer in answer:
        tmp_strike, tmp_ball = 0, 0

        for tmp in range(3):
            if guess[tmp] == k_answer[tmp]: #strike 개수 구하기
                tmp_strike += 1
            if guess[tmp] != k_answer[tmp] and guess[tmp] in k_answer: #ball개수 구하기
                tmp_ball += 1
        if tmp_strike == strike and tmp_ball == ball:
            correct.append(k_answer)
    answer = correct #정답 가능한것 업데이트

print(len(correct))

[백준] 로봇 (13567번)

Mon, 16 Sep 2024 21:17:51 GMT

난이도 : Silver 4 Link : https://www.acmicpc.net/problem/13567 Tag : 구현, 시뮬레이션 풀이일자 : 2024년 9월 17일

📌 문제 탐색하기

N : 명령어의 개수 M : 이동할 수 있는 면적 크기

가능한 시간복잡도

명령어가 들어올 때마다 이동하는 위치가 주어진 좌표에서 벗어나는지 안벗어나는지 확인하면 되므로 시간 복잡도는 명령어 갯수와 비례한다 따라서 O(N) 이다.

📌 문제 접근 방법

현재 위치는 (0,0)이고 이도할 수 있는 곳은 4방향이다. 따라서 방향을 설정하고 이동했을 때 주어진 좌표 이내이면 현재 좌표를 업데이트 해주고, 주어진 좌표보다 크다면 -1을 출력하게 접근하면 될것이라고 생각한다.

방향은 현재 90도 방향으로 돌리는 명령어를 사용하고 있으므로 실제로 이동하는 방향을 알아야 한다.

direction = 0 # 0 오른쪽 1 위 2 왼쪽 3 아래 이런식으로 각각의 숫자에 방향을 매핑해 놓을 생각이다.

또한 유효한 명령인지 아닌지를 구분지어야 하기 때문에 answer 변수를 이용해서 이동 불가능한 좌표일 경우 -1을 answer에 저장해 구분한다.

📌 코드 설계하기

n,m을 입력 받는다.
direction변수에 방향을 매핑한다 (초기값 0 : 오른쪽)
answer와 answer_x,answer_y를 초기화 한다
초기 좌표 x,y를 설정한다.

N번만큼 for문을 만든다.

command와 cnt를 입력받는다 (command는 명령어 유형, cnt는 좌표 또는 방향이다)

if command == 'MOVE':
  if direction == 0: #우측
      if x + cnt <= m:
          y, x = y, x + cnt
      else:
          answer = -1
          break
  elif direction == 1:
      if y + cnt <= m:
          y, x = y + cnt, x
      else:
          answer = -1
          break```

이런식으로 move에 대한 명령어를 처리한다.

elif command == 'TURN':
        if cnt == 0: #왼쪽 90 도
            if direction == 3 :
                direction = 0
            else:
                direction += 1
        elif cnt == 1: #오른쪽 90도
            if direction == 0 :
                direction = 3
            else:
                direction -= 1

이런식으로 Turn에 대한 명령어를 처리한다.

📌 시도 회차 수정 사항

📌 정답 코드

m,n = map(int,input().split()) # m : gird 크기 n: 명령 개수

direction = 0 # 0 오른쪽 1 위 2 왼쪽 3 아래
answer = 0
answer_x, answer_y = 0, 0
y,x = 0,0

for i in range(n):
    command, cnt = map(str, input().split())
    cnt = int(cnt)

    if command == 'MOVE':
        if direction == 0: #우측
            if x + cnt <= m:
                y, x = y, x + cnt
            else:
                answer = -1
                break
        elif direction == 1:
            if y + cnt <= m:
                y, x = y + cnt, x
            else:
                answer = -1
                break
        elif direction == 2:
            if x - cnt >= 0:
                y, x = y, x - cnt
            else:
                answer = -1
                break
        elif direction == 3:
            if y - cnt >= 0:
                y, x = y - cnt, x
            else:
                answer = -1
                break
    elif command == 'TURN':
        if cnt == 0: #왼쪽 90 도
            if direction == 3 :
                direction = 0
            else:
                direction += 1
        elif cnt == 1: #오른쪽 90도
            if direction == 0 :
                direction = 3
            else:
                direction -= 1
if answer != -1:
    answer_x, answer_y = x, y
    print(answer_x, answer_y)
else:
    print(answer)

[백준] 내려가기 (2096번)

Sun, 15 Sep 2024 20:51:55 GMT

난이도 : Gold5 Link : https://www.acmicpc.net/problem/2096 Tag : 다이나믹 프로그래밍, 슬라이딩 윈도우 풀이일자 : 2024년 9월 16일

📌 문제 탐색하기

N: 줄의 개수

조건 즉 0번째 인덱스일 경우 0번째와 1번째 인덱스를 다음번에 가질 수 있고 1번째 인덱스일 경우 0, 1, 2 2번째 인덱스일 경우 1, 2 를 다음번에 가질 수 있다.

가능한 시간복잡도

시간복잡도 상 N의 개수는 100,000이므로 문제는 없어보이나 메모리 제한이 4mb로 되어 있는것으로 보아 기존 DP로 누적 값들을 계속 저장하고 있으면 메모리가 초과 될 것으로 보인다.

따라서 이 문제는** DP 와 슬라이딩 윈도우**를 이용하여 접근해야한다.

📌 문제 접근 방법

** 슬라이딩 윈도우란 ?**

창문 틀을 밀어서 창문을 이동시키는 알고리즘이다. 즉 정해진 배열 크기 내에서 배열의 위치만 바꿔서 값들을 배열에 저장하는 DP 방법 중 하나이다.

예를들어 지금까지 DP 문제들은 DP라는 배열에 0번째 인덱스부터 N 번째 인덱스까지 저장하였지만 슬라이딩 윈도우를 이용하면 정해진 규칙 내에서 윈도우 틀을 만들고 틀의 배열의 크기만큼 누적 값을 더해서 이동하는 방식이다.

이런 방법을 적용시키기 위해

grid 배열에 얻을 수 있는 점수들을 저장할 것이고 줄이 바뀔 때 마다 grid배열을 초기화하여 메모리를 절약할 예정이다.

최대값을 저장할 dp_max 배열과 최솟값을 저장할 dp_min배열을 만들어 각 줄마다 얻을 수 있는 최대 점수와 최소 점수를 배열로 저장할 예정이다.

📌 코드 설계하기

n을 입력 받는다.
grid의 첫째줄을 입력받는다.
첫째줄의 값들을 dp_max와 dp_min에 초기화 시켜 첫째줄에서 얻을 수 있는 점수를 저장한다.
둘째줄부터 N번째 줄까지 반복문을 통해 dp_max와 dp_min을 초기화한다

dp_max = [grid[0] + max(dp_max[0],dp_max[1]), grid[1] + max(dp_max[0], dp_max[1], dp_max[2]), grid[2] + max(dp_max[1], dp_max[2])]
 dp_min = [grid[0] + min(dp_min[0],dp_min[1]), grid[1] + min(dp_min[0], dp_min[1], dp_min[2]), grid[2] + min(dp_min[1], dp_min[2])]

다음과 같이 초기화를 진행한다.
0번째 인덱스로 이동할 경우 그전 0번째, 1번째에서 오는 경우 중  max 또는 min
1번째 인덱스로 이동할 경우 그전 0번째, 1번째, 2번째 에서 오는 경우 중 max 또는 min
2번째 인덱스로 이동할 경우 그전 1번째, 2번째에서 오는 경우 중 max 또는 min

5. dp_max와 dp_min 에서 max와 min값을 출력한다.

### 📌 시도 회차 수정 사항

#### 틀렸습니다. (1%)

```python
n = int(input())

grid = list(map(int, input().split()))
dp_max = grid
dp_min = grid

for i in range(n-1):
    grid = list(map(int,input().split()))
    dp_max = [dp_max[0] + max(grid[0],grid[1]), dp_max[1] + max(grid[0], grid[1], grid[2]), dp_max[2] + max(grid[1], grid[2])]
    dp_min = [dp_min[0] + min(grid[0],grid[1]), dp_min[1] + min(grid[0], grid[1], grid[2]), dp_min[2] + min(grid[1], grid[2])]

print(max(dp_max), min(dp_min))

dp_max 와 dp_min을 초기화 시켜주는 과정에서 max 또는 min에서 gird를 선택하게 한다면 두번째 행부터 현재의 모든 값을 고려하지만 과거의 모든값까지 고려하지 않기 때문에 dp_max와 dp_min을 gird와 바꿔주었다.

📌 정답 코드

n = int(input())

grid = list(map(int, input().split()))
dp_max = grid
dp_min = grid

for i in range(n-1):
    grid = list(map(int,input().split()))
    dp_max = [grid[0] + max(dp_max[0],dp_max[1]), grid[1] + max(dp_max[0], dp_max[1], dp_max[2]), grid[2] + max(dp_max[1], dp_max[2])]
    dp_min = [grid[0] + min(dp_min[0],dp_min[1]), grid[1] + min(dp_min[0], dp_min[1], dp_min[2]), grid[2] + min(dp_min[1], dp_min[2])]

print(max(dp_max), min(dp_min))

[백준] RGB거리 (1149번)

Sat, 14 Sep 2024 23:36:16 GMT

난이도 : Silver1 Link : https://www.acmicpc.net/problem/1149 Tag : 다이나믹 프로그래밍 풀이일자 : 2024년 9월 15일

📌 문제 탐색하기

N: 집의 개수

조건: 집을 칠할 때 연속되게 칠하면 안된다. 따라서 R 칠했을 때 G,B를 G를 칠했을 때 R,B를 B를 칠했을 때 R,G를 칠할 수 있다.

가능한 시간복잡도

탐색할 자원의 크기는 N이므로 탐색할 수 있는 시간복잡도는 O(n)으로 생각 할 수 있다.

📌 문제 접근 방법

DP를 이용하여 RGB색을 칠할때 최솟값을 집의 좌표마다 저장한다면 해결할 수 있을것이다.

grid 배열에 각 집의 칠하는 비용을 저장하고 dp 배열에 색상별 비용을 저장할 것이다.

dp[i][0] R dp[i][1] G dp[i][2] B 이런식으로 각 색별로 값을 누적해 나가면 최소값을 구할 수 있다.

📌 코드 설계하기

n을 입력받는다.
grid를 입력받는다.
첫번째 dp 배열을 초기화 한다.

dp[0][0] = grid[0][0] dp[0][1] = grid[0][1] dp[0][2] = grid[0][2]
빨강, 초록, 파랑을 칠할때의 누적값을 저장한다. (이때 각 색을 칠할때 가격이 낮은것을 선택한다.)

for i in range(1,n): dp[i][0] = min(dp[i-1][1] + grid[i][0], dp[i-1][2] + grid[i][0]) #빨강을 칠할때 dp[i][1] = min(dp[i-1][0] + grid[i][1], dp[i-1][2] + grid[i][1]) #초록을 칠할때 dp[i][2] = min(dp[i-1][0] + grid[i][2], dp[i-1][1] + grid[i][2]) #파랑을 칠할때
최종적으로 칠한 색중 최솟값인 것을 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

n = int(input())
grid = [list(map(int,input().split())) for i in range(n)]

dp = [[0]* 3 for _ in range(n)]

# dp[i][0] R
# dp[i][1] G
# dp[i][2] B
dp[0][0] = grid[0][0]
dp[0][1] = grid[0][1]
dp[0][2] = grid[0][2]

for i in range(1,n):
    dp[i][0] = min(dp[i-1][1] + grid[i][0], dp[i-1][2] + grid[i][0]) #빨강을 칠할때
    dp[i][1] = min(dp[i-1][0] + grid[i][1], dp[i-1][2] + grid[i][1]) #초록을 칠할때
    dp[i][2] = min(dp[i-1][0] + grid[i][2], dp[i-1][1] + grid[i][2]) #파랑을 칠할때

print(min(dp[n-1][0], dp[n-1][1], dp[n-1][2]))

[백준] 자원 캐기 (14430번)

Sat, 14 Sep 2024 12:21:44 GMT

난이도 : Silver2 Link : https://www.acmicpc.net/problem/14430 Tag : 다이나믹 프로그래밍 풀이일자 : 2024년 9월 14일

📌 문제 탐색하기

N,M : 탐색할 자원의 크기 본 문제는 오른쪽으로 이동하거나, 아랫쪽으로 이동하는 로봇이 최대로 탐색할 수 있는 자원의 개수를 구하는 문제이다.

가능한 시간복잡도

탐색할 자원의 크기는 N x M 이므로 탐색할 수 있는 시간복잡도는 O(n*m)으로 생각 할 수 있다.

📌 문제 접근 방법

BFS 문제와 비슷하지만 지나는 경로마다 최대치를 계산하고 해당 좌표에 지금까지 얻은 자원의 갯수를 넣는다면 마지막 좌표에서 최대값이 들어있을것으므로 DP문제로 접근 할 수 있다.

따라서 x축으로 이동할때와 y축으로 이동할 때의 최대값을 해당 좌표에 넣어주면 될것이다.

📌 코드 설계하기

n,m을 입력 받는다.
grid를 생성한다 (n x m 크기의 자원 맵)
dp 배열을 생성한다 (grid를 탐색하면서 지금까지 모은 자원을 저장할 공간)
2차원배열을 탐색하며 dp좌표에 전 좌표에서 x축 y축 이동중 큰 값을 저장한다.
dp의 마지막 좌표를 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

n,m = map(int,input().split())
grid = [list(map(int,input().split())) for i in range(n)]
dp = [[0 for i in range(m+1)]for j in range(n+1)]


for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = grid[i-1][j-1] + max(dp[i-1][j], dp[i][j-1])

print(dp[-1][-1])

[백준] 1, 2, 3 더하기 (9095번)

Fri, 13 Sep 2024 11:35:53 GMT

난이도 : Silver3 Link : https://www.acmicpc.net/problem/9095 Tag : 다이나믹 프로그래밍 풀이일자 : 2024년 9월 13일

📌 문제 탐색하기

N : 1, 2, 3으로 만들 정수 본 문제는 1, 2, 3으로 만들 수 있는 경우의 수를 구하는 문제이다. 순열과 조합으로 이 문제를 접근 가능하지만 순열을 구하는 과정에서 시간복잡도가 증가될 가능성이 있으므로 DP로 접근 가능하다.

가능한 시간복잡도

본래 구했던 경우의 수에서 추가되는 경우의 수를 구한다는 것이 DP의 기본적인 개념으로 시간복잡도는 O(n)으로 생각 할 수 있다.

📌 문제 접근 방법

DP를 사용해서 접근할 예정이다. 예를 들어 1을 만들 수 있는 경우의 수는 1 이렇게 1개이다. 2를 만들 수 있는 경우의 수는 1+1 , 2 이렇게 2개이다. 3을 만들 수 있는 경우의 수는 1+1+1, 1+2, 2+1, 3 이렇게 4개 이다.

다음 문제에서 조건이 1, 2, 3을 이용해서 N을 만드는 것이다. 따라서

4를 만들 수 있는 경우의 수는 위에서 구한 1, 2, 3을 만들 수 있는 경우의 수에서 1과 3을 이용하는 경우의 수, 1과 2를 이용하는 경우의 수를 더한 값과 같다. 따라서 4를 만들 수 있는 경우의 수는 7가지가 된다.

한번더 5까지 진행한다면 4에서 1을 더하는 방법 (7가지) 3에서 2를 더하는 방법 (6가지) 2에서 3을 더하는 방법 4와 1를 사용하는것 7가지 + 3과 2를 사용하는것 6가지를 더해 13가지가 된다.

따라서 점화식을 만든다면 N = N-1 + N-2 + N-3 이라고 볼 수 있다.

📌 코드 설계하기

테스트 케이스 n을 입력받는다.
1~3으로 만들 수 잇는 경우의 수를 arr[1], arr[2], arr[3] 에 저장한다.
for문을 통해 4~11까지 dp를 진행한다.
들어오는 테스트 케이스의 결과값을 보여준다.

📌 시도 회차 수정 사항

📌 정답 코드

n = int(input())

arr = [0] * 11
arr[1] = 1 # 1을 만들 수 있는 경우의 수
arr[2] = 2 # 2를 만들 수 있는 경우의 수
arr[3] = 4 # 3을 만들 수 있는 경우의 수

for i in range(4, 11):
    arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3]

for i in range(0,n):
    a = int(input())
    print(arr[a])

[백준] 적록색약 (10026번)

Thu, 12 Sep 2024 13:04:53 GMT

난이도 : Gold5 Link : https://www.acmicpc.net/problem/10026 Tag : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 풀이일자 : 2024년 9월 12일

📌 문제 탐색하기

N : 그림의 크기 (N x N) 이 문제는 그리드 내에서 R,G,B의 집합의 갯수를 구하는 문제이다. 단 적록 색약인 경우도 생각해야 한다.

이 문제는 다른 지도 문제와 마찬가지로 BFS 섬의 개수 구하는 방법대로 접근하면 될 것으로 보인다.

가능한 시간복잡도

BFS함수를 2가지로 나눌 생각이다. 가능한 시간복잡도는 NxN을 완전 탐색하는 경우로 N의 크기는 1<=N<=100이므로 100 x 100 = 10000 이어서 충분히 탐색가능하다. 단) BFS를 두번 사용하면서 두번 완전 탐색 되는 경우만 방지하면 될것으로 보인다.

📌 문제 접근 방법

BFS를 이용하여 RGB의 집합의 개수를 파악할 예정이다.
BFS에 조건을 추가한 적록색약 전용 RGB의 집합의 개수를 파악할 예정이다.
- 적록색약 전용 BFS는 탐색하고 있는 RGB중 R과 G일 경우에 주변에 R과 G를 탐색하고 있는 RGB로 인식하게한다.
각 집합의 개수를 더해서 출력할 예정이다.

📌 코드 설계하기

Grid의 크기를 설정할 N을 입력받는다.
grid와 grid2를 입력 받는다
- grid를 입력받아 DeepCopy를 통해 grid2에 저장한다
- grid는 정상인 grid2는 색약 사람이 측정할 그리드 공간이다.
RGB 집합을 계산할 변수 6개를 생성한다

cnt_R, cnt_G, cnt_B = 0, 0, 0 cnt_R2, cnt_G2, cnt_B2 = 0, 0, 0 R,G,B는 정상인의 개수 R2,G2,B2는 색약인구의 개수

BFS 함수를 생성한다. (정상인)

def BFS(x,y, RGB): #정상인
 queue = deque([(x,y)])
 grid[y][x] = 'A'
 dx = [1,-1,0,0]
 dy = [0,0,1,-1]
 while queue:
     x,y = queue.popleft()
     for i in range(4):
         nx,ny = x+dx[i], y+dy[i]
         if 0<=nx


BFS 함수를 생성한다. (색약) - R과 G일 경우 주변의 G와 R을 개수를 세고 있는 RGB로 바꾼다.
def BFS_rg(x,y,RGB): #적녹 색맹
 queue = deque([(x,y)])
 grid2[y][x] = 'A'
 dx = [1,-1,0,0]
 dy = [0,0,1,-1]
 while queue:
     x,y = queue.popleft()
     for i in range(4):
         nx,ny = x+dx[i], y+dy[i]
         if (RGB == 'R' or RGB == 'G') and 0<=nx


grid와 grid2를 탐색하며 두 BFS를 사용한다.

answer에는 정상인의 집합 개수를 , answer2에는 색약인의 집합 개수를 저장해 출력한다.


📌 시도 회차 수정 사항
📌 정답 코드
from collections import deque
import copy

n = int(input())
grid = [list(input()) for _ in range(n)]
grid2 = copy.deepcopy(grid)
m = len(grid[0])
cnt_R, cnt_G, cnt_B = 0, 0, 0
cnt_R2, cnt_G2, cnt_B2 = 0, 0, 0
answer = 0

def BFS(x,y, RGB): #정상인
    queue = deque([(x,y)])
    grid[y][x] = 'A'
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]
            if 0<=nx



[백준] 버섯 농장 (27737번)
Wed, 11 Sep 2024 14:31:09 GMT
난이도 : Silver1
Link : https://www.acmicpc.net/problem/27737
Tag : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
풀이일자 : 2024년 9월 11일
📌 문제 탐색하기
정사각형으로 이뤄진 나무판에서 M개의 버섯 포자를 가지고 농사가 가능한지 불가능한지, 사용 가능한 버섯 포자의 개수는 몇개인지 구하는 문제이다.
N : 나무판의 크기
M : 포자의 개수
K : 포자가 자라게 하는 버섯의 개수
1 : 버섯이 자랄 수 없는 칸
0 : 버섯이 자랄 수 있는 칸
가능한 시간복잡도
완전 탐색의 문제로 N의 크기별로 문제의 시간복잡도는 달라지게 된다.
N의 크기는 100까지 이므로 최대 반복할 수 있는 시간복잡도는 100 x 100 = 10000이므로 완전탐색인 BFS로 접근이 가능하다.
📌 문제 접근 방법

전체 나무판에서 for문을 이용하여 육지를 찾는다.
나무판에서 0을 찾았다면 BFS를 이용하여 주변의 0을 탐색한다.
탐색한 곳의 개수를 찾아 반환한다. mursh
한 그룹의 0의 개수를 다 셌다면 needed_mursh에 (mursh + k -1) // k 로 필요한 포자의 개수를 구한다.
필요한 포자의 개수가 m 보다 작다면 농사가 가능하고, m보다 크다면 농사가 불가능하다고 판단하면 될것이다.

📌 코드 설계하기

n,m,k 를 입력받고, grid에 나무판을 입력받는다.

answer변수을 0으로 초기화 하고 needed_mursh 변수를 만든다 (필요한 포자 개수)

4방향으로 이동할 수 있는 방향을 설정한다.

#4방향
dx = [1,-1 ,0 ,0]
dy = [0, 0, 1, -1]


BFS 함수를 작성한다.

queue에 처음 좌표를 넣어준다.
처음 좌표의 0을 1로 바꿔 재탐색을 방지한다.
queue에 원소가 존재할때 동안 x,y를 업데이트 해준다.
4방향으로 이동했을때 이동할 수 있는 지 파악하고 0일 경우 1로 변경한다.
0을 찾을때마다 mursh 변수에 1씩 추가한다.


나무판을 반복하여 0인 나무판을 찾아 BFS 함수를 호출한다.

mursh에 BFS로 탐색하여 찾은 0의 개수를 넣어주고 needed_mursh를 구해 answer를 업데이트 한다.

answer의 값이 m보다 작거나 같고, needed_mursh > 0 사용한 포자가 1개 이상이라면 POSSIBLE을 출력하고 answer - m을 출력한다.

그렇지 않다면 IMPOSSIBLE을 출력한다.


📌 시도 회차 수정 사항
틀렸습니다. (최소 1개 이상 포자를 사용할때를 제외 시킴)
from collections import deque

n,m,k = map(int,input().split())
grid = [list(map(int,input().split())) for _ in range(n)]
answer = 0
def BFS(x, y):
    queue = deque([(x,y)])
    grid[x][y] = 1
    mursh = 1
    dx = [1,-1 ,0 ,0]
    dy = [0, 0, 1, -1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx

📌 정답 코드
from collections import deque

n,m,k = map(int,input().split())
grid = [list(map(int,input().split())) for _ in range(n)]
answer = 0
needed_mursh = 0
def BFS(x, y):
    queue = deque([(x,y)])
    grid[x][y] = 1
    mursh = 1
    dx = [1,-1 ,0 ,0]
    dy = [0, 0, 1, -1]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if 0<=nx 0:
    print("POSSIBLE")
    print(m-answer)
else:
    print("IMPOSSIBLE")





[백준] 섬의 개수 (4963번)
Tue, 10 Sep 2024 00:49:50 GMT
난이도 : Silver2
Link : https://www.acmicpc.net/problem/4963
Tag : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
풀이일자 : 2024년 9월 10일
📌 문제 탐색하기
정사각형으로 이루어져 있는 섬과 바다 지도가 주어졌을 때 섬의 개수를 세는 문제이다.

섬의 조건
상하좌우대각선 방향으로 이어져 있다면 하나의 섬으로 간주한다.

따라서 이 문제는 BFS를 이용하여 육지가 발견되었을 경우 이동할 수 있는 8가지 방향에 대해서 탐색한 뒤 탐색한 곳의 육지를 바다로 바꿔준다면 최소한의 탐색으로 섬의 개수를 구할 수 있을것이다.
가능한 시간복잡도
모든 곳이 육지일 확률이 있기 때문에 가능한 시간복잡도의 가장 최악인 경우는 지도의 넓이와 같다. W, H의 범위는 50보다 작거나 같은 양의 정수 이므로 시간복잡도상 BFS로 접근했을 때 문제는 없어보인다.
📌 문제 접근 방법

전체 지도에서 for문을 이용하여 육지를 찾는다.
육지를 찾았다면 육지로부터 이어져있는 육지를 찾기위해 BFS를 이용하여 8방향으로 탐색한다.
탐색한 곳은 바다로 바꿔 재탐색을 방지한다.
BFS를 호출 할때 육지 카운트를 하나 올려 육지의 개수를 센다.

📌 코드 설계하기

8방향으로 이동할 수 있는 방향을 설정한다.

#8방향
dx = [1,1,1,0,0,-1,-1,-1]
dy = [1,0,-1,1,-1,1,0,-1]


BFS 함수를 작성한다.

queue에 처음 좌표를 넣어준다.
처음 좌표의 육지를 바다로 바꿔 재탐색을 방지한다.
queue에 원소가 존재할때 동안 x,y를 업데이트 해준다.
8방향으로 이동했을때 이동할 수 있는 지 파악하고 육지일 경우 같은 육지로 설정하기 위해 바다로 바꾼다.


W,H를 입력받는다.

W,H가 0, 0 이 들어올때까지 테스트케이스를 반복한다.

W,H를 통해 지도를 grid에 저장한다.

grid에서 육지를 찾았을 경우 BFS 함수를 실행하고 육지 카운트를 올린다.


📌 시도 회차 수정 사항
📌 정답 코드
from collections import deque
import sys
#8방향
dx = [1,1,1,0,0,-1,-1,-1]
dy = [1,0,-1,1,-1,1,0,-1]

def BFS(x, y):
    queue = deque()
    queue.append([x,y])
    grid[y][x] = 0
    while queue:
        x,y = queue.popleft()
        for i in range(8):
            if (x + dx[i]) >= 0 and (x + dx[i]) < w and (y + dy[i]) >= 0 and (y + dy[i]) < h:
                if grid[y+dy[i]][x+dx[i]] == 1:
                    queue.append([x+dx[i],y+dy[i]])
                    grid[y+dy[i]][x+dx[i]] = 0

while True: # 0 0이 들어올때까지 무한 반복
    w,h = map(int,input().split())
    if w == 0 and h == 0:
        break
    grid = list()
    answer = 0
    for i in range(h):
        grid.append(list(map(int,sys.stdin.readline().split()))) #지도 만들기

    for i in range(h): #y
        for j in range(w): # x
            if grid[i][j] == 1: # [y][x]
                answer += 1
                BFS(j,i)
    print(answer) #섬의 개수 출력





[백준] 폴짝폴짝 (1326번)
Mon, 09 Sep 2024 08:29:40 GMT
난이도 : Silver2
Link : https://www.acmicpc.net/problem/1326
Tag : 그래프 이론, 그래프 탐색, 너비 우선 탐색
풀이일자 : 2024년 9월 9일
📌 문제 탐색하기
개구리는 a번째 징검다리에서 b번째 징검다리까지 최소 몇번 점프를 해야하는지 구하는 문제이다.
조건)
개구리는 징검다리에 쓰여있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다.
가능한 시간복잡도
징검다리의 개수는 N(1<= N <= 10,000)이므로 최악인 시간복잡도인 항상 한칸만 점프할 때를 가정해도 10,000번만 반복하면 되기 때문에 문제 없어 보인다.
📌 문제 접근 방법
개구리의 위치의 숫자를 파악하고 숫자의 배수중 징검다리로 부터 가장 멀리 떨어진 곳으로 도달하는 것이 가장 중요하다.
BFS를 이용하여 방문횟수를 파악하여 B번째 징검다리에 도달했을 때 점프 횟수를 반환하면 될것이라고 판단한다.
문제에서 오른쪽으로만 점프하는지, 왼쪽으로 점프하는지 명시되어 있지 않기 때문에 둘다의 경우를 확인해야 한다.
📌 코드 설계하기

N을 입력받는다.
bridge와 a,b를 입력받는다. bridge는 인덱스의 헷갈림을 줄이기 위해 0번째 인덱스를 추가한다.
BFS 함수를 작성한다.
queue에 시작 위치를 설정한다.
visted 리스트를 -1로 초기화 시킨다.
visited[start] 를 0으로 초기화 시켜 첫번째 위치를 방문했다는 것을 인지 시킨다.
queue에 원소가 존재할 경우 while문을 반복한다.
오른쪽으로 이동할 경우, 왼쪽으로 이동할 경우로 나눠 for문을 작성한다

bridge[now]만큼 간격을 주어 점프 할 수 있는 곳을 확인한다.
if visited[i] == -1 이라면 방문한적이 없는 징검다리이므로 , 해당 징검다리를 몇번 점프해야 방문 할 수 있는지 visited[i] 에 추가한다.
만일 i 가 끝에 가고 싶은 징검다리라면 해당 점프 횟수를 반환한다.
전체를 탐색해도 가고싶은 징검다리가 나오지 않는다면 -1을 반환한다.






📌 시도 회차 수정 사항

틀렸습니다. (왼쪽으로부터 오른쪽으로만 징검다리를 이동 가능한 줄 알았다.)
(왼쪽방향과 오른쪽 방향을 확인하기 위해 BFS를 활용하여 문제를 해결하였다.)from collections import deque



N = int(input())
bridge = list(map(int, input().split()))
bridge.insert(0,0)
a,b = map(int, input().split())
def BFS(start, end):
    queue = deque([start]) #시작 위치 설정
    visited = [-1] * (N+1) # 방문 노드 표시 (방문하지 않은곳 -1)
    visited[start] = 0 #방문시 0
    while queue:
        now = queue.popleft() #현재 노드 탐색
        # 오른쪽 방향 탐색
        for i in range(now, N + 1 , bridge[now]):
            if visited[i] == -1 :
                queue.append(i)
                visited[i] = visited[now] + 1 #i까지 도달하는데 필요한 점프 횟수 추가
                if i == end:
                    return visited[i]
        # 왼쪽 방향 탐색
        for i in range(now, 0, -bridge[now]):
            if visited[i] == -1:
                queue.append(i)
                visited[i] = visited[now]
                if i == end:
                    return visited[i]
    return -1
print(BFS(a, b))

### 📌 정답 코드

``` python
from collections import deque

N = int(input())
bridge = list(map(int, input().split()))
bridge.insert(0,0)
a,b = map(int, input().split())

def BFS(start, end):
    queue = deque([start]) #시작 위치 설정
    visited = [-1] * (N+1) # 방문 노드 표시 (방문하지 않은곳 -1)
    visited[start] = 0
    while queue:
        now = queue.popleft() #현재 노드 탐색
        # 오른쪽 방향 탐색
        for i in range(now, N + 1 , bridge[now]):
            if visited[i] == -1 :
                queue.append(i)
                visited[i] = visited[now] + 1 #i까지 도달하는데 필요한 점프 횟수 추가
                if i == end:
                    return visited[i]
        # 왼쪽 방향 탐색
        for i in range(now, 0, -bridge[now]):
            if visited[i] == -1:
                queue.append(i)
                visited[i] = visited[now] + 1
                if i == end:
                    return visited[i]
    return -1

print(BFS(a, b))