본문 바로가기

분류 전체보기

Baekjoon 1543 문서 검색 2019. 6. 2. Link https://www.acmicpc.net/problem/1543 소스결과 1988 KB / 0 ms 언어 C++ 17 출처 Baekjoon 분류 그리디 알고리즘, 문자열 처리, 탐색 설명 영어로만 이루어진 문서가 주어질 때 검색하고 싶은 단어가 중복되지 않게 몇번 등장하는지 알아보자. 문제의 난이도에 비해 정답률이 낮은게 의문이었다. 아마 원인은 String 클래스의 find 함수나 indexOf 함수를 이용하며 생기는 검색 속도 문제일꺼 같다. 이번 문제는 String 클래스의 find와 indexOf 함수를 합쳐놓은(?) 방식으로 풀었다. 알고리즘 1. 총 문자열과, 검색할 문자열을 입력 받는다. 2. 0번 인덱스부터 문자열을 비교한다. 2-1. 현재 탐색하는 문자열의 위치와, 탐색할 문자..
Baekjoon 1946 신입 사원 2019. 6. 2. Link https://www.acmicpc.net/problem/1946 소스결과 2888 KB / 144 ms 언어 C++ 17 출처 Baekjoon, ACM-ICPC 2006 분류 그리디 알고리즘 설명 한 지원자의 서류 심사 성적과, 면접시험 성적중 적어도 다른 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙 하에 지원자를 선발할 때 선발 할 수 있는 최대 인원 수를 구하여라. 되게 간단한 듯 보이면서 많이 틀렸던 문제다. 서류 심사 성적을 기준으로 정렬을 한 뒤, 면접 시험에 대해서 처리 하는 부분이 애매했었다. 결과론적으로 서류 심사 성적이 같다면 면접 시험 성적이 좋은 사람을 위로 놓았다. 또한 서류심사 성적이 낮지만, 면접 시험 성적이 가장 좋은 경우도 존재 할 수 있기 때문에, ..
Baekjoon 2217 로프 2019. 6. 2. Link https://www.acmicpc.net/problem/2217 소스결과 3276 KB / 16 ms 언어 C++ 17 출처 Baekjoon 분류 그리디 알고리즘 설명 k개의 로프 정보가 주어질 때, 로프를 사용하여 들어 올릴 수 있는 최대 중량을 계산하여라. 알고리즘에 있어 크게 생각할 부분은 없었다. 각 로프 입장에서는 자기가 들 수 있는 값보다 큰 값을 들어올리지는 못하기 때문에 자기 자신을 기준으로 자기보다 많이 들어 올릴 수 있는 수 만큼을 곱해주면 그 로프를 이용 했을 때의 최대 중량이 된다. 최대 값만 찾으면 되기에 배열을 이용해도 되지만 이번 문제에서는 힙을 이용했다. 힙은 최대 힙으로 사용하고, 정렬된 값을 넣을 때에는, (자신의 장력) * (남은 로프의 수)의 값으로 넣어준다..
Baekjoon 1931 회의실 배정 2019. 6. 2. 링크 https://www.acmicpc.net/problem/1931 소스결과 2772 KB / 32 ms 언어 C++ 17 출처 Baekjoon 분류 그리디 알고리즘 설명 한개의 회의실과 회의 일정이 주어질 때 회의가 겹치지 않게 최대한 많이 배정 할 수 있는 수를 구하여라. 문제 자체에서 그리디 알고리즘이라는걸 알 수 있는 문제였다. 정렬을 이용하면 쉽게 해결 될 꺼 같은 문제 였는데 감이 잡히지 않아 고생좀 했었다. 종료 시간을 기준으로 정렬을 하되, 종료 시간이 같은 경우 시작시간이 작은 경우로 정렬 하면 된다. 정렬 후 최선의 경우를 선택 하면서 다음에 시작이 가능한 시간만 골라서 이어서 카운팅 해주면 정답이 된다. 알고리즘 1. 종료시간을 기준으로 경우의 수를 정렬한다. 단 종료시간이 같은 ..
Baekjoon 1761 정점들의 거리 2019. 4. 22. Link https://www.acmicpc.net/problem/1761 소스결과 6504 KB / 668 ms 언어 C++ 17 출처 Baekjoon 분류 LCA 설명 가중치가 있는 트리가 주어질 때 두 정점 사이의 가중치의 합을 출력한다. 기존 LCA문제에서 가중치가 추가된 LCA문제. 단지 루트 노드가 지정이 되지 않았기에 어느 노드를 기준으로 깊이를 설정해도 상관은 없다. 가장 일반적이게 1번 노드를 기준으로 깊이를 지정했다. 두 정점이 주어졌을 때 두 정점의 깊이를 맞추는 과정에서도 가중치의 합을 구해야 하는 것을 조심 해야한다. 두 정점의 깊이가 일치해 졌다면 같은 공통 조상까지 찾아가면서 가중치의 합을 구하면 최소 거리가 된다. 알고리즘 1. 간선과 가중치 정보를 입력 받는다. 2. 임의의..
Baekjoon 11437 LCA 2019. 4. 22. Link https://www.acmicpc.net/problem/11437 소스결과 7400 KB / 816 ms 언어 C++ 17 출처 Baekjoon 분류 LCA 설명 1을 루트로 하는 트리가 주어질 때 두 정점의 가장 가까운 공통 조상의 번호를 출력한다. LCA를 처음 공부할 때 개념을 잡기 좋은 문제라고 한다. 다른 블로그를 돌아다니면서 개념을 익힐 때 왜 깊이를 DFS로 설정해 주는지 의문을 가졌었다. 예제를 직접 노트로 옮겨보니 바로바로 이어져서 입력과 동시에 깊이와 부모를 설정해 줬는데 제출을 하니 바로 시간초과에 걸렸었다. TC로 들어오는건 꼭 1이 있는 트리에 이어져서 들어오는게 아니라 나눠져 들어오기 때문에 깊이와 부모 설정에 문제가 생겨 높이를 맞추는 과정에서 무한루프에 빠지게 됬었..
Baekjoon 6118 숨바꼭질 2019. 4. 21. Link https://www.acmicpc.net/problem/6118 소스결과 3724 KB / 16 ms 언어 C++ 17 출처 Baekjoon 분류 BFS, 최단거리 알고리즘 설명 수혀니와 재서기가 숨바꼭질을 할 때 가장 멀리 있는 지점 중 가장 작은 번호와, 거리, 같은 지점의 개수를 출력해주자. 가중치도 없고, 단순히 거리만 있는 문제이기에 크게 생각할 점이 없다. 최대 지점의 수가 2만이기에 인접 행렬을 사용하지 않아야 한다. 최소 거리만 저장하면 되기에 방문체크도 간단하다. BFS이후 거리를 저장해 가장 작은 번호 출력하고, 거리, 지점을 계산한다. 알고리즘 1. n, m, 간선 정보를 입력 받는다. 2. 수혀니가 1번에서 시작하기 때문에 1번을 기준으로 BFS를 시작한다. 2-1. 현재..
Baekjoon 1967 트리의 지름 2019. 4. 21. Link https://www.acmicpc.net/problem/1967 소스결과 2700 KB / 4 ms 언어 C++ 출처 Baekjoon 분류 BFS, 트리 설명 트리의 최대 지름을 출력해주자. 어떤 경우가 트리의 지름이 최대가 되는지를 생각하는 것이 가장 어려운문제. 질문 게시판에서 해답을 얻었던 문제. 루트노드에서 갈 수 있는 최장 거리 노드는 무조건 리프노드가 된다. 그렇다면 최장 거리에 있는 리프노드를 기준으로 가장 멀리 있는 다른 노드를 찾는다면 최장 지름을 얻을 수 있다. 해당 아이디어만 있으면 됬던 문제. 떠올리지 못했던 것이 조금 아쉽다. 알고리즘 1. 노드와 간선 정보를 입력 받는다. 2. 1번 노드(root Node)를 기준으로 가장 멀리있는 노드를 구한다. 3. 구해진 노드를 ..

티스토리툴바