블로그 언저리인 무언가

문제 : 1753 최단경로 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 방향 그래프가 주어졌을 때, 시작점에서 다른 모든 점까지의 최단경로를 구해 출력하는 문제이다. Dijkstra 알고리즘을 사용해 순회한 후 경로가 존재하는지 체크해 배열의 값을 출력하면 된다. Code #include #define ll long long #define INF 987654321 using namespace std; typedef pair pll; struct ABC { ll idx, dst; ..

일단 저번에 가장 중요한 부분들은 구현을 얼추 했으니 이제부터는 좀 부가적인 기능을 만들기로 했다. 내 목표는 아무것도 없이 마작 패만 있을 때도 웹사이트만 켜면 다른 모든 것을 할 수 있는 것이었기 때문에 가장 먼저 떠오른 주사위를 굴리는 기능을 만들기로 했다. 처음에는 이미지를 가져와서 쓸까 하다가 그냥 그리드 그리는 법을 연습하는 셈 치고 손수 도트를 찍어서 주사위 모양을 만들었다. 굴리기 버튼을 눌렀을 때 바로 주사위가 나오니 너무 밋밋해서 setInterval함수를 사용해 주사위가 여러 번 나오는 모션을 만들었다. 주사위를 만들고 나니까 점수가 바뀔 때에도 모션이 있으면 좋겠다는 생각을 해서 만들기 시작했다. 여기에서도 똑같이 setInterval함수를 사용해서 점수가 변할 때 한 번에 바뀌지 ..

뭔가 한 게 없는 것 같은데 2020년이 100일도 안 남았다고 한다. 어제 썼으면 99일 남아서 딱이었는데 다음날이 돼버렸다. 이번 연도는 뭐 수업도 다 온라인으로 진행하다 보니까 내가 대학생이긴 한데 그런 체감도 별로 안 들고 강의가 다 싸강이라 미루게 되고 집중이 안돼서 안 듣게 된다. 저번 학기엔 기말고사 치는 5일이 다 격일이라 전날에 20시간씩 몰아 듣고 나서 겨우 시험 쳐서 이번에는 좀 미리 싸강 좀 듣고 여유롭게 공부해야지 했는데 벌써 3-4주 치 밀린 과목이 수두룩하다. 42서울 신청한 게 드디어 10월 5일부터로 확정이 나서 다행이긴 한데 또 추석 때 집단감염이 크게 터져서 미뤄지진 않을까 걱정이다. 원래 내 플랜은 42서울을 여름 기간에 딱 하고 그거 기반으로 공부를 하면 좀 산업체 ..

문제 : 17953 디저트 17953번: 디저트 창호는 매일 점심마다 디저트를 먹는다. 그런데 같은 디저트라도 매일 느끼는 맛이 달라진다. 어떤 날에는 마카롱을 먹고 매우 행복함을 느끼는 반면 어떤 날에는 ‘차라리 케이크를 먹는게 나� www.acmicpc.net 각 날마다 디저트가 주는 만족감이 주어질 때, 최대로 얻을 수 있는 만족감을 출력하는 문제이다. 날짜를 N, 디저트의 종류를 M이라 할 때 그냥 모든 경우의 수를 구하면 O(M^N)이므로 당연히 시간 초과가 난다. DP 배열을 만들어 전날까지의 만족감 중 최대를 골라 계속 갱신해주면 O(N*M^2)로 시간제한 안에 해결할 수 있다. Code #include #define ll long long using namespace std; ll N, M..

문제 : 15724 주지수 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 �� www.acmicpc.net 직사각형의 범위가 주어질 때 그 안에 사는 사람 수의 합을 출력하는 문제이다. 배열의 길이가 N, 주어지는 범위의 개수가 M일 때 그냥 구하게 되면 O(N^2*M)으로 시간 초과이므로 누적합 배열을 이용해 시간을 O(N^2+M)으로 줄여서 구하면 된다. Code #include #define ll long long using namespace std; ll N, M, T, arr[1050][1050]; int main(){ ios::sy..

문제 : 1342 행운의 문자열 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작� www.acmicpc.net 어떤 문자열이 주어졌을 때 문자를 재배치해 인접한 문자가 같지 않은 문자열의 경우의 수를 구하는 문제이다. 문자열을 정렬한 후 next_permutation을 이용해 모든 경우의 수를 확인하면 된다. Code #include #define ll long long using namespace std; string S; ll ans; int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> S;..

문제 : 14499 주사위 굴리기 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 지도의 크기와 각 칸에 쓰여있는 정수가 주어졌을 때, 주사위를 굴리는 명령이 주어질 때 위에서 보이는 면을 출력하는 문제이다. 각 방향으로 이동할 때 각 주사위의 면이 어떻게 회전하는지 알려주는 roll배열을 선언한 후 해당하는 순서로 값의 순서를 바꾸고 해당하는 칸의 명령을 수행하면 된다. Code #include #define ll long long using ..