서론 (잡설) ????????????????? 골드바흐의 추측 문제가 재채점 되면서 원래 풀었던 문제가 오답처리되고 말았다. 기존 알고리즘으로는 더이상 풀지 못하게 되었으므로, 소수를 찾는 새알고리즘을 배우는 겸사겸사 몰랐던 파이썬 문법도 배워보자. 소수 찾기 기존 방법 def get_prime(): for num in ...
문제 : https://www.acmicpc.net/problem/16929 접근 DFS 또는 BFS를 통해 풀 수 있다. (여기서는 DFS 사용) 일반 DFS와 다른 점은 한 바퀴를 도는 cycle을 만들어야 한다는 것이다. visited 리스트를 만들어 True, False를 체크하는 것 만으로는 사이클 여부를 알 수 없다. 주요 아이디어...
문제 : https://www.acmicpc.net/problem/27313 접근 다이나믹 프로그래밍을 이용해서 풀 수 있다. 하지만, 동시에 볼 수 있는 애니메이션 K의 범위가 100,000이므로 1, 2, 3 더하기 5 문제처럼 모든 경우의 수를 따지면 바로 시간초과다. 주요 아이디어 N개의 애니메이션을 K개씩 볼 수 있을...
VS Code에서 주피터 노트북 사용하기 VS Code에서 Jupyter 익스텐션을 설치하면 주피터 노트북을 사용할 수 있다. 원하는 폰트, 테마 등 본인이 원하는 작업환경에서 자동완성까지 지원해주기 때문에 여러모로 편리하다. 단축키 역시 정말 유용한 단축키는 대부분 지원하는 것 같다. 일부 단축키는 사용하려면 Jupyter Keymap 익스텐션이 ...
의사코드(Pseudo-Code)란? 개인적으로 의사코드라는 말 보다는 슈도코드가 더 입에 잘 붙기 때문에 여기서는 슈도코드라고 하겠다. 슈도는 ‘가짜’, ‘유사한’라는 의미로, 슈도코는 말 그대로 코드와 유사하지만 진짜 코드는 아닌 코드를 말한다. 보통 파이썬 같은 고수준 언어와 흡사한 형태이고, 엄격한 규칙이 있는 것이 아니기 때문에 일정한 형식...
문제 : https://www.acmicpc.net/problem/1707 이분 그래프란? 이미지 출처 : https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html 이분 그래프란 서로 인접하지 않는 두 그룹으로 나눌 수 있는 그래프를 말한다. 풀이 DFS와 BFS...
문제 : https://www.acmicpc.net/problem/14391 풀이 비트마스크 알고리즘을 이용해 풀어보자 n x m 배열을 조각으로 나누는 경우의 수를 비트마스크로 표현할 수 있다. 조각 합 구하기 백준 문제로 예시를 들어보자 여기서 세로크기가 1인 조각을 1, 가로크기가 1인 조각을 0이라 하면 다음과 같이 나타낼...
비트마스크란? 비트마스크(BitMask)는 데이터를 저장하는 하나의 방법이다. 일반적으로 파이썬에서는 데이터를 리스트에 저장한다. 0, 1 또는 True, False 등의 두 종류의 값이 저장되는 리스트가 있다고 생각해보자. A = [0, 1, 1, 1, 1, 0, 1, 0] A_bool = [False, True, True, True, True...
문제 : https://www.acmicpc.net/problem/1248 문제 아래의 표를 만족하는 정수 수열을 구하는 문제이다. 수열 a의 길이가 n일 때 n행 n열 크기의 표가 주어진다. 표 1 2 3 4 1 - ...
문제 : https://www.acmicpc.net/problem/14889 풀이 기본적으로 팀을 구성할 수 있는 모든 조합에 대해 두 팀의 능력치 차이를 구하는 브루트포스 알고리즘이다. 1. 변수설정 N, S : input으로 받는 변수이다. N은 총 참가자의 수, S는 능력치 조합을 나타낸 2차원 배열이다. ...