본문 바로가기

Algorithm705

[자료구조/스택] 백준 1406 에디터 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 2. 문제 풀이 L: 커서를 왼쪽으로 한 칸 옮김 D: 커서를 오른쪽으로 한 칸 옮김 B: 커서 왼쪽에 있는 문자 삭제 P $: $ 문자를 커서 왼쪽에 추가 에디터를 구현하는 문제입니다. 단순히 리스트 연산으로 구현가능하지만, 시간제한이 0.3초로 굉장히 짧습니다. 따라서 (연결)리스트의 삭제, 삽입 연산은 사용하면 안됩니다. 그대신, 커서를 기점으로 두 개의 스택으로 나누어서 담으면 해결할 수 있습니다. 2022... 2022. 6. 7.
[구현/수학] 백준 2903 중앙 이동 알고리즘 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2903번: 중앙 이동 알고리즘 상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다. www.acmicpc.net 2. 문제 풀이 규칙에 따라 점의 개수를 구해야 합니다. 1. 정사각형의 각 변의 중앙에 점을 하나 추가 2. 정사각형의 중심에 점을 하나 추가 문제에 흰점과 검은점이 섞여 있어서 오히려 더 어렵게 보이기도 합니다. 색깔 구분없이 보면, 그저 빽빽하게 점이 채워진 정사각형이 보입니다. 즉, 변의 길이만 알면 점의 개수를 구할 수 있습니다. 처음에는 변의 길이가 2였고, 그 다음은 3, 5로 증가합니다. 다.. 2022. 6. 6.
[탐색/BFS] 백준 2644 촌수계산 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 2. 문제 풀이 촌수를 계산하는 문제입니다. 2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자 BFS는 가까운 주변부터 탐색하는 알고리즘입니다. 큐를 이용한 BFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. BFS(Breath First S.. 2022. 6. 5.
[구현/수학] 백준 2921 도미노 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2921번: 도미노 도미노는 여러 종류의 타일 게임에서 사용하는 조각이다. 도미노 조각은 두 칸으로 이루어져 있다. 각 칸에는 점이 찍혀있는데, 점이 안 찍혀져 있을 수도 있다. 점의 개수는 세트의 크기에 의 www.acmicpc.net 2. 문제 풀이 크기가 N인 도미노 세트에 점이 몇 개 있는지 구하는 문제입니다. ○ ○ ○○ ○ ○ ○○ ○○ ○○ 크기가 2인 도미노 세트는 12개입니다. 총 6가지 도미노가 나오며, (윗 칸, 아랫 칸)으로 표시하면 다음과 같습니다. (0, 0), (0, 1), (1, 1), (0, 2), (1, 2), (2, 2) 즉, 0, 1, 2 중에서 2개를 뽑을 중복조합의 수와 같습니다. 3. 코드 from itertools.. 2022. 6. 4.
[구현/수학] 백준 11966 2의 제곱인가? - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11966번: 2의 제곱인가? 자연수 N이 주어졌을 때, 2의 제곱수면 1을 아니면 0을 출력하는 프로그램을 작성하시오. www.acmicpc.net 2. 문제 풀이 주어진 수가 2의 제곱인지 판별하는 문제입니다. 간단한 문제지만 실수하기 쉽습니다. 2의 0제곱인 1도 포함되야 하며, 2의 배수 판별과 혼동하면 안됩니다. 2의 제곱이니, 일일이 2를 곱해가며 확인해야 합니다. 3. 코드 # 입력 N = int(input()) # 2의 제곱 판별 num = 1 while True: # 2의 제곱이면 1 출력 if num == N: print(1) break # 2의 제곱이 아니면 0 출력 elif num > N: print(0) break num *= 2 주.. 2022. 6. 3.
[DP/동적계획법] 백준 1904 01타일 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 2. 문제 풀이 1과 00의 조합으로 만들 수 있는 길이가 N인 2진 수열의 개수를 구하는 문제입니다. N = 1) 1 => 1개 N = 2) 11, 00 => 2개 N = 3) 111, 001, 100 => 3개 N = 4) 1111, 0011, 1001, 1000, 0000 => 5개 N = 5) 11111, 00111, 10011, 11001, 11100, 00001, 00100, 10000 => 8개 규칙을 잘 .. 2022. 6. 2.
[구현/수학] 백준 2959 거북이 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2959번: 거북이 첫째 줄에 거북이가 생각한 네 양의 정수 A, B, C, D가 주어진다. (0 < A, B, C, D < 100) www.acmicpc.net 2. 문제 풀이 거북이가 만들 수 있는 직사각형의 최대 넓이를 구하는 문제입니다. 주어진 정수 네 개가 1, 2, 3, 4일 때, 만들 수 있는 직사각형의 최대 넓이 3입니다. ( 1 * 3 = 3 ) 작은 변을 기준으로 넓이가 결정되기 때문에, 1, 3번째로 작은 변이 사용됩니다. 3. 코드 # 입력 A, B, C, D = sorted(map(int, input().split())) # 가장 큰 직사각형 너비 계산 print(A*C) 2022. 6. 1.
[구현/수학] 백준 10178 할로윈의 사탕 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 10178번: 할로윈의 사탕 할로윈데이에 한신이네는 아부지가 사탕을 나눠주신다. 하지만 한신이의 형제들은 서로 사이가 좋지않아 서른이 넘어서도 사탕을 공정하게 나누어 주지 않으면 서로 싸움이 난다. 매년 할로윈 www.acmicpc.net 2. 문제 풀이 사탕의 몫과 나머지를 구하는 문제입니다. 3. 코드 # 입력 T = int(input()) for _ in range(T): total, divide = map(int, input().split()) print(f"You get {total//divide} piece(s) and your dad gets {total%divide} piece(s).") 매우 간단한 계산문제입니다. 이런 문제의 경우, 출력형.. 2022. 5. 31.
[DP/동적계획법] 백준 14501 퇴사 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 2. 문제 풀이 주어진 스케줄 내에서 최대 이익을 구하는 문제입니다. 2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP) [ Contents ] 1. 동적 프로그래밍(Dynamic Programming, 동적계획법) 동적계획법(Dynamic programming, DP): 작은 문제들에 대한 결과를 배열(리스트)에 저장하고, 이를 이용해서 입력 크기가 더 큰 문제를 점진.. star7sss.tistory.com .. 2022. 5. 30.

티스토리툴바