원

https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 구간 내 숫자가 모두 같으면 넘어가고 만약 구간 내 숫자가 다른 게 하나라도 있다면 총 9등분한 후 등분한 부위를 다시 검사해주는 것이다. 큰 것에서 작은 것으로 넘어가기 때문에 분할 정복 알고리즘을 사용하여 해결할 수 있다. #include #include #include #include #include #include #include #include #include #include ..

https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i > v[i]; } cin >> X..

https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 이분 탐색을 이용해서 해결해야 하는 문제이다. 처음 가로등과 마지막 가로등을 제외하면 가로등끼리 떨어진 거리가 존재한다. 그 거리를 비교값으로 설정해 (내가 임의로 지정한 길이 * 2)보다 가로등 사이 걸이가 길다면 가로등 사이 밝히지 못하는 구간이 존재한다는 의미이다. 위 방법으로 이분 탐색을 진행해주면된다. 그리고 처음 가로등은 (내가 임의로 지정한 길이)보다 좌표값이 더 큰 곳에 위치한다면 처음..

https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 이 문제도 백트래킹으로 완전 탐색을 하는 문제이다. 개인적으로 전에 풀었던 문제가 더 까다로웠던 것 같은데 이 문제가 난이도는 더 높게 등록되어있다. 이 문제는 조건이 구간으로 나누어져 있어서 정렬을 먼저 한 후 몇 개를 최대로 뽑을 수 있는지 먼저 구해주었다. 만약 입력되는 난이도의 개수가 15개인데, 사실상 조건에 만족하는 개수는 2개 뿐이라면 나머지는 필요없는 연산이기 때문이다. 그래서 가장 먼저 범위에 만족하는 최대 개수를 구해주었다. 그리고 그 후는 똑같이 백트래킹 -> 완전탐색으로 구한 후 최종적으..

https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net N과 M을 응용한 문제로 2차원 배열에서 사용해야한다. 인접한 구간끼리는 합을 구하지 않으므로 방문 처리 표시를 통해 인접한 칸을 더하는 것을 방지한다. 그리고 백트래킹을 통해 완전탐색을 해야하므로 한 번 확인하고 나면 방문처리를 원래대로 돌려주어야 하는데 나는 스택으로 몇 개의 인접한 칸을 방문 처리 표시했는지 기억해두고 다시 되돌려야할 경우 기억했던 개수만큼 다시 스택에서 꺼내 방문..

https://www.acmicpc.net/problem/5347 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. www.acmicpc.net 최소공배수를 구하는 문제이다. 유클리드 호제법을 통해 최대공약수를 먼저 구한 후 두 수의 곱을 최대 공약수로 나누어주면 된다. 단, 최소 공배수의 크기가 32비트 정수형을 넘을 수 있다는 점을 주의한다. #include #include #include #include #include #include #include #include #include #include #include #define CUNLINK ios::sync..

https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 문제 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 그림) 각 노드에는 그 곳에 위치한 빌딩의 번호가 붙여져 있다. 또, 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다. 깊이가 2와..

https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 파이썬에서 조건에 따른 정렬을 할 때 lambda를 사용하는데 그것과 관련된 문제이다. 가장 높은 우선순위를 팔린 책의 수로 두고, 팔린 책의 수가 같다면 사전순으로 정렬하는 문제이다. 나는 딕셔너리를 이용해 "책 제목 : 팔린 책의 수"로 설정하고, 모든 입력이 끝나면 딕셔너리를 리스트로 형변환 시켜주었다. 그리고 리스트를 lambda를 이용해 우선순위에 따른 정렬을 해주었다. impor..

https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 이번 문제는 문자열 문자라 파이썬으로 풀어보았다. 요즘 학교 수업 시간에 파이썬을 배우고 있는데 확실히 문자열 관련 문제는 C++보다는 파이썬이 훨씬 풀기에 쉬운 것 같다. 딕셔너리를 이용해서 해결하였고, 딕셔너리도 collections에서 defaultdict()으로 추가까지 할 수 있게 해주었다. 그리고 입력이 끝나면 key값을 기준으로 정렬해주고 출력만 해주면 된다.! import..

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 문제만 읽고 보면 정말 쉬워보여서 그냥 짜고 제출했는데 메모리 초과가 떴다. 문제를 보니 메모리 제한이 12MB였고 내가 한 방식대로 모든 수들을 우선순위 큐에 넣고 해결하려하면 메모리 초과가 날 수밖에 없다. 그러면 어떻게 해결해야하냐면 문제의 힌트가 주어져있다. NxN 형태로 수가 입력이 되고 모든 수는 자신의 한 칸 위의 수보다 크다. 즉 가장 위에 있는 수들이 그 열의 수들 중 가장 작은 값이고 ..