겜돌이의 개발일지

문제 백준 2473 세 용액 C++ 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 용액문제 (https://gamedoridori.tistory.com/238)의 심화형이다. 오름차순으로 용액이 정렬되어있지 않으므로 먼저 정렬을 해준다. 그리고 각각의 용액에 대해, 그 용액과 합의 절댓값이 최소가 되는 두 용액을 두 포인터로 찾아준다. 여담으로 용액과 두 용액 문제는 입력값이 -10억~10억이라 int 자료형으로도 문제가 없었지만, 세 용액 문제는 int 자료형을 사용할 시에 ab..

문제 백준 2467 용액 C++ 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 일반적인 두 포인터 문제이다. 앞 뒤에서 용액을 확인한 뒤, 주어진 조건에 따라 start와 end를 이동시켜주면 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include #in..

문제 백준 1937 욕심쟁이 판다 C++ 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 dp와 dfs가 섞인 재밌는 문제이다. dp 배열은 해당 칸에서 판다가 시작할 시에, 먹을 수 있는 최대 대나무를 가지고 있는 배열이다. (-1로 초기화) dfs를 돌면서 다음과 같은 과정을 거친다. 1. 어느 곳에서 시작하든, 자기 자신 칸에 있는 대나무는 먹을 수 있다. 따라서 dp 배열의 최소값은 1이다. result 값을 먼저 1로 설정한다. 2. 상하좌우 순으로, 다음값이 현재값보다 크다면 둘 중..

문제 백준 17299 오등큰수 C++ 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 오큰수 문제와 크게 다를 건 없다. 비교하는 방식만 몇번 나왔는지 횟수를 저장하고 있는 cnt 배열을 비교하는 것으로 바꿔주면 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 5..

문제 백준 4883 삼각 그래프 C++ 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net 풀이 기본적인 DP문제이다. 각 행은 3열이고, 조건에 따라 열까지의 최소 거리를 저장하는 배열 dp에 따라 최소 거리를 갱신해준다. dp 배열의 첫 행 첫 열에는 쓰레기값을 넣어주는데, 시작 지점이 따로 있으므로 첫행첫열에서 최소 거리를 갱신하지 못하게 하기 위함이다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27..

문제 프로그래머스 132266 부대복귀 C++ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 아주 일반적인 BFS문제. destination(start)부터 BFS를 돌면서, 각각 노드 첫번째 방문시에 얼마나 걸렸는지(cnt)를 배열(dist)에 넣어준다. 방문 전에 배열은 -1로 초기화하고, 처음 방문시에 걸린 횟수(cnt)를 넣어준다. BFS 특성상 가장 첫 방문이 최단 거리이므로 dist값이 -1이 아니라면 이미 방문한 노드이니 갱신해주지 않는다. BFS를 끝내면 sources에 들어있는 노드까지 얼마나 걸리는지를 answer에 넣어준다. 소스..

문제 프로그래머스 132265 롤케이크 자르기 C++ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 토핑 최대 개수가 백만개이기 때문에, 시간복잡도에 유의해야 한다. 루프를 여러번 돌면 시간초과가 나므로, 처음 top2 확인에 1번, 토핑 전체 검사 후 answer 증가에 1번 루프를 돈다. 먼저 토핑 전체를 검사해서, 서로 다른 토핑의 개수를 top2에 저장한다. 그 후에 토핑을 하나하나 확인해서, top1에 없는 토핑이라면 top1을 늘려준다. top2에 토핑이 없어지면 top2를 1감소시킨다. top1와 top2가 같다면 answer를 1증가시..

문제 백준 2240 자두나무 C++ 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 풀이 전형적인 dp문제이다. 1번에서 시작한다는 문구를 놓쳐서 디버깅하는데 시간이 쪼오끔 걸렸다... (2번에서도 시작할 수 있는줄 알았음) 움직이지 않는 경우에는 첫번째에 있는 경우이므로, 그 전칸에서 바로 가져오고 1번째 칸은 1번째에서 그대로 내려오거나 / 2번째 칸에서 바꾸거나 2번째 칸은 2번째에서 그대로 내려오거나 / 1번째 칸에서 바꾸거나 각각 2가지 경우가 있으므로 이를 비교하여 더 큰 값을 취하고 dp배열에 저장해두면 ..

문제 프로그래머스 할인 행사 C++ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 조건을 만족하려면 want에 있는 물품이 number에 있는 수 만큼 할인 받아야 한다. map을 활용해 cntMap 선언한 뒤 할인을 받을 때마다 cntMap의 값을 1감소 시키고, 할인 받지 못할 때는 cntMap의 값을 1증가 시키면 된다. 11일차 부터는 해당 날짜의 물품의 cntMap 값을 1감소시키고 (할인 받았으므로), 해당 날짜로 부터 10일 전 물품의 cntMap 값은 1 증가시키면(할인을 이제 못 받으므로) 된다. 오랜만에 map 자료 구조를 이용하는..

문제 백준 10026 적록색약 C++ 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 주어진 조건에 따라 DFS나 BFS를 활용하여 그래프를 탐색해주면 된다. 색약인 경우와 색약이 아닌 경우를 color로 구분하여, 색약이 아닌 경우에는 색깔이 같을 때만 queue에 push해주고 색약인 경우에는 빨강과 초록의 구분이 없게 하여 queue에 push 한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28..