Algorithm
-
[Python][백준] 11723번 집합 문제 풀이 | 비트마스킹이 뭐여Algorithm/백준 2022. 3. 16. 10:00
https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 이 문제는 정말 어려웠다 이 문제는 '비트마스킹'이라는 것을 모르면 메모리 초과의 늪에 빠지는 문제이다. 다른 사람들은 Python의 set 자료구조를 이용하여 풀기도 하던데, 그것은 문제의 출제의도와 다른 것 같으니 배제하고 비트마스킹을 이용한 풀이를 소개하겠다. 비트마스킹이란? 비트마스킹(Bitmasking)은 비트, 즉 0과 1, True와 False를 이용하여 문제를 해결하는 것이다. 11723번 문제의 조건을 보면 공집합 ..
-
[Python][백준] 9095번 문제 1, 2, 3 더하기 해결 | DP는 어려워Algorithm/백준 2022. 3. 12. 10:00
동적 계획법(dynamic programming, DP) DP 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다. DP의 핵심 작은 부분을 기억하는 것이다. 왜냐하면 Optimal Structure가 있는 문제를 풀 때 구조를 새로 구할 필요없이, 방금 전 기억한 작은 부분을 불러오면 더 빠르고, 효율적으로 구할 수 있기 때문이다. 오늘은 DP를 이용하여 푼 1, 2, 3 더하기 문제를 풀어보겠다. lines = int(input()) cases = list(int(input()) for _ in range(lines)) for c in cases: dp = [0, 1, 2, 4] + [0 for _ in range(c)] for i in range(4, c+1): dp[i] = dp[i-3] + dp[i..
-
[Python][백준] 1260번 DFS와 BFS | 런타임 에러 (KeyError) 해결Algorithm/백준 2022. 3. 10. 10:00
DFS(Depth First Search)와 BFS(Breadth First Search) 컴퓨터시스템개론, 자료구조, 알고리즘을 하나라도 들어봤다면 누구나 알지. 그래프 이론의 핵심. 모르는 사람은 아래 영상을 보고 배워보자 https://youtu.be/pcKY4hjDrxk CS 1타 강사 Professor Abdul Bari 사랑해요 Python으로 구현해보겠다! 그래프를 구현하는 방법은 인접 행렬 (Adjacency matrix)과 인접 리스트 (Adjacency List)가 있다. 필자는 그 중 인접 리스트, 정확히는 Python의 dictionary 자료구조를 이용하여 그래프를 만들고, DFS와 BFS를 구현할 것이다. 여러 웹페이지, 백준 질문게시판 등등을 참고하여 만들었다. 그래프 구현 n..
-
백준 문제를 4년 만에 해결한 사람이 있다?Algorithm/백준 2022. 3. 3. 10:00
그것도 브론즈 3 문제를? 때는 2017년 6월 8일 17:16:54 풋풋한 17학번 새내기 시절 C는 포인터, 구조체 때문에 머리 싸매고 있었고, Python의 P도 모르던 시절 백준을 풀었다. 아마, 그 때 선배님과 스터디를 했던것 같다. // 그 때 풀었던 소스코드 #include main (){ char text[100]; scanf("%s", text); printf("%s", text); return 0; } 뭔가 이상하다. 이 코드를 보면 1줄만 받고 끝내는데...? 그 때의 나는 무슨 생각이었을까 # 이번에 푼 소스코드 import sys for _ in range(100): print(sys.stdin.readline().strip()) 파이썬으로 하면 이리 간단한데... C는 너무 불편..
-
[Python][백준] 1002번 문제 풀이 | 2년 만에 푼 문제Algorithm/백준 2022. 2. 28. 10:00
2019년 7월 11일 20:44:54 내가 처음 터렛 문제를 푼 시간이다. 2018년 8월 20일에 입대하여 2020년 5월 27일에 전역전 휴가를 나왔으니... 아마 사이버지식정보방에서 풀었을 것이다. 그때의 나는 군대에서 머리가 굳어, 코린이나 다름없었다. 파이썬 문법도 가물가물 했을 것이다. 그러니 이런 실버4 문제도 여러번 틀렸을 것이다! # 2022년 코드 import sys def P1002(): for _ in range(int(input())): x1, y1, r1, x2, y2, r2 = map(int, input().split()) rp = r1 + r2 rm = abs(r1 - r2) distance = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** (1 / 2)..
-
[Python][백준] 백준 1463번 1로 만들기 풀이 | DP와 Divide and conquerAlgorithm/백준 2022. 2. 25. 19:51
DP(Dynamic Programming) 큰 문제를 작은 문제로 나누어 푸는 알고리즘이다. Divide and conquer와는 다르다! Divide and conquer는 큰 문제를 작은 단위로 나누어 해결한 다음 합치는 알고리즘이다. (예시 merge sort) 오늘은 DP를 이용하여 푸는 백준 1463번의 코드를 공유하겠다. # DP를 이용한 풀이 n = int(input()) dp = [0] * max(4, n+1) dp[2], dp[3] = 1, 1 for i in range(4, n+1): temp1 = dp[i//3] if i % 3 == 0 else float("inf") temp2 = dp[i//2] if i % 2 == 0 else float("inf") dp[i] = min(temp..
-
[자료구조][백준] 스택의 활용 | 백준 9012번 풀이Algorithm/백준 2022. 2. 12. 10:00
스택은 후입선출, LIFO(Last In First Out)구조이다. 이 스택을 활용할 수 있는 예시는 웹 브라우저 뒤로 가기) : 가장 나중에 열린 페이지부터 뒤로가기 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력 실행 취소 (undo) : 가장 나중에 실행된 것부터 실행 취소 괄호 검사 등이 있다. 백준 9012번 문제 '괄호'는 올바른 괄호 문자열(Valid PS, VPS)을 찾는 문제이다. 이 문제는 스택 자료구조를 활용하면 쉽게 풀 수 있다. 알고리즘 전공 강의를 열심히 들은 보람이 있다. 들은지 몇달이 지났는데, 기억이 나네 def P9012(): num = int(input()) vps = list(input() for _ in range(num)) stack = [] for st..
-
[Python][백준] 2292번 문제 벌집 풀이Algorithm/백준 2022. 2. 11. 10:00
출처: https://www.acmicpc.net/problem/2292 벌집의 규칙은 다음과 같다. 가운데는 1개가 있고, 그 가운데의 바깥에는 6개, 그 바깥에는 12개, ... 6n개의 양말이 있다. 이 규칙을 다시 쓰면 다음과 같다. 이 규칙에 맞추어, 코드를 짜면 아래와 같다. def P2292(): n = int(input()) sum, i = 1, 0 while True: sum += 6 * i if sum < n: i += 1 continue else: break print(i + 1) if __name__ == '__main__': P2292()