https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 간단한 그래프 탐색 문제. BFS 알고리즘의 구현에 대해서 묻고 있다. 클래스3 문제에 해당한다. 굳이 신경써줄 점이라면 입력으로 받은 지도를 잘 저장하고 있다가 숫자를 출력할때 원래 갈수 있는 땅인데 고립/격리되어있어서 가지 못한 땅인지 원래부터 갈수 없는 땅인지 둘을 구분할때 사용해야 한다. 이런 2차원 격자를 탐색할때 int dx[] = {1,-1..

절사평균을 구현해내는 문제. 클래스2에 새로 들어간 문제가 되어서 클래스2 금장이 은장이되었길래 풀어보았다. https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 절사평균을 구하는 방법은 문제에서 제시해주고 있으므로 문제에서 말하는 바에 따라 계산해 주면 되는데, 반올림하는법을 여기서 짚고가면 도움이 될 듯 하다. 내가 아는 바로 C언어에는(Cpp에는 있을지도 모르겠다) 반올림이 없으므로, floor(바닥함수), ceil..

https://www.acmicpc.net/problem/1498 1498번: 주기문 어떤 문자열 X를 n번 연달아 쓴 것을 (X)^n으로 나타내기로 하자. 예를 들어 (ab)^3는 ababab를 의미한다. 어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있다면, 그리고 n이 1이 아니라면 Y를 주기문 이라고 한다 www.acmicpc.net 실패함수의 응용의 응용 반복되는 가장 작은 문자열 == 문제에서 원하는 "주기문" 의 길이를 https://blog.koderpark.dev/263 백준 BOJ 1305 - 광고 @이화월백 이 골라준 태그 문제풀이 오늘의 태그는 KMP되시겠다 https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 ..

https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 등수의 차이가 $K$보다 작거나 같으면서 이름의 길이가 같은 친구들의 쌍 갯수를 세는 문제이다. 평범하게 생각하면 $O(N)$으로 훑어가면서 $O(2K)$에 등수의 차이가 작은 구간을 순회하게 되는데, 이 경우에는 $O(KN)$으로 TLE를 받아 제한시간 내에 문제를 해결할 수 없다. 투포인터를 활용한 스위핑으로 문제를 해결했다. 두개의 포인터 $l$ 과 $r$ 을 만드는데, ..

DP + BFS 문제. https://www.acmicpc.net/problem/16397 16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 www.acmicpc.net dp[k] 를 숫자 $K$를 만드는데 필요한 최소한의 버튼 누름 횟수 라고 하고, 숫자 $K$인 상태에서 두 버튼을 눌렀을때 변화하는 수를 각각 $A(K)$, $B(K)$ 이라고 하면 dp[A(K)] = dp[k] + 1 dp[B(K)] = dp[k] + 1 이 된다. 버튼 A, B를 누를 때 각각 숫자가 99,999..

https://www.acmicpc.net/problem/17212 17212번: 달나라 토끼를 위한 구매대금 지불 도우미 달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은 www.acmicpc.net DP 알고리즘 문제. dp[k]를 k원 계산을 할때 필요한 최소 동전의 개수로 정의하면 dp[k-a] 에서 a원어치 동전을 b개 지불하면 dp[k-a]+b = dp[k]가 되므로 dp[k] = min({dp[k-1], dp[k-2], dp[k-5], dp[k-7]})+1 이 된다. 해당 식을 그대로 적용해서 재귀문을 이용해 풀어도 되고 나는 바텀업 DP를 짰다. 입..

부분합 배열 만들어서 해결했다. 부분합 배열을 만들지 않는 O(T*N^3) 풀이로도 풀 수 있다고 한다. 내가 구현한 코드의 시간복잡도는 O(T*N^2) https://www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 부분합 배열을 미리 계산해놓고 답을 구하는데, 이때 sum[e] - sum[s] 를 통해 값을 구할 때 e와 s가 같아지는, 즉 아무것도 더하지 않아서 subarray의 길이가 0이 되는 경..

우선순위큐를 죽어라 바이럴하는 문제 우선순위 큐(특히 STL의 그것) 에 대해 알고있다면 쉽게 해결할 수 있는 문제였다. https://www.acmicpc.net/problem/14235 14235번: 크리스마스 선물 크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 www.acmicpc.net 아이들이 요구할때마다 가장 가치가 큰 물건을 꺼내야 하기 때문에, 우선순위 큐를 통해서 우선순위(가치) 가 높은 숫자를 꺼내서 하나씩 출력해주면 된다. 굳이 우선순위 큐 아니더라도 중복 감안할수 있는 멀티셋 같은거 활용해도 되지 않나 싶기도 하고 아마 그냥 반복문으로도 해결을 할..

https://www.acmicpc.net/problem/3049 3049번: 다각형의 대각선 세 대각선이 한 점에서 만나지 않는 볼록 N각형이 주어졌을 때, 대각선의 교차점의 개수를 세는 프로그램을 작성하시오. 아래 그림은 위의 조건을 만족하는 한 육각형의 교차점 그림이다. 모든 www.acmicpc.net 수학문제. "세 대각선이 한 점에서 만나지 않는" 이라는 조건이 중요하다. 근데 아마 지문이슈가 좀 있는거같은게 N>=3 인 N개의 대각선이 한점에서 만나지 않는 이 좀 더 정확하지 않나 싶다. 암튼 세 대각선이 한 점에서 겹치지 않는다면 대각선의 교차점이 생기는 경우는 무조건 두 대각선이 서로 한 점에서 만나는 경우인데, 대각선은 볼록 N각형의 꼭짓점에서 임의의 점 두개를 골라서 만들어 낼 수 있..

범위가 터무니없어서 의심이 갔던 문제. https://www.acmicpc.net/problem/9660 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 풀고나서 확인해보니 돌 게임3의 확장버전이라고 한다 돌 게임 3도 풀고 와야지 히히 범위가 하도 터무니 없다는 점에서 무언가 꼼수가 있겠다 싶어 일단 100개 정도만 dp를 통해서 구해보았다. dp를 통해 구한 방법은 dp[k-1], dp[k-3], dp[k-4] 중에 창영이가 반드시 승리하는 경우가 있다면 상근이의 승리, 아니라면 창영이의 승리에 해당한다. 중요한것은 아니니 짧게 적어보고 암튼 해당 방법을 통해서 구해놓고 보니 알수 있었던 점으로 1111 네개가 붙어있는..