본문 바로가기

전체 글

 (119)
백준 : 다리 만들기 2 c++ www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 1. 섬들을 2번부터 시작해서 라벨링 한다!! -> bfs 이용 2. 이제 각 섬에서 다른 섬까지 연결 가능한 모든 다리 생성 후 vector에 저장 -> 길이가 2 이상이여야됨!! -> 두개의 섬 라벨과 다리 길이 value로 이루어진 struct로 관리 3. 길이 작은 순으로 sort 후 크루스칼 4. 모든 섬이 연결이 안됬으면 -1 출력 #include #include #incl..
백준 : 기타줄 C++ www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 풀이 및 후기 1. 어려운 문제는 아닌데 이거 신경쓰는걸 까먹으면 안된다 -> 남은 낱개들을 전부 낱개로 사는거보다 그냥 세트가 더 싸면 세트로 사야됨! #include #include #include using namespace std; int main() { int n, m; int set, one; int answer = 0; int min_set = 1000; int min_one = 1000; //..
백준 : 제곱수의 합 C++ (DP 연습!!) www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 풀이 및 후기 DP는 너무 어렵다 1. 일단 모두 1만 써서 더하는 경우는 항의 수가 자기 자신이므로 그것으로 초기화! 2. 그다음에 본인보다 작은 제곱수를 뺀 모든 경우에서의 DP값들 중 최솟값을 구하기 #include #include #include #include #include #include using namespace std; int main() { int n;..
백준 : 퇴사 c++ www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 1. DFS로 풀었다. 경우는 두가지 1) 그날에 주어진 일을 한다! -> 일을 했으면 이게 끝나는 다음날로 이동!! 2) 그날에 주어진 날은 안하고 다음날로 넘어간다! -> 기존 day에 +1 #include #include #include #include #include using namespace std; int n; int answer = 0; vector v; void dfs(int day, int sum) { if (day > n) { answer = max(sum, answer); return; } //1번경우는 지금 날에 잡혀있..
프로그래머스 : 거스름돈 C++ (DP 사용) programmers.co.kr/learn/courses/30/lessons/12907?language=cpp 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr 풀이 1. 처음에 그냥 DFS 썻다가 효율성 테스트에서 시간초과 뜨더라 #include #include #include #include using namespace std; bool cmp(int a, int b) { return a>b; } int answer = 0; void dfs(int now,int index, vector mone..
프로그래머스 : 기지국 설치 C++ programmers.co.kr/learn/courses/30/lessons/12979?language=cpp 코딩테스트 연습 - 기지국 설치 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5 programmers.co.kr 풀이 및 후기 1. 난 진짜 빡구현보다 이런게 더 어렵다, 아무리 문제를 풀어도 왜 생각이 안날까 1) index 두개로 관리한다 - station, 오름차순으로 정렬되어 있다 - now, 지금 내 위치! 2) now가 n까지 갈때까지 while 루프 지금 위치에 전파가 안온다면 기지국 설치 -> 지금 위치를 왼쪽끝에 걸치게 설치하는..
프로그래머스 : 길찾기 게임 C++ programmers.co.kr/learn/courses/30/lessons/42892?language=cpp 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 풀이 겸 후기 1. 그동안 알고리즘 풀때 포인터를 진짜 거의 안썻는데 이 문제는 포인터 없이는 너무 힘들어서 포인터 공부좀 다시 했다 2. 원래 주어진 벡터를 그냥 index로 치면 몰라도 이건 주어진 노드 정보들을 한번 sort하고 트리 구성하는거라 이게 훨씬 편하더라 1) 노드 stuct - 좌표정보랑, 자식 두명 포인터 2) 초기화 과정 3) 좌표를..
프로그래머스 : 지형 이동 c++ programmers.co.kr/learn/courses/30/lessons/62050 코딩테스트 연습 - 지형 이동 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]] 3 15 [[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]] 1 18 programmers.co.kr 풀이 1. 일단 모든 지역을 사다리 없이 이동할 수 있는 구역으로 묶는다 2. 이제 크루스칼을 사용 1) 하나의 지역은 노드 2) 인접해있는 다른 지역으로 이동할때 드는 사다리 비용이 간선 길이 3) 간선의 정보는 struct 로 저장 -> 섬 두개, 비용 4) 비용에 따라 오름차순으로 정렬하고 유니온파인..

티스토리툴바