분류 전체보기

[백준 1744번] 수 묶기 (C++)

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 수 묶기 문제에서 큰 값과 큰 값을 곱해주면, 합이 최대가 되도록 해줄 수 있습니다. 하지만, 입력으로 0 이하의 숫자들도 주어질 수 있습니다. 따라서 양수와 0 이하의 숫자를 구분할 필요가 있습니다. 알고리즘의 기본 틀은 아래와 같습니다. 양수와 음수를 구분하여 각각의 배열에 저장한다. 양수 배열(p)과 음수 배열(m)을 정렬한다. 양수 배열 p[i + 1]이 양수이면, p[i], p[i + ..

[백준 11501번] 주식 (C++)

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 주식 문제에서는 매일 3가지 행동 중 한 행동을 할 수 있습니다. 주식 하나를 산다. 원하는 만큼 가지고 있는 주식을 판다. 아무것도 안 한다. 아래와 같은 동작을 생각해볼 수 있습니다. (단, stock[d]는 d일의 주식 가격) stock[d] stock[d+1]이면, 주식을 판다. stock[d] == stock[d+..

[백준 2457번] 공주님의 정원 (C++)

https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 공주님의 정원 문제는 회의실 배정과 유사한 문제로, 그리디 알고리즘을 이용하여 해결할 수 있습니다. 현재 피어 있는 꽃이 지기 전에 피고, 그 중 가장 늦게 지는 꽃을 선택하면 꽃을 최소의 개수로 선택할 수 있습니다. ⚠️ 주의할 점 빨리 피는 순으로 꽃을 정렬해야합니다. 현재 피어 있는 꽃이 지기 전에 피는 꽃이 없는 경우 0을 출력해야합니다. 3월 2일 이전에 피는 꽃이 없..

[백준 12865번] 평범한 배낭 (C++)

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 평범한 배낭 문제에서 가치가 높은 물건부터 선택하면 최대 가치를 만들 수 있는가? 아닙니다. 아래의 예시를 보면, 무게가 1000인 물건을 먼저 넣으면 가치를 최대로 만들 수 없습니다. 7 1000 1000 10 500 1 100 9 100 8 90 8 80 6 70 4 평범한 배낭 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 ..

[백준 1026번] 보물 (C++)

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net S의 값을 가장 작게 만들기 위해서는 B의 i번째로 큰 값과 A의 i번째로 작은 값을 곱해주면 됩니다. 아래는 전체 코드입니다. #include using namespace std; int a[51], b[51]; bool cmp(int x, int y){return x > y;} int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >..

[백준 2217번] 로프 (C++)

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 로프 문제는 그리디 알고리즘을 이용하여 해결할 수 있습니다. 먼저, 버틸 수 있는 최대 중량이 가장 높은 로프부터 골라야 높은 중량의 물체를 들 수 있습니다. 따라서, 최대 중량을 기준으로 정렬을 수행해야합니다. n번째부터 i번째까지 로프를 선택했을 때, 들 수 있는 최대 중량은 Si * (n - i)입니다. (단, Si는 i번째 로프의 최대 중량) 왜냐하면 i번째 로프의 최대 중량이 가..

2022 코딩 테스트 후기 (라인, 오늘의 집, 네이버, 카카오 , 넥토리얼, KT, SSAFY, 넷마블 ...)

본 게시글은 아래의 코딩 테스트를 경험하고 느낀점에 대한 게시글입니다.주관적인 느낀점이니 참고만 해주시면 감사하겠습니다! 👍 (2022.10월 이후로 게시글 업데이트는 중단되었습니다.) 코테 합격원티드 (2022.04.02)  - 은손 뱃지Summer Coding 인턴 (2022.05.08)SSAFY (2022.05.29)로민 (2022.06.10)네이버 공채 인턴 (2022.06.19)다나와 (2022.07.12)카카오 블라인드 공채 (2022.09.28)넥토리얼 (2022.10.07)KT SW 역량 우수자 (2022.10.15)넷마블 신입 공채 (2022.10.20)코테 불합격라인 플러스 (2022.03.26)오늘의 집 (2022.04.09)카카오 인턴십 (2022.05.07)NCSOFT 인턴 (2..

[백준 4883번] 삼각 그래프 (C++)

https://www.acmicpc.net/problem/4883 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net 삼각 그래프 문제는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다. ⚠️ 단, 비용이 음수가 될 수 있다는 것을 주의해야합니다. 먼저, 테이블 d[i][j]는 i행 j열로 이동하는 최소 비용으로 정의했습니다. 따라서, 초기값은 아래와 같습니다. d[0][0] = INT_MAX, d[0][1] = graph[0][1], d[0][2] = graph[0][1] + graph[0][..