https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 💡IDEA 스택을 사용하는 문제이다. 스택에 차례대로 인덱스와 그 높이를 넣고, 스택의 가장 끝에 있는 값의 높이가 i번째 탑의 높이보다 높은 경우에 결과 배열에 인덱스+1을 저장한다. 높이가 낮은 경우 pop을 해준다. 스택에 아무것도 남지 않을 때까지 반복한 후 다음 인덱스와 높이를 넣는다. 현재 탑을 기준으로 왼쪽, 그러니까 이전의 탑들 중 자신보다 큰 높이의 탑의 인덱스를 저장해야하기 때..
https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 전깃줄이 겹치지 않기 위해서 A의 전깃줄 순 으로 정렬한 후 A와 연결된 B의 전깃줄 중 가장 긴 증가하는 부분 수열을 구하면 된다. i번째와 i번째 이전까지의 j번째 값을 비교하며 dp 배열을 채운다. i번째 dp 값과 j번째 dp 값에 개수를 하나 더한 값 중 큰 값으로 i번째 dp를 갱신한다. dp의 최댓값은 겹치지 않고 연결된 전깃줄의 개수이므로, 결과..
https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 💡IDEA 이분 탐색을 사용하는 문제이다. 어떻게 풀어야할지 감을 못 잡았는데 알고리즘 분류를 보고서야 이분 탐색임을 알았다. 이분 탐색의 왼쪽 값(l)은 배열의 최댓값, 오른쪽 값(r)은 배열 원소들의 총합을 기준으로 시작한다. 가운데 값(m)은 (l+r)//2로 정한다. 블루레이의 크기에 몇 개의 강의가 들어가는지 세어주는 함수를 만들어서 개수를 반환한다. 이 때 블루레이의 크기는 m을 기준으로 판단..
https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 상하좌우로 연결된 부분을 하나의 그림으로 보고, 그림의 크기와 개수를 구해야 한다. 그림의 크기는 BFS를 수행하면서 연결된 곳이 있을 때 마다 개수를 세어주고, 그림의 개수는 BFS가 정상적으로 끝난 후 개수를 세어주면 된다. BFS 과정에서 별도의 방문 배열 없이 기존 입력받은 배열을 갱신해가며 그림이 있을 때(1) BFS를 수행하여 그림이 없다고(0) 변경한..
https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 💡IDEA 그리디를 사용하는 문제이다. A행렬의 3×3 부분 행렬을 뒤집어서 B행렬을 만들어야 한다. 뒤집는 과정을 함수로 만들어서 3×3 부분 행렬의 각 값이 1이면 0으로, 0이면 1로 바꾸어 준다. A행렬과 B행렬의 같은 위치를 비교하여 다른 경우 뒤집는 함수를 실행하고, 횟수를 세어 출력한다. 모든 경우에 뒤집고도 두 행렬이 다른 부분이 있다면 -1을 출력한다. 📌CODE import sys input ..
https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 💡IDEA 정렬을 사용하는 문제이다. 좌표 압축의 조건은 현재 값보다 작은 값의 개수를 구하면 되기 떄문에 정렬이 필요하다. 정렬한 배열에서 자신이 몇 번째인지 딕셔너리로 기록해둔 후 원래 배열의 순서에 맞게 출력한다. 이 때 중복된 값이 있을 수 있으므로 set() 함수를 사용해야한다는 점을 주의한다. 📌CODE import sys input =..
https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 💡IDEA 조합을 사용하는 문제이다. 받아온 k개 길이의 배열 중 6개만큼 선택하는 kC6 경우를 출력하면 된다. itertools의 combinations 함수를 사용하면 쉽게 6개를 조합한 배열을 돌려주기 때문에 그대로 출력한다. 📌CODE import sys input = sys.stdin.readline from itertools import combinations while T..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 💡IDEA BFS를 사용하여 구현하는 문제이다. 인구 이동 조건에 따라 구현하는 과정 중 인접한 나라 중 인구 차이가 L이상 R이하인 나라끼리 연합을 맺는다는 부분에서 BFS를 사용해야 한다. 상하좌우로 인접한 나라가 범위 내에 있고, 방문하지 않았고, 현재 나라와의 인구 차이가 L이상 R이하라면 큐에 추가해주는 식으로 구현했다. 이 때 연합한 나라들을 저장해두는 union 배열에도..
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 💡IDEA 문제의 조건대로 구현해야 한다. 네 개의 톱니바퀴를 어떤 방향으로 돌려야 하는지 알아야 하는데, 현재 바퀴와 맞닿은 바퀴들의 방향도 조정해주어야 한다. 이 과정에서 나는 BFS를 사용했다. 현재 바퀴의 번호를 바탕으로 인접한 바퀴의 맞닿은 부분이 같은지 다른지 판단하여야 한다. 왼쪽과 닿는 것은 현재 바퀴의 -2번째와 왼쪽 바퀴의 2번째이고, 오른쪽과 닿는 것은 현재 바퀴의 2번째..
https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 💡IDEA BFS를 사용하는 문제이다. 음식물이 있는 곳(1)과 없는 곳(0)을 구별하여 음식물이 있는 곳에서 BFS를 돌며 상하좌우로 연결된 음식물을 찾는다. 음식물을 찾으면 음식물이 없다고 갱신해주고, 개수를 센다. 이런식으로 하면 굳이 방문배열을 만들지 않고도 입력받은 맵 배열 하나로 해결된다. BFS를 돌면서 음식물이 없어지기 때문에, 음식물이 있는..
