IT 꿈나무 참다랑어

[Gold III] 세 용액 - 2473 문제 링크 성능 요약 메모리: 14224 KB, 시간: 164 ms 분류 이분 탐색, 정렬, 두 포인터 제출 일자 2023년 12월 13일 00:51:05 문제 문제 설명 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가..

문제 요약 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제를 봤을 때 어... 시뮬레이션인가..? 그냥 다 해보면 되는건가..? 했는데 입출력 봤을 때 나라 크기가 50*50이 최대길래 시뮬레이션 맞네 하고 풀었다. 이 문제에서 포인트는 연합이 될 국가를 찾아서 인구수 업데이트를 효율적으로 하는 것이라고 생각했다. 연합이 확정되면 연합에 포함되는 인구수도 확정되는데, 이를 연합을 찾으면서 한번에 계산할 수 있으면 속도가 더 ..

https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 문제를 푸는데 있어서 필요한 것은 사각형의 넓이를 구하기 위해서 도대체 어디가 안으로 들어가 있는 부분의 길이인가를 구하는 것이라고 생각했다. 한시간 이상 고민하다가 안되서 다른 풀이를 읽어보고 다시한번 최적화해봤다. 문제를 읽어봤을 때 방향과 길이를 줄 때 출발지는 랜덤이긴 하지만 연속된 모서리를 돌기 때문에 index 상에서 동서 방향 옆에는 항상 남북 방향이 온다. 그리고 가로 방향 중 가..

이번 주는 그래프 이론과 깊이 우선탐색(dfs), 넓이 우선 탐색(bfs)에 대해서 살펴보았다. 먼저 그래프는 사물이나 개념 간의 연결관계를 수학적 모델로 단순화하여 표현한 것으로 프로그래밍으로 이를 표현하기 위한 방법으로는 대표적으로 인접 행렬과 인접 리스트 방식이 있다. 문제의 조건에 따라 효율적인 방식을 골라 이용하는 것이 중요하다. 인접 행렬은 인접 리스트보다 비교적 dense한 조건 하에 사용하는 것이 더욱 효율적이고 반대로 인접 리스트는 sparse한 조건 하에 사용하는 것이 더욱 효육적이라고 볼 수 있다. 그리고 각각의 방식으로 표현된 그래프는 그 탐색을 위해 dfs와 bfs 방식을 사용할 수 있다. 먼저 dfs(깊이 우선 탐색) 방식은 가지 하나를 길게 탐색에 이용하는 방식으로 이해했다. ..

https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net https://www.acmicpc.net/problem/11025 11025번: 요세푸스 문제 3 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000,000) www.acmicpc.net 요세푸스 문제는 n명의 사람이 ..

백준 문제 11720번에 대한 이야기. string 형태, 즉 char[] 형의 input 이 주어졌을때 이를 어떻게 숫자로 변환해서 합을 구할것인가 나는 처음에 이 문제를 봤을 때 그냥 (int)문자 쓰면 되는 거 아닌가?하고 생각했다. 그리고 아스키코드를 까맣게 잊고 있었기 때문에 출력이 너무 이상하게 나오고 있었다. 입력은 char 배열에 숫자 하나씩 잘 들어가는데 (int)로 형변환만 해주고 나서 sum 으로 합을 구하니 자꾸 합이 255 가 나왔다. 문제는 다음과 같다. 입력 첫줄에 정수의 개수 N이 주어진다. 두번째줄에 0≤x≤9인 정수가 N개 주어진다. ex) 5 54321 출력 입력받은 숫자들의 합을 출력한다 ex) 15 그래서 아스키코드를 다시한번 검색해보았다. 아스키코드표를 살펴보면 아..

요즘 복습 겸 백준 단계별 풀이를 하고 있는데 while을 이용하면서 다른 종료에 대한 조건(ex. a+b 계산에서 a,b가 둘다 0이면 종료) 없이 입력이 끝나면 프로그램을 종료하는 문제(백준 10951번)를 처음 작성하게 되었다. 학교에서 그래도 프로그래밍 수업을 은근 들었는데 한번도 eof를 이용한 종료를 써본 기억이 없다니..ㅋㅋㅋㅋㅋㅋ 아무튼 문제의 조건은 다음과 같다. input - 한 줄에 두 숫자 a, b가 입력된다. - 총 몇 개의 테스트케이스가 있을지는 알 수 없다. output - 입력이 종료될 때까지 a + b를 출력한다. 입력예제 1 1 2 3 3 10 5 1 2 7 2 1 출력예제 2 5 13 6 9 3 처음에 cin >> a >> b를 이용해서 a==EOF일때 프로그램을 종료하..