본문 바로가기

백준14

백준18156🐨Black and White https://www.acmicpc.net/problem/18156 시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초512 MB1431139483186%문제n x n 격자가 주어지며, 각 칸은 흑색 또는 백색으로 칠해져 있습니다. 다음 조건을 모두 만족하면 격자는 ‘올바른’ 것으로 간주됩니다:모든 행에서 흑색 칸의 수와 백색 칸의 수가 같아야 합니다.모든 열에서 흑색 칸의 수와 백색 칸의 수가 같아야 합니다.어떤 행이나 열에서도 같은 색상의 칸이 3개 이상 연속으로 있어서는 안 됩니다.주어진 격자가 올바른지 판단하세요.입력첫 줄에는 정수 n이 주어집니다 (2 ≤ n ≤ 24; n은 짝수).그 다음 n개의 줄에는 각각 길이 n의 문자열이 주어지며, 'B’와 'W’로만 구성되어 있습니다. 이는 격자 칸의 .. 2024. 10. 9.
백준18005🐨Even or Odd? https://www.acmicpc.net/problem/18005문제의 주요 조건을 살펴보자.picked n consecutive positive integers between 1 and 1018 guess if their sum is even or oddIf the sum must be even, write 2.If the sum must be odd, write 1.If the sum could be even or could be odd, write 0.The single line of input contains a single integer n (1 ≤ n ≤ 109). 일련의 $n$개 수의 합이 홀수가 되거나 짝수가 되는 것은홀수로 시작하는지 짝수로 시작하는지가 영향을 줄 것이다.홀수로 시작하는.. 2024. 8. 6.
파이썬🐨더욱 더 로우레벨한 입출력 import osarr = list(map(int, os.read(0, os.fstat(0).st_size).split()))is_hacker = any((((i // 2) + 1) * 100)  제시된 코드는 os.read와 os.fstat를 사용하여 표준 입력으로부터 데이터를 읽고 처리하는 방식으로 작성된 코드이다. 이 코드의 동작 방식과 sys.stdin, open(0), input()과의 차이점을 자세히 설명하겠다.코드 분석import os# 표준 입력으로부터 데이터를 읽어온다arr = list(map(int, os.read(0, os.fstat(0).st_size).split()))# 조건에 따라 'hacker'인지 아닌지 판별is_hacker = any((((i // 2) + 1) * 100).. 2024. 7. 31.
백준3015🐨오아시스 재결합.py 백준 3015번 “오아시스 재결합” 문제는 스택을 이용하여 각 사람이 볼 수 있는 다른 사람의 쌍을 구하는 문제이다. 아래에 주어진 코드를 바탕으로 문제 풀이를 설명한다:n, *nums = map(int,open(0).read().split())stack = []result = 0for i in range(n): count = 1 while stack and stack[-1][0] 코드 설명초기화 및 입력 처리:n과 nums에 입력 데이터를 받아오고, stack과 result를 초기화한다.스택을 이용한 탐색:각 사람의 키를 nums에서 하나씩 순서대로 처리한다. 현재 사람의 키 nums[i]를 기준으로, 스택에 쌓인 이전 사람들 중 nums[i]보다 작거나 같은 키를 가진 사람들을 제거한다. .. 2024. 7. 30.
백준17298🐨오큰수.py .c + 백준17299🐨오등큰수.py https://redcubes.tistory.com/124 🐨BOJ#6549 히스토그램에서 가장 큰 직사각형] 모노톤 스택(#1725히스토그램)히스토그램에서 가장 큰 직사각형 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 256 MB 54258 14782 9717 26.945% 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이redcubes.tistory.com 오큰수 (NGE: Next Greater Element)오큰수: 현재 숫자 오른쪽에 위치하면서 현재 숫자보다 큰 수 중 가장 왼쪽에 있는 수.예시: 숫자 배열이 [9, 5, 4, 8]일 때 각 숫자의 오큰수는 다음과 같다:9: 오른쪽에 더 큰 수가 없으므로 -15: 오른쪽에 있는 8이 오큰수4: 오른쪽에 있는.. 2024. 7. 28.
🐨BOJ#1697 숨바꼭질]🙄BFS(feat. collections) 문제 보기 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 아이디어 딱 봐도 dp로 풀 수 있을 것 같지만... 머리가 아파서(=어려워서) 수빈이가 도착할 수 있는 위치가 분기로 갈라지는 트리를 만들어서 풀기로 했다. 가장 적은 횟수(빠른 시간)에 동생을 찾아야 하기 때문에, 트리의 깊이가 가장 얕은 게 정답이다. 그래서 dfs로 탐색한 뒤 깊이를 비교하는 것 보다 bfs를 사용해야 한다고 생각했다. 그리고 분기.. 2024. 3. 29.
# 2559번 수열 ''' 10개의 원소가 있고 3 크기의 윈도우를 슬라이딩 시킨다고 하면 0 1 2 3 4 5 6 7 8 9 |___| | | | | | | | |___| | | | | | | |___| | | | | | |___| | | | | |___| | | | |___| | | |___| | |___| 반복 횟수는 10 - 3 + 1 = 8회다. 최초 윈도우를 설정하는1회를 제외한 7회동안 제일 앞과 제일 뒤의 값을 빼고 더하면 된다. n개의 원소와 k크기의 윈도우라면 n-k회가 된다. ''' import sys def sliding_window_sum(arr, n, k): window = sum(arr[0:k]) result = window for i in range(n-k): window = window - a.. 2024. 3. 9.
10844번 쉬운 계단 수 동적 계획법(Dynamic Programming)을 사용해서 문제를 해결해 보자. 길이가 n이고 마지막 숫자가 0에서 9까지 각각인 계단 수의 개수를 dp[n][last]라고 할 때, (dp[1][0] = 0) (길이가 1이고 마지막 숫자가 0인 계단 수는 없다.) (dp[1][i] = 1) (1 2024. 3. 3.
# 9251번 LCS def lcs(A, B): lenA, lenB = len(A), len(B) DP = [[0] * (lenB+1) for _ in range(lenA+1)] for i in range(1, lenA+1): for j in range(1, lenB+1): if A[i-1] == B[j-1]: DP[i][j] = DP[i-1][j-1] + 1 else: DP[i][j] = max(DP[i-1][j], DP[i][j-1]) return DP[lenA][lenB] def main(): A = input() B = input() print(lcs(A, B)) if __name__ == "__main__": main() lcs(A, B) 함수는 두 문자열 A와 B를 입력으로 받습니다. 변수 lenA와 lenB는 각.. 2024. 2. 19.
백트래킹(Backtracking, 퇴각검색) # 14889번 스타트와 링크, # 9663번 N-Queen [파이썬] 목차 그래프와 트리 탐색 알고리즘 백트래킹의 소개 개념 방법 성능개선 개발 활용 사례(예산 활용법 찾기) 알고리즘 설명 코드보기 백준 문제 #14889 스타트와 링크 # 9663번 N-Queen α–β A* B* 퇴각검색 빔 벨먼-포드 최상 우선 양방향 Borůvka 분기 한정법 BFS 영국박물관 D* DFS 데이크스트라 에드먼즈 플로이드-워셜 Fringe search 언덕등반기법 IDA* 반복적 깊이심화 존슨 Jump point 크러스컬 Lexicographic BFS LPA* 프림 SMA* 출처: https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89 퇴각검색 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 퇴각검색.. 2024. 2. 14.
14889번 스타트와 링크 - 백 트래킹 14889번 스타트와 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 더보기 문제의 이해 어떤 사람과 팀이 되느냐에 따라 능력치가 달라질 때 두 팀의 능력치 차이가 가장 적을 때 얼마인지 알아내는 문제다. 직관적으로 떠오르는 방법은 조합을 구하고 팀 1,2를 조합해서 최소값을 찾으면 되는 문제인데 백트래킹이 붙어 있어서 아마 안 되겠지 생각하며 해 보았는데 성공. 조합을 생각해 보면 한 팀만 구성하면 나머지 팀이 완성되기 때문에, 그리고 인원이 짝수인 것이 보장되기 때문에 $$n C (n/2) = \frac{n!}{(n/2)!.. 2024. 2. 8.
백준 # 31287번 장난감 강아지 - 파이썬 4 2 URLD YES 3 2 URD NO 시뮬레이션으로는 풀리지 않고 시간 초과가 난다. 생긴 도형의 최종점과 원점의 관계를 통해 그림을 새로 그리지 않고 원점을 최종점(x,y)에 대해 -x, -y 만큼 이동한다고 생각하고 문제를 풀었지만 시간 초과를 도무지 해결할 수가 없었다. 먼저 1회 순회하면서 0,0을 지나는지, 어느 점을 지나는지 기록하고, 최종점을 구한 뒤에 2회 반복부터는 좌표에 대한 함수로 구하려고 했는데.... 안되었다. 망한 코드를 보자. 이거보다 개선된 k회 포지션을 기준으로 하는 코드가 있는데 의미없다. def can_return_to_origin(n, k, text): x, y = 0, 0 positions = set() # 거쳐간 좌표들을 저장할 집합 # 명령어 순회 for t.. 2024. 2. 5.

티스토리툴바