전체 글 (58) 썸네일형 리스트형 백준 6068 시간 관리하기 http://www.acmicpc.net/problem/6068 6068번: 시간 관리하기 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1>N; for(int x=0;x>ti>>si; vec.push_back({si,ti}); } sort(vec.begin(),vec.end()); int before=0; for(int x=0;x 백준 24678 돌 무더기 게임1 http://www.acmicpc.net/problem/24678 24678번: 돌무더기 게임 1 첫 번째 케이스에서 R의 첫 시행 이후 가능한 다음 상태는 $(0,0,2), (0,2,0), (2,0,0)$뿐이며, B는 더 이상 시행을 할 수 없으므로 이긴다. 두 번째 케이스에서 R의 첫 시행 이후 가능한 다음 상태는 다음 www.acmicpc.net 게임이론 문제였습니다. 개인적으로 발상을 떠올리기 어려운 문제였습니다. 짝수가 2개이상인 꼴로 시작한다면 짝수번째 시행에서 남은 돌을 1개이하로 만들 수 없게 됩니다. 따라서 짝수 2개이상일때 홀수번째시행인 R이 아닐때는 짝수번째 시행인 B가 이기게 됩니다. #include using namespace std; void fast_io() { cin.tie(.. 백준 16238 독수리 http://www.acmicpc.net/problem/16238 16238번: 독수리 첫째 날 1번 칸의 왼쪽에서 날기 시작해 2번 칸의 양을 먹는다. 독수리가 먹은 양의 수는 10마리이다. 2번 칸에 있는 양을 먹었기 때문에, 1번, 2번 칸의 양의 수는 0이 된다. 첫째 날의 밤에 양의 수 www.acmicpc.net 그리디 문제였습니다. 배열에서 한칸에 있는 양을 먹을때마다 전체 배열에 있는 양이 1씩 줄어들며 지나온 칸에 있는양이 없어지는데 직관적으로 순서와 상관없이 먹을 칸을 정할 수 있다는걸 알 수 있습니다. 예를 들어 배열에 1 5 1 10 1 11 1 이라 했을때 지나온 칸들의 양은 없어지므로 5 10 11만 택해서 먹을 수 있는것입니다. 따라서 우리가 t시간동안 양을 먹는다 할때 먹는 .. 공룡책 정리 1 Computer System은 크게 네 파트로 나눌 수 있다. H/W OS APP USER H/W는 (CPU Memory I/O 장치 등) 기본적인 computing 자원들을 제공한다. 응용프로그램, 우리가 흔히 접하는 프로그램들 엑셀,게임 같은 것들은 앞서 말한 자원들을 사용자가 원하는 방향으로 사용하는 방법을 정의한다. OS는 하드웨어를 제어하며 여러 유저들이 사용하는 응용프로그램들이 하드웨어를 사용하는것을 조정한다. OS는 자체적으로 유용한 기능을 직접적으로 유저에게 제공하기보다 그런 일을 하는 프로그램들에게 환경을 제공해주는 것이라 볼 수 있다. User의 관점 PC같은 경우 한 유저가 모든 자원을 독점하게 설계되어있다. (예를 들어 마우스,키보드) 따라서 유저의 편한 사용성에 맞춰서 설계되며 자.. 백준 1525 퍼즐 http://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net bfs를 통해 푸는 문제였습니다. 초기상태를 고려하지않고 가능한 모든 퍼즐의 상태를 고려해보면 9!이므로 O(362800)인것을 알 수 있습니다. 따라서 우리는 초기상태에서 목표상태로 도달할때까지 상태를 바꿔보면 됩니다. brute force 탐색 중 최단경로를 찾는데에는 bfs가 적절합니다. 이제 남은건 현재 상태에서 중복을 체크하는 방법입니다. 메모리가 32mb로 매우 작으므로 int[3][3]배열을 set이나 map으로 체크하기에는 용량이 부족할 것으로 추측하고 현재 상.. 백준 20943 카카오톡 http://acmicpc.net/problem/20943 20943번: 카카오톡 카카오톡은 주식회사 카카오가 2010년 3월 18일 서비스를 시작한 글로벌 모바일 인스턴트 메신저로, 2020년 기준 $4\,000$만 명의 사용자가 등록돼 있고 시장 점유율이 $96$%로 사실상 거의 모든 국민 www.acmicpc.net map을 사용해 푸는 문제였습니다. 교차하는 두 직선의 쌍을 구하는 문제였습니다. ax+by+c꼴로 주어지는데 결과적으로 기울기는 a/b가 됩니다. 두직선은 기울기가 같지않는 이상 교차하기때문에 각각 기울기로 분류하면됩니다. 실수계산을 피하기 위해서 a와 b의 최대공약수로 나눠준 a,b값을 pair로써 map의 key값으로 사용했고 각각 a=0 인경우 b=0인경우를 나눠서 구했습니다. .. 백준 2629 양팔저울 http://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net DP를 이용해 푸는 문제였습니다. 추의 개수가 30이므로 추가 올라갈 수 있는 모든 경우의 수를 고려하기에는 시간복잡도가 매우큽니다. O(2^30) 따라서 우리는 구슬과 추의 무게범위가 크지 않은 것을 이용해야합니다. DP를 통해 무게에 대한 경우의 수로 바꿔야합니다. 따라서 모든 추를 어떤 무게에 대해서 더하고 빼는 것으로 경우의 수를 셀 수 있습니다. 배열의 크기를 정할때 중요한 것은 무게를 빼고.. 백준 23759 비슷한 문자열 http://www.acmicpc.net/problem/23759 23759번: 비슷한 문자열 첫째 줄에 정수 $N$, $K$가 공백을 사이에 두고 주어진다. $(1 \leq N \leq 5 \times 10^5, 1 \leq K \leq 10)$ 둘째 줄부터 $N$개의 줄에 걸쳐 길이가 $K$인 문자열이 한 줄에 하나씩 주어진다. 모든 문자열은 알 www.acmicpc.net DP를 이용해 푸는문제였습니다. 최장 비슷한 부분 문자열집합을 구하는걸로 볼 수 있습니다. LIS 같이 풀수도 있고 문자열의 길이가 작으므로 문자열에 대한 상태를 기록하여 DP로 구할수 있습니다. 저는 DP를 이용해 풀었는데 각각 문자열 위치에 어떤 문자에 대해 현재까지의 가장 긴 비슷한 문자열길이를 저장하여 구하였습니다. #in.. 이전 1 2 3 4 5 6 ··· 8 다음