자료구조
-
[백준] 2615 오목 with PythonPS 2021. 12. 12. 17:42
📌 BOJ 2615 오목 💡 조건 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있다. board의 크기는 19 * 19 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시 가로, 세로 또는 대각선 방향 모두 포함해서 같은 색의 바둑돌이 5개 놓여져 있다면 승리한다. 5개 초과 또는 미만의 개수는 승리할 수 없다 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성. 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력 은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알의 가로줄, 세로줄 번호를 출력한다. 세로로 놓인 경우,..
-
[백준] 1515 수 이어 쓰기 with PythonPS 2021. 12. 12. 17:07
📌 BOJ 1515 수 이어 쓰기 💡 조건 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 다솜이가 숫자의 일부를 지웠고, 지워지기 전의 숫자를 다시 쓰려고 하니 N이 기억나지 않는다. 남은 수를 이어 붙인 수가 주어질 경우, N의 최솟값을 구하는 문제. 일부 숫자를 지우고 남은 수를 이어붙인 수가 주어지며, 이 수는 최대 3000자리. 구현, 문자열, 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin data = stdin.readline().rstrip() s, i = '', 1 def check(s): t = list(s) k = list(data) while 1: if len(t) < len(data): return ' ..
-
[백준] 1411 비슷한 단어 with PythonPS 2021. 12. 12. 03:25
📌 BOJ 1411 비슷한 단어 💡 조건 문자열 A를 숌스럽게 바꾸어 B로 만들었다면, 그 단어는 비슷한 단어라고한다. 숌스럽게 바꾼다는 것은 단어 A에 등장하는 모든 알파벳을 다른 알파벳으로 바꾼다. 단어가 여러 개 주어졌을 때, 몇 개의 쌍이 비슷한지 구하는 문제. 단어의 길이는 최대 50 N은 100보다 작거나 같은 자연수이다. 모든 단어의 길이는 같고, 중복되지 않는다. 브루트포스 알고리즘 유형의 문제 🖥 소스 코드 from sys import stdin from itertools import combinations words = [] res = set() tc = int(stdin.readline()) if tc == 1: print(res) else: for _ in range(tc): wor..
-
[Programmers] 블록 이동하기 with PythonPS 2021. 12. 12. 02:28
📌 Programmers - [블록 이동하기] 💡 조건 board의 한 변의 길이는 5 이상 100 이하. board의 원소는 0(이동가능 블록) 또는 1(이동불가 벽). 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어진다. 로봇은 회전할 수 있다. BFS, 시뮬레이션의 문제 (N, N) 좌표까지 도달하는 최소시간을 구하는 문제 🖥 소스 코드 from collections import deque def get_next_pos(pos, board): next_pos = [] pos = list(pos) pos1_x, pos1_y, pos2_x, pos2_y = pos[0][0], pos[0][1], pos[1][0], pos[1][1] dx = [-1, 1, 0, 0] dy = ..
-
-
[백준] 11497 통나무 건너뛰기 with PythonPS 2021. 12. 6. 21:07
📌 BOJ 11497 통나무 건너뛰기 💡 조건 첫 줄에 통나무의 개수를 나타내는 정수 (5 ≤ N ≤ 10,000) 둘째 줄에 각 통나무의 높이를 나타내는 정수 (1 ≤ Li ≤ 100,000) 통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 그리디 알고리즘유형의 문제 🖥 소스 코드 from sys import stdin for _ in range(int(stdin.readline())): n = int(stdin.readline()) arr = list(map(int, stdin.readline().split())) arr.sort() res = 0 for i in range(2, n): res = max(re..
-
-
[백준] 2841 외계인의 기타 연주 with PythonPS 2021. 12. 1. 21:51
📌 BOJ 2841 외계인의 기타 연주 💡 조건 멜로디는 음의 연속이고, 각 음은 줄에서 해당하는 프렛을 누르고 줄을 튕기면 연주할 수 있다. 어떤 줄의 프렛을 여러 개 누르고 있다면, 가장 높은 프렛의 음이 발생. 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 2번 프렛의 음을 연주하려고 한다면, 5번과 7번을 누르던 손가락을 뗀 다음에 2번 프렛을 누르고 연주해야 한다. 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성. Stack, 자료구조 유형의 문제 🖥 소스 코드 from sys import stdin import heapq n, p = map(int, stdin.readline().split()) ..
-
-
[Programmers] 자물쇠와 열쇠 with PythonPS 2021. 11. 29. 20:54
📌 Programmers - [자물쇠와 열쇠] 💡 조건 key는 M x M(3 ≤ M ≤ 20, M은 자연수) 크기 2차원 배열 lock은 N x N(3 ≤ N ≤ 20, N은 자연수) 크기 2차원 배열 M은 항상 N 이하, key와 lock의 원소는 0 또는 1 자물쇠는 홈이 있으며, 열쇠도 돌기가 있다. 열쇠는 회전이 가능하다. 자물쇠 부분이 회전할 수 있는 열쇠와 겹쳐져서 모두 1이 된다면 열 수 있으니 True, 열 수 없다면 False를 반환 구현 & 시뮬레이션 유형의 문제 🖥 소스 코드 def turn_key(l, key): new_key = [item[:] for item in key] for i in range(l): for j in range(l): new_key[i][j] = key[l..