2110번: 공유기 설치 (acmicpc.net) 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 난이도 : 골드5 풀이방법: 이분탐색 문제인데, 내가 구한 방식은 일단 좌표를 오름차순으로 정렬을하고, 첫번째 인덱스부터 시작해서 반복문을 돌려 차이가 mid이상이면 두 점 차이가 가능하다는 의미에서 chk=true로 해주었고, 공유기 개수를 +1 해준다. 그다음 mid이상이나오는 인덱스부터 다시시작해서 다음번째 그다다다음번째가 mid이상인지 계속 체크해서 공유..
Algorithm
14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 난이도 : 골드5 풀이과정 : 완전 탐색 문제이다. 모든 경우의 수.. 회전.. 대칭 에 대한 모든 경우의 수를 따져주면된다. 기존 좌표가 (x,y) 라 할때 나올수 있는 회전, 대칭에 대한 경우의 수는 8개 (x,y), (x,-y), (-x,y), (-x,-y), (y,x), (y,-x), (-y,x), (-y,-x) 다음과 같다..!!! 중딩때 배우던가... 이거 rx배열은 부호곱해줘야되서 선언해줬다. 이 걸 ..
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 난이도 : 골드 4 풀이과정 : 다익스트라를 이용한 문제 2차원 배열에서 다익스트라 알고리즘을 활용하면 되는 문제였다. 도둑루피 값은 2차원 배열에 저장하고, 우선순위 큐는 다중 페어를 이용하여 pair (pair 형태로 넣어주도록 했다. 가중치 dist 배열은 2차원 벡터 형태로 선언하였다. 다익스트라를 안다면 2차원 형태를 어떻게 구현하느냐가 주요 문제였음 코드 : #incl..
11779번: 최소비용 구하기 2 (acmicpc.net) 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 난이도 : 골드 3 풀이 방법 : 다익스트라를 이용하는 문제 경로를 출력하는 것이 관건이었다... 경로를 출력하는 방법을 도시 개수만큼 배열(route)을 선언해 주고 다익스트라에서 dist(비용) 이 업데이트 될 때, 업데이트 되는 next인덱스에 전 노드 here 값을 저장 시켜준다. 그러면 route배열의 각 인덱스에는 인덱스 전의 노드의 인덱스 가 저장 되어 있는 것..
1005번: ACM Craft (acmicpc.net) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 난이도 : 골드 3 풀이 방법 : 위상정렬 + dp 문제 ans라는 배열에 각 건물 시간 걸리는거 저장해놓고 위상정렬 돌릴 때 특정건물을 짓기위한 시간 = 건물을 짓기위해 지어야 되는 건물 중 가장 오래걸리는 시간 + 특정건물 걸리는 시간 if (ans[now] + time[next] > ans[next]) { ans[next] = ans[now] + time[next]; } 을 해주면 된다. + 58..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 난이도 : 골드5 풀이 방법 : 가로 세로가 최대 50이기 때문에 전체를 돌아도 될거같아서 각 인덱스 별로 bfs를 돌려서 최댓값을 찾아줬다. 맨처음에 50퍼정도에서 에러가 나서 반례를 찾아봤는데 시작점을 두번 방문하는 오류가 있음을 알게 됐다. 시작점을 1부터 시작해서 나중에 ans-1을 빼주면 해결 코드 : #include #include #include using namespace std; in..
1. 순열 1. swap을 이용한 재귀함수 구현 => 사전순 출력x #include #include #include using namespace std; int n; vector v(10); void permutation(int s, int e) { if (s == e) { for (int i = 0; i < n; i++) { cout
1946번: 신입 사원 (acmicpc.net) 난이도 : 실버 1 풀이 방법 : 문제가 살짝 헷갈렸긴했는데 문제의 의미는 한 사람의 서류등수와 면접등수가 어떠한 다른 사람의 두 등수에 둘 다 지면 안된다는 뜻 머튼 해결방법 pair배열을 선언하여, 서류랑 면접점수를 담게 하고, 서류점수를 기준으로 배열을 sort를 한 다음 면접점수에서 배열 순서대로 arr[i] < arr[i+1] 이면 i+1 의 인덱스를 가진 배열이 둘다 점수가 졌다는 의미이므로 cnt변수에 1씩더해준다. 답은 n-cnt를 출력하면 끝! 이제 n이 십만개고 시간제한이 2초이므로 nlogn이하로 풀어야 되는 문제였음 (n제곱이면 시간초과임 !) 코드 : #include #include using namespace std; int t, ..
7576번: 토마토 (acmicpc.net) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net https://www.acmicpc.net/problem/7569 난이도 : 골드 5 해결 방법 : 굉장히 오래 걸렸던 문제.... 일단 배열 입력자체가 보통은 가로, 세로 를 주는데 세로 가로 수를 줘서 반대로 입력을 해주면 좀더 편하게 풀 수 있다. (이것도 시간 오지게 잡아먹힘 헷갈려서) 뭐튼 bfs로 푸는문제인데 처음에 접근을 잘못해서 연결요소의 개수로 접근해 풀었다가 1시간 날렸다 이제 토마토..
