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..
Algorithm/Solution
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..
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시간 날렸다 이제 토마토..
8979번: 올림픽 (acmicpc.net) 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 문제 : 올림픽 메달 순위 구하는 문제 해설 : 맨처음엔 배열로 해보다가 그냥 정렬하는게 낫겠다 싶어서 다중 페어벡터를 선언해서 정렬함수를 이용하여 정렬을 해줬다. 근데 순위가 같은 경우가 있어서 다중 반복문을 이용해 같은 걸 찾아주었다. #include #include #include using namespace std; int n, k, ans; vector v; bool op(const pa..
https://www.acmicpc.net/problem/11140 11140번: LOL 당신 친구 지민이는 지금 할 일이 없다. 그리고 매우 심심하다. 그래서 쓸데없는 짓으로 시간을 때우려고 한다. 그래서 단어 하나가 주어질 때 단어에 'lol'이 들어가도록 글자를 추가하거나 변경 www.acmicpc.net 문제 설명 : LOL이 나올 수있는 여러 가짓수를 생각해서 조건문을 만드는 문제였다. L과 L사이에 알파벳 하나가 왔을 때 결과값이 1이 나와야 되는 경우 때문에 정규표현식을 이용하려고했는데 다까먹어서 엄청 헤맸다...저게 맞는지도 모르겠음 정답이라고 떴으니까 맞는거겠지 코드 : #include #include #include using namespace std; int main() { int t..
코딩테스트 연습 - 문자열 다루기 기본 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 문자열 다루기 기본 문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 "a234"이면 False를 리턴하고 "1234"라면 True를 리턴하면 됩니다. 제한 사항 s는 길이 1 programmers.co.kr ⚠ 조심할사항! 문자열 s의 길이가 4또는 6인걸 체크하는 것이 필요..!!! 문제 꼼꼼히 보자~~ #include #include using namespace std; bool solution(string s) { bool answer = true; for (int i = 0; i < s.size(); i++) { ..
코딩테스트 연습 - 4주차 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 4주차 개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부 programmers.co.kr 1. 문제 설명 첫번째 매개변수로 배열로 각 직업군 마다의 언어점수가 주어진다. [ "SI JAVA JAVASCRIPT SQL PYTHON C#", "CONTENTS JAVASCRIPT JAVA PYTHON SQL C++", "HARDWARE C C++ PYTHON JAVA JAVASCRIPT", "PORTAL JAVA JAVASCRIPT PYTHON KOTLIN PHP", "GAME..
코딩테스트 연습 - 두 개 뽑아서 더하기 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 두 개 뽑아서 더하기 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한 programmers.co.kr 🔎 풀이 과정 answer벡터에 모든 더한값을 push하고, 정렬한다. 그 후 중복을 제거해준다. => [C++] vector 배열 중복 제거 하는 법 (tistory.com) #include #include #include using namespace std; vector solution(vector numbers) { ..
