이쪽은 그냥 내가 풀다가 죽어라 헷갈리는 부분이나 새로 배우면서 흥미롭다 싶은부분 메모하는 글들이기때문에 작성방법이 묘할것이라 생각함. 세그트리 밀다가 만난 문제 유형 정렬은 그냥 무지성 std::sort 박아서 정렬을 한번쯤 정리해두는게 좋을것 같았다. 해당 유형의 문제로는 1517번, 23336번, 10090번 등등이 있다 머지소트 merge sort 머지소트는 정렬에 대해서 분할정복을 적용한 케이스라고 이해하면 되겠다. void mergeSort(int s, int e){ if(s

https://www.acmicpc.net/problem/22963 22963번: 3초 정렬 원래 수열인 A = [6, 7, 10, 8, 20]의 4번째 원소인 8을 15로 바꾸면 A = [6, 7, 10, 15, 20]이 되어 오름차순으로 정렬된 배열이 된다. 3번째 원소인 10을 8로 바꾸어도 A = [6, 7, 8, 8, 20]이 되어 오름차순으로 정 www.acmicpc.net 처음 보고 든 생각은 lis였고, lis에 포함되지 못한 값들을 적당히 변경하면 오름차순으로 만들수 있지 않을까 생각. https://blog.koderpark.dev/191 백준 BOJ 14003 - 가장 긴 증가하는 부분 수열 5 https://www.acmicpc.net/problem/14003 14003번: 가장 긴..

https://www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net 이 역시 O(N^2) 문제다 디피 짤때 -1을 INF로 따로 처리한다는게 좀귀찮았다. chtoin map은 글씨를 임의 인덱스로 변환시키고 intoch array는 인덱스를 글씨로 변화시킨다 (k+2)%3을 해준 이유는 (k-1)%3과 동일한 역할을 하면서 C언어에서 음수에 %연산할때 생기는 오류를 막기 위해서이다. inf는 편의상 0x3f3f3f3f = 1061109567으로 했다. 사실 잘 안쓰는데 memset하려니 귀찮아서 이번엔 이걸로 해봤다. dp..

N이 그리 크지 않아서 O(N^2) 풀이를 적용할 수 있다. https://www.acmicpc.net/problem/22971 22971번: 증가하는 부분 수열의 개수 길이가 $N$인 수열 $A$가 주어진다. 수열의 $i$번째 원소($A_i$)로 끝나는 증가하는 부분 수열의 개수를 출력하는 프로그램을 작성하자. 단, 수가 너무 커질 수 있으니 $998\,244\,353$으로 나눈 나머지를 www.acmicpc.net 심지어 문제에서 친절하게 점화식 짜는거까지 도와준다 dp[i]를 Ai로 끝나는 증가하는 부분 수열의 개수로 정의하면 dp[i]를 1로 초기화 해두고, (0 A[i]; } for(int i=1; i

[원석방 산하 폐수방] 1일차 셋 div 2 B번. 뇌절오지게했다. 이놈의다익스트라 구현만 1e9번 했는데 아직도 못외웠다는점에서 코더가 멍청하다는걸 바로알수있다... :blobsob: https://www.acmicpc.net/problem/20160 20160번: 야쿠르트 아줌마 야쿠르트 주세요 첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ www.acmicpc.net 보고 다익스트라는 빠르게 떠올랐었다. 야쿠르트 아줌마 경로구하는것도 그냥 다익스트라를 많이 돌려주면 해결된다. 쬐끔 까다로웠던 부분이 야쿠르..

중학교때 잠깐 봤었던거 같은 문제 [원석방 산하 폐수방] 1일차 셋 div 2 A번이다. https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 일단 간단한 그림을 그려보든지 해서 알수 있는 정보는 벽장문을 옮길때, 횟수는 그냥 A번 벽장을 B번 벽장으로 옮기고자할때 abs(A-B) 이다. 사이에 C번벽장이 있더라도 이는 동일하다. 여기서 좀 이상한 사고를 거쳐서, 브루트포싱하자는 의견에 도달했다. 벽장 두개가 기본적으로 주어져있고, 열려있는 벽장..

처음 봤을때는 전구를 두번 켜고끄고 할필요가 없다는 내용을 떠올리고 무지성 브루트포싱을 시도했지만 바로 2^100 TLE 나만 모르는 웰논 풀이 윗줄에 대해서 비트마스킹 등으로 브루트포싱을 진행해주면, 그 아랫줄은 윗줄의 상태에 따라서 켜고끄고 여부를 결정할수 있다고 한다. 쭉 순회해가면서 처리하기. 구현자체는 그리 어렵진 않았다. https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net #include using namespace std; ..

아름고등학교 인트라넷, 아름인의 가이드 문서입니다. 0. 접속 가능 기기 및 서론 아름인은 컴퓨터와 태블릿 스마트폰 세가지를 모두 지원합니다. 모두 브라우저에서 링크만 입력해주시면 정상적으로 접근할 수 있습니다. 직접 테스트해본 해상도의 목록은 다음과 같습니다. 아이폰 6s lg v30 lg v50 갤럭시 s6 갤럭시 s7 갤럭시 탭 A 8.0 with S pen 15.6인치 표준 노트북 14인치 표준 노트북 21인치 모니터 29인치 울트라와이드 모니터 ( 21:9 비율 ) 아이폰 se 1세대 (4.0인치) 나 4k 모니터와 같은 극단적 환경에서는 정상적으로 동작함을 보장할 수 없습니다. 브라우저는 chrome을 권장합니다. 애플사 기기같은 경우는 safari를 권장합니다만 보유중인 맥북이 없어 직접 테..

11066번 파일 합치기 문제와 매우 동일하므로 따로 풀이를 적지는 않도록 하겠다. 간단히하자면 DP[i][j] => i번째부터 j번째까지를 계산할때의 최소 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net #include #define INF 1234567890 using namespace std; typedef long long int ll; pair arr[567]; ll dp[567][567] = {0}; int f(int s..

DP문제 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net dp[i][j]를 i번째 수부터 j번째 수까지 붙여 만든 문자열이 팰린드롬인가? (1 or 0) 으로 정의해주면 된다 일단 i와 j가 같은 경우에는 항상 팰린드롬일 것이고, 길이가 짝수인 팰린드롬은 i+1 와 j 번째 숫자가 같아야 한다. 이것들을 먼저 처리해 큐에 넣어주고 BFS를 통해 순회해주며 DP배열을 채우면 된다. #include using namespace std; int dp[2345][2345] = {0}; //..