문제 확인 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트에서 문제를 확인해주세요. 나의 풀이 전에 풀었던 백준 2667번 단지번호 붙이기 문제와 동일한 문제다. 풀고보니 이번에 풀 때는 불필요한 global 처리도 없애고 방문 처리도 graph 하나로 가지고 진행했다. 전 풀이는 아래 링크를 통해 확인할 수 있다. 다시 보니 부끄럽다. ㅋ import sys from collections import deque def bfs(queue): num = 0 while queue: x, y = queue.popleft() num += 1 for i in range(4): x_new = x + dx[i] y_new = y + dy[i] # 방문 아직 하지 않은 점이 ..

문제 확인 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트에서 문제를 확인해주세요. 나의 풀이 단순한 문제라서 풀이에 대해 말할 것은 없다. 하지만 답이 이미 [1,2,3,4,5,6,7,8] 또는 [8,7,6,5,4,3,2,1]로 주어진 상황에서 굳이 원소 별로 확인할 필요가 없었던 거 같은데 그냥 관성적으로 접근했던 거 같다. 쉬운 문제여도 더 효율적으로 풀 수 있게 좀 더 생각하면서 풀자. import sys speed = list(map(int, input().split())) asc = 0 dsc = 0 for i in range(8): if speed[i] == i + 1: continue else: break else: asc = 1 for i in ..

문제 확인 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트를 방문하여 문제를 확인해주세요. 나의 풀이 시간 초과가 발생하여 결국 풀이를 참고해서 풀었다. 처음엔 바이러스가 곱해지는 비율(거듭 제곱)을 빠르게 구하기 위해서 O(logN)의 시간 복잡도를 가지는 분할 정복을 사용했다. 하지만 N의 범위가 1,000,000이라서 분할 정복 여부는 시간 초과가 관계가 없었다. 결국 큰 수 끼리 곱해지는 과정에서 시간 초과가 발생하게 되는데 큰 수를 어떻게 처리해야할 지 몰랐다. 처음 분할 정복을 시도한 풀이는 다음과 같다. import sys def get_pow(a, b): if b == 0: return 1 # b가 짝수일 경우 elif b % 2 == 0: ret..

문제 확인 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트를 방문하여 문제를 확인해주세요. 나의 풀이 정렬엔 O(N)인 Count 정렬 최대 무게를 얻기 위한 idx를 찾기 위해선 O(logN)인 이진 탐색 사용 idx를 찾는 경우엔 범위가 10,000이었기 때문에 단순 탐색으로도 시간 초과가 발생하지는 않았을 것이다. 귀금속의 종류(N)이 1,000,000이므로 $O(Nlog(N))$인 파이썬의 기본 정렬 대신 $O(N)$인 Counting 정렬을 사용했다. 이때, N(귀금속 종류의 수)가 P(귀금속 무게당 가치)보다 크기 때문에 P가 같은 경우가 발생할 수 있다. P가 같은 경우엔 동일 P를 가지는 귀금속 과 구분할 수 없기 때문에 무게를 추가해줬다. 이후 ..

문제 확인 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트를 방문하여 문제를 확인해주세요. 나의 풀이 구간 마다 조건을 나눠서 푸는 방법도 생각해봤지만 각 위치에서의 속도 정보를 저장해서 비교했다. 이 방법이 더 편하고 실수할 일도 없을 거 같아서 선택했다. import sys n, m = map(int, input().split()) # 제한 구간 정보 section_limit = [list(map(int, input().split())) for _ in range(n)] # 테스트 구간 정보 section_test = [list(map(int, input().split())) for _ in range(m)] # 제한 구간 정보 입력 speed_limit =..

문제 확인 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트를 방문하여 문제를 확인해주세요. 나의 풀이 완전 탐색으로 풀었다. 코드를 다시 보니 굳이 리스트에 담아뒀다가 확인할 필요 없이 for문에서 바로 확인하는 것이 더 나았을 것 같다. 조작법 앞뒤로 다른 버튼 조작이 있어도 비밀 메뉴로 인정된다. 처음에 위 문항을 조작법 사이에 어떤 버튼이 있어도 상관 없다는 것으로 이해하고 풀었어서 시간이 좀 걸렸다. import sys # 레시피, 유저 입력, 버튼 수 secret_num, seq_num, button_num = map(int, input().split()) # 레시피 / 유저 정보 입력 secret = list(map(int, input().split(..

문제 확인 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트를 방문하여 문제를 확인해주세요. 나의 풀이 전광판에 해당되는 전구를 미리 dict로 지정해서 풀었다. 이때, A -> B로 바뀔 때, A에만 있는 전구는 꺼야 하고 B에만 있는 전구는 켜면 된다. import sys # 맨 위 idx를 0, 왼쪽을 1, 오른쪽을 2 아래를 3 ... 방식으로 숫자를 만들 경우 필요한 전구 미리 정의 num2lamp = { "0" : set([0, 1, 2, 4, 5, 6]), "1" : set([2, 5]), "2" : set([0, 2, 3, 4, 6]), "3" : set([0, 2, 3, 5, 6]), "4" : set([1, 2, 3, 5]), "5" : set(..

문제 확인 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 사이트를 방문하여 문제를 확인해주세요. 나의 풀이 입출력이 까다로워서 조건에 맞게 수정하느라 시간이 꽤 걸렸다. 시간 정보 - idx 정보를 변환해가면서 풀었는데 [9, 10], [10, 11] 처럼 그냥 시간 형태로 입력에 넣었으면 더 간단하게 풀 수 있었을 것 같다. import sys # 시간 - idx 변환 hour = dict(zip(range(9, 19), range(10))) idx2hour = dict(zip(range(10), range(9, 19))) # 방/미팅 수 room_num, meeting_num = map(int, input().split()) # 방 이름 입력 room_name =..

1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 시간 제한 2초 메모리 제한 256MB 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 ..

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 시간 제한 2초 메모리 제한 192MB 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는..

16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 시간 제한 1초 메모리 제한 512MB 문제 뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다. 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까? 게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 1..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 시간 제한 1초 메모리 제한 256MB 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽,..