본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 1446번 : 지름길 https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net brute force로 풀었습니다. 풀이방법 1. 인접리스트로 지름길의 출발점, 도착점 그리고 길이정보들을 간선과 해당 비용으로 생각해 저장합니다. 저장할 때 주의할 점이 두 가지 있습니다. 도착점 - 출발점 사이의 거리가 길이정보 이하라면 사실상 지름길이 아니므로 볼 필요가 없습니다. 배보다 배꼽이 더 큰 상황이죠 두 번째로는 예시에 나와있듯이 도착지점이 d를 넘어가는 경우에도 간선정..
(C++) - 백준(BOJ) 1005번 : ACM Craft https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상정렬 문제였습니다. 풀이방법 1. 기존 위상정렬 문제처럼 x번을 지을 조건이 되면 바로 지을 수 있는 것이아닌 x번 건물의 선제조건인 건물들 중 건설시간이 가장 오래걸리는 건물이 다 지어져야 해당 건물을 지을 수 있습니다. 2. 적절히 입력을 받습니다. 단 방향 그래프의 형태이며 인접리스트로 저장했습니다. 또한 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다. 의미는 그래프의 형태로..
(C++) - 백준(BOJ) 2268번 : 수들의 합 https://www.acmicpc.net/problem/2268 2268번: 수들의 합 첫째 줄에는 N(1≤N≤1,000,000), M(1≤M≤1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는지를 www.acmicpc.net 기본 segment tree였습니다. 풀이방법 1. 기본적으로 data n개에 대해 segment tree를 만드는데 필요한 공간은 n보다 크면서 가장 가까운 제곱수 * 2입니다. 제곱수를 찾기 귀찮기 때문에 n*4만큼의 공간을 할당해줍니다. 2. 입력에 대해 들어있는 값을 갱신하거나 또는 구간의 합을 출력합니다. 명령어가 1인경우에는 입력받은 i,j의 범위가 오름차순이 아..
(Python) - 백준(BOJ) 1340번 : 연도 진행바 https://www.acmicpc.net/problem/1340 1340번: 연도 진행바 평년일 때, 각 달은 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31일이 있다. 윤년에는 2월이 29일이다. 윤년은 그 해가 400으로 나누어 떨어지는 해 이거나, 4로 나누어 떨어지면서, 100으로 나누어 떨어지지 www.acmicpc.net 문자열 처리 문제였습니다. 풀이방법 1. 현재 연도가 윤년이냐 아니냐에 따라 2월의 날짜 수가 달라집니다. 이 말은 윤년에는 하루가 366일이라는 의미입니다. 따라서 먼저 윤년인지 여부를 판단합니다. 2. 비교하는 최소의 단위가 '분'이기 때문에 입력 받은 정보를 분 단위로 치환해야 합니다. * 날의 수를 셀 때 입력받은 달의 이전 달까지..
(C++) - 백준(BOJ) 17827번 : 달팽이 리스트 https://www.acmicpc.net/problem/17827 17827번: 달팽이 리스트 첫째 줄에 노드의 개수 N(2 ≤ N ≤ 200,000), 질문의 횟수 M(1 ≤ M ≤ 200,000), N번 노드가 가리키는 노드의 번호 V(2 ≤ V ≤ N)가 공백으로 구분되어 주어진다. 둘째 줄에 N개의 정수 C1, C2, …, CN이 공백 www.acmicpc.net 순회하는 공식을 찾는 수학문제였습니다. 풀이방법 1. 1번노드를 제외한 2번부터 사이클의 첫 번째이므로 v의 값을 입력받은뒤 1을 빼줘야 합니다. 그 외 적절히 입력받습니다. 2. k < n인 경우에는 사이클을 순회하지 않으므로 그대로 k번째 값을 출력합니다. 이외의 경우에는 사이클을 적절히 돌게 됩니다. 사이클에 해당하지 않는 노드의..
(C++) - 백준(BOJ) 17826번 : 나의 학점은? https://www.acmicpc.net/problem/17826 17826번: 나의 학점은? 3학년인 홍익이는 이번 학기 전공필수 과목인 운영체제(OS) 수업을 들었다. 수업을 마치고, 얼마 후 교수님께서 클래스넷을 통해 전 학생의 중간고사, 기말고사, 과제점 점수를 만점 기준 300점으 www.acmicpc.net 단순구현문제였습니다. Code #include using namespace std; int score[50]; int hongik; string getDegree(int rank){ if(rank
(C++) - 백준(BOJ) 21739번 : 펭귄 네비게이터 https://www.acmicpc.net/problem/21739 21739번: 펭귄 네비게이터 펭귄은 현재 ($1$, $1$)에 있다. 펭귄은 집까지 가고 싶다. 펭귄의 집은 ($2$, $N$)이다. 하지만 누군가에 의해 얼음길이 다 깨져 집에 갈 수 없게 되었다. 현진이는 펭귄들을 위해 얼음길을 만들어줄 www.acmicpc.net 카탈란 수열의 값을 구하는 문제였습니다. 접근법이 너무 어려워 아래 해설을 참조하게 되었습니다. 응용하기 너무 어렵네요 ㅠㅠ https://www.acmicpc.net/board/view/68251 글 읽기 - 제1회 숙명여자대학교 교내 알고리즘 경진대회 (SMUPC) 종료 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net Code #include usi..
(C++) - 백준(BOJ) 21738번 : 얼음깨기 펭귄 https://www.acmicpc.net/problem/21738 21738번: 얼음깨기 펭귄 첫째 줄에 얼음 블록의 개수 $N$($ 3 \leq N \leq 328\,000$)과 지지대의 역할을 하게 되는 얼음의 개수 $S$($ 2 \leq S \leq N-1$), 펭귄이 위치한 얼음 블록의 번호 $P$($ S \lt P \leq N$)가 주어진다. 지지대의 역 www.acmicpc.net dijkstra로 해결한 문제였습니다. 풀이방법 1. 간선을 인접리스트 형태로 저장합니다. 2. 펭귄 위치에서 i번째 얼음 볼록으로 가는 최단거리를 모두 저장합니다. 거리가 모두 1이기 때문에 이것이 곧 깰 수 있는 얼음의 개수가 됩니다. 즉, i번 얼음 블록을 깬다면 연쇄적으로 펭귄과의 최단거리만큼의 얼음이 깨진..

티스토리툴바