본문 바로가기

Algorithm

 (640)
6731. 홍익이의 오델로 게임 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWefzFeq5P8DFAUh SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com DFS로 풀면 시간초과 및 종료 시점에 대한 지정이 힘들다. 규칙을 찾아서 푸는 것이 관건인 문제. 어떤 모양이 주어졌을 때, 그 모양을 만들기 위해서 최소로 뒤집어야 하는 좌표는 i,j에 있어서 해당 열과 행의 검은색의 개수의 합이 홀수인 좌표이다. 따라서 각 열과 행의 검은색 개수를 구하고 이때 i,j 좌표 자체가 검은색이면 행과 열의 개수 합에서 -1을 해줘야 함. 홀수인 좌표의 개수를 카운트..
백준 2110번 공유기 설치 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는..
백준 게리맨더링 2 재풀이 완전 탐색으로 간단히 풀 수 있었다. #include using namespace std; int N; int arr[21][21]; int main(void) { cin >> N; for (int i = 1; i arr[i][j]; } } int mina = 987654321; for (int i = 1; i
6719. 성수의 프로그래밍 강좌 시청 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWd7sgDatsMDFAUh SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 그동안 K개 선별에 DFS를 사용했던 것은 선별되는 값 자체의 의미보다 그 값으로 다른 결과가 만들어지기 때문에 사용했던 것인데, 이번 문제는 그냥 최대값 K개를 뽑으면 되는 것이므로 DFS를 쓰면 시간초과가 발생한다. 그냥 sort를 통해 정렬 후 K값 선정. 중요한 것은 평균은 갈수록 큰 값과 진행 할 수록 최대이기때문에 최대값 K개를 작은것부터 평균을 해서 진행하면 끝. #include #in..
4613. 러시아 국기 같은 깃발 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 하나씩 바꿔가면서 DFS가 아니고 행을 3개로 분리하는 로직을 생각해 내면 끝. #include #include #include using namespace std; string arr[50]; int N, M; int mina; vector vec; void DFS(int cur) { if (cur == 2) { v..
1238. [S/W 문제해결 기본] 10일차 - Contact https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15B1cKAKwCFAYD&categoryId=AV15B1cKAKwCFAYD&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 끝 점에서 우선순위로 카운트랑 넘버를 넣어서 카운트 기준으로 1차정렬 넘버 기준으로 2차 정렬 해서 가장 큰 카운트의 가장 큰 넘버를 출력. ///////////////////////////////////////////////////////////////////////////////////////////// //..
1861. 정사각형 방 보호되어 있는 글입니다.
1231. [S/W 문제해결 기본] 9일차 - 중위순회 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD&categoryId=AV140YnqAIECFAYD&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 트리 탐색이 어떻게 동작하는지 그대로 구현하면 되는 문제. #include #include using namespace std; struct Node { char c; int left; int right; }; string str; Node arr[101]; int parent[101]; bool visit[101];..

티스토리툴바