본문 바로가기

전체 글

[c++][백준 21944][multiset + map] 문제 추천 시스템 Version2 - 컴도리돌이 21944번: 문제 추천 시스템 Version 2 recommend, recommend2, recommend3 명령이 주어질 때마다 문제 번호를 한 줄씩 출력한다. 주어지는 recommend, recommend2, recommend3 명령어의 총 개수는 최소 1개 이상이다. www.acmicpc.net 해당 문제는 저번 포스팅에 언급한 version 1가 유사하게 풀었다. 문제에서 알고리즘 분류, 전체 문제, 난이도의 크기에 따라 문제 번호를 출력을 요구했기에 version 1 문제 보다는 map함수와 multiset 함수를 조금 더 사용하였다. 요번 포스팅은 함수의 쓰임만 언급하겠다.. 1. map group 그룹에서 가장 어려운 문제 또는 쉬운 문제를 출력하는 명령어가 있기에 그룹에 해당한 번호에 대.. 더보기
[c++][백준 21942][해시/파싱] 부품 대여장 - 컴도리돌이 21942번: 부품 대여장 첫 번째 줄에 부품 대여장에 작성된 정보의 개수 $N$, 대여기간 $L$, 벌금 $F$이 공백으로 구분되어 주어진다. 대여기간 형식은 DDD/hh:mm으로 DDD는 일, hh는 시간, mm은 분을 의미한다. (000/00:00 는 주어 www.acmicpc.net 해당 문제는 5번을 틀렸다.. 정말 제출하고 나서 실패라는 문구를 보면서 맞왜틀을 외쳤다.. 요번 문제는 풀이과정보다는 왜 틀렸는지를 언급하는 게 좋을 것 같다.. 1. 너무 멍청했다. 빌리고 반납 기간이 최대 한 달이라는 안일한 생각을 했다. 2월에 빌리고 11월에 반납할 경우를 생각해보자. 나는 month라는 배열 값에 달의 일수를 입력하여 사용하였다. 그다음에 빌린 달과 반납하는 달의 차이가 한 달 이상일 경우 .. 더보기
[c++][백준 21937][bfs] 작업 - 컴도리돌이 21937번: 작업 민상이가 작업할 개수 $N$와 작업 순서 정보의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째줄부터 $M + 1$ 줄까지 작업 $A_i$와 작업 $B_i$가 공백으로 구분되어 주어진다. 이때 두 값의 의미는 작 www.acmicpc.net 풀이 과정 해당 문제는 bfs,dfs로 풀어도 될 것같다. 나는 bfs가 친숙해서 해당 문제를 bfs를 풀었다. 입력 값 'process'라는 벡터는 이차원 배열로 구성하였고 해당 노드의 자식 노드를 삽입해줬다. 그 다음 문제에서 요구하는 x라는 입력 값을 받아서 해당 x에 대한 bfs 탐색을 한다. 그 다음부터는 평범한 bfs 코드이다. x 밑에 있는 자식 노드가 있고 해당 자식 노드를 방문하지 않았다면 큐에 삽입하여 해당 자식노드를 탐색.... 더보기
[c++][백준 21938][bfs] 영상 처리 - 컴도리돌이 21938번: 영상처리 화면의 세로 $N$, 가로 $M$ 값이 공백으로 구분되어 주어진다. 두 번째 줄부터 $N + 1$줄까지 $i$번째 가로를 구성하고 있는 픽셀의 $R_{i,j}$, $G_{i,j}$, $B_{i,j}$의 값이 공백으로 구분되어 총 $M$개 주어진 www.acmicpc.net 풀이 과정 해당 문제는 bfs로 문제를 해결할려고 결정하였고, 정말 쉽게 풀었다. 하지만 결과는 실패.. 정말 맞왜틀.. 처음에는 내 로직이 틀린 줄 알았다. 그래서 다른 사람 코드를 보고 참고했는데 좀 더 간단하게 구현했을 뿐이지 별 차이가 없는 정말 쉬운 문제였는데,,, 그래서 반환 값 문제인가 해서 long long으로도 바꿔보고 double형으로도 바꿔봤지만 계속 실패만 하였다. 그래서 차근차근 input.. 더보기
[c++][백준 21923][BFS] 곡예 비행 - 컴도리돌이 21923번: 곡예 비행 동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 www.acmicpc.net 풀이 과정 상향과 하향을 나누어서 BFS 탐색을 하였다. (상향) 방향은 위, 오른쪽으로 오른쪽과 위로만 탐색하며, 정해진 2차원 배열 안에서 시작점부터 오른쪽 모서리까지 이동하면서 최대 이동 값을 저장한다. (하향) 방향은 위, 왼쪽으로 왼쪽과 위로만 탐색하며, 정해진 2차원 배열 안에서 끝점에서 왼쪽 모서리까지 이동하면서 최대 이동 값을 저장한다. 끝점과 시작점의 BFS 탐색이 끝났으면 위치에 따른 둘의 합이 제일 큰 값을 출력한다. #include #include.. 더보기
[c++][백준 21924][최소 신장 트리][MST] 도시 건설 - 컴도리돌이 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 풀이 과정 알고리즘 코딩 문제를 어느 정도 풀었으면 해당 문제에서 예로 사용한 그림만 봐도 최소 신장 트리 알고리즘으로 풀어야한다는 것을 단번에 알 수 있을것이다. 여기서 최소 신장 트리는 그래프 내의 모든 정점을 포함하는 트리중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 최소 신장트리는 각 간선의 가중치가 동일하지 않을 때 단순히 가.. 더보기
[c++][백준 14499][구현] 주사위 굴리기 - 컴도리돌이 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 과정 더 쉽게 풀 수 있는 방법이 있을거 같지만 시간을 재고 푸는 바람에 하드 구현을 했던거 같다.. 방향 값이 입력 받을 때마다 먼저 주사위를 이동시켜서 바깥으로 이동할 경우는 제외시켰다. 안쪽으로 이동할 경우 rotation 함수를 실행 시키는데 해당 함수는 방향과 이동된 좌표(주사위 입장에서는 바닥)를 넘겨 주었다. 그 이후에는 간단하게 구현하는 방법이 생각나지 않아서 주사위의 배열 값을.. 더보기
[c++][백준 21919][에라토스테네스의 체][유클리드 호제법] 소수 최소 공배수 - 컴도리돌이 21919번: 소수 최소 공배수 수열 중에 소수는 2, 3, 5가 있다. www.acmicpc.net 풀이과정 1. 주어진 입력 값중에서 소수가 존재하는지 판정한다. -> 에라토스테네스의 체를 이용하여 소수를 찾는다. 에라토스테네스의 체 : 소수란 약수가 오로지 1인 수이다. 즉, 1을 제외한 수의 배수가 되는 수는 소수가 아니다. 에라토스테네스의 체는 이러한 소수의 개념을 이용한 알고리즘으로 임의의 수 n까지의 소수르 구하고자 할 때 2부터 n의 제곱근까지 돌며 모든 배수들을 소수에서 제외시키는 방식이다. 시간 복잡도 : O(Nlog(logN)) 2. 소수가 존재할 경우 -> 유클리드 호제법을 이용하여 최대 공약수를 구한다. 시간 복잡도 : O(log(N)) 3. 주의 사항 : 최소 공배수의 크기를 고.. 더보기
728x90

티스토리툴바