Study/BOJ와 Programmers (111) 썸네일형 리스트형 [BOJ] 18312 시각 c++ (시간문제, string) https://www.acmicpc.net/problem/18312 ✔ 문제 이해 N과 R이 주어진다. 00시 00분 00초부터 N시 59분 59초 까지의 시간 중에서 R이 등장하는 모든 시간들의 수를 구하여라. ✔ 풀이 + 코드 00~N까지의 hour중에서, 00~59까지의 minute중에서, 00~59까지의 second중 K가 포함된 것을 찾기 위해서 for문을 세개 이용한다. #include using namespace std; int main() { int n, k, cnt = 0; cin >> n >> k; string str = ""; for(int h = 0; h [BOJ] 2579 계단 오르기 c++ (DP) https://www.acmicpc.net/problem/2579 ✔ 문제이해 한번에 한 계단 or 두 계단 씩 오를 수 있고 연속된 세 개의 계단을 밟을 수 없고 마지막 도착 계단은 반드시 밟아야 한다. 라는 세가지 규칙을 가진 계단 오르기 게임이 있다. 계단의 수와 계단들의 값이 주어진다. 규칙을 지키며 계단을 오를때 계단들의 값을 더하고 최대 값을 구하여라. ✔ 풀이+코드 계단의 값을 모아둔 배열을 arr, 계단의 최대값을 모아둔 배열을 DP라고 했을때, 아래 그림을 보자. 세 칸 올랐을 때부터 두가지 경우가 생긴다. 1. 두 계단으로 올라오는 경우 2. 연속으로 한 계단씩 밟고 올라오는 경우 이 두가지 경우를 max로 최대값을 구하여 풀어준다. 한 칸 올랐을 때 DP[1] = arr[1] 두 칸 .. [BOJ] 1463 1로 만들기 c++ (dp) https://www.acmicpc.net/problem/1463 ✔ 문제 이해 1을 빼거나, 2로 나누거나, 3으로 나눌 수 있다. 주어진 숫자 N을 앞서 말한 세가지 연산을 이용하여 1로 만들때 최소 횟수를 return하라 ✔ 풀이 + 코드 일일이 1을 빼보고 2와 3을 나눠보기엔 주어진 숫자가 너무 커서 시간초과가 날게 분명했다. 2와 3의 배수들로 계산한다면 빠를것 같다는 생각이 들었지만 어떻게 구현해야 하는지 생각이 떠오르지 않았다. 위 그림의 윗 부분에는 숫자가 1부터 10까지 있고, 1이 되기까지의 걸리는 최소 횟수이다. 나열된 숫자들을 잘 관찰해보면 규칙을 알아낼 수 있다. 1~3은 초기 값으로 제외하고 4부터는 규칙을 가지고 있는데, 다음수로 넘어갈 때 1을 더해주고 더해준 값이 2나 3.. [BOJ] 11656 접미사 배열 c++ (priority_queue) https://www.acmicpc.net/problem/11656 ✔ 문제이해 한 단어의 모든 접미사를 알파벳 순서대로 정렬하라 ✔ 풀이 + 코드 다른사람들 다 풀듯이 문자열 자르고 vector에 저장해서 정렬하는 방식을 사용했는데 시간이 오래걸려서 백준에 있는 다른 사람의 풀이를 참조했다. 더보기 #include #include #include using namespace std; int main() { string s = ""; vector str; cin >> s; for(int i = 0; i < s.size(); ++i) { str.push_back(s.substr(i, s.size())); } sort(str.begin(), str.end()); for(int i = 0; i < str.si.. [BOJ] 하얀칸 c++ (for문 index 규칙) https://www.acmicpc.net/problem/1100 ✔ 문제이해 8x8 크기의 체스판이 있고, 이 체스판의 (0,0)은 하얀색이며 검정색과 번갈아가며 구성되어있다. 8x8 크기의 입력이 주어지고 F가 있는 칸이 하얀칸일때 수를 세주어라. ✔ 풀이 + 코드 이중 for문의 index의 특성을 이용하여 풀었다. i+j가 짝수일 경우에는 무조건 흰색board이다. 규칙적으로 번갈아며 board위에 나타나는 무언가가 있다면 이 방법을 사용하면 실행시간을 많이 단축할 수 있을것 같다. #include using namespace std; int main() { int answer = 0; string s = ""; for(int i = 0; i > s; for(int .. [BOJ] 1068 트리 c++ (트리 그래프, int형 dfs문 활용) https://www.acmicpc.net/problem/1068 ✔ 문제이해 특정 노드를 지웠을 때, 트리의 리프노드(더이상 자식노드가 없는 노드)의 개수를 구하여라. 0~N-1개 까지의 노드들로 구성되어있다. ✔ 풀이 + 코드 처음에는 dfs를void 함수로 만들어 vector list에 값이 존재할 경우 재귀문을 타고, 존재하지 않으면 리프노드의 수를 올리는 방식으로 만들었지만, 반례에서 자꾸 막히게 되었다. 또한 rootnode를 무조건 0이라고 생각하면 또 틀리게 된다. 이 반례를 참고하여 틀린 부분을 알았다 : https://www.acmicpc.net/board/view/112681 아래 코드는 dfs를 돌 때마다 자식 노드의 수를 확인해주어서 자식노드가 없으면 1을 반환에 ret에 차곡차곡.. [BOJ] 11725 트리의 부모 찾기 c++ (트리 특징, dfs) https://www.acmicpc.net/problem/11725 ✔ 문제 이해 루트노드가 1인 트리가 있다. 2부터 N까지 노드들의 부모노드를 순서대로 출력하라. ✔ 풀이 + 코드 자식노드부터 찾으려고 해서 답을 찾지 못했다. 트리는 부모노드부터 탐색하면 자식노드 모두를 탐색할 수 있다는 특징을 갖고 있다. 이를 사용하여 부모노드부터 타고 내려가 모든 자식노드들의 부모노드를 현재 방문하고 있는 노드로 설정해주면 된다. #include #include using namespace std; int N, a, b; vector board[100004]; bool visited[100004]; int arr[100004]; void dfs(int n) { visited[n] = 1; for(int i = 0.. [Programmers] 배달 c++ (우선순위 큐, 다익스트라) https://school.programmers.co.kr/learn/courses/30/lessons/12978 ✔ 문제이해 n개의 마을이 존재하고, 연결된 마을마다 배달하는데 걸리는 시간이 주어진다. 1번 마을에서 출발해서 k이하의 시간이 걸리는 마을의 개수를 구하여라 ✔ 풀이 + 코드 다익스트라 알고리즘을 사용하고, 다익스트라 알고리즘은 간단하게 말하자면 특정 노드까지의 최단 경로가 계속 수정되는 테이블을 갱신하며 최단경로를 구하는 알고리즘이다. 노드의 번호인 number과 최단거리인 shortestTime이 담긴 구조체Town을 우선순위 큐에 담에서 모든 경로를 탐색하고 그 정보를 time 벡터 테이블에 갱신하며 저장한다. 탐색 후 number은 index로, shortestTime은 값으로 설정.. 이전 1 2 3 4 ··· 14 다음 목록 더보기
