문제 풀이
[기업 과제] "자음별 갯수 세기" (Javascript)
[기업 과제] "자음별 갯수 세기" (Javascript)
2021.08.14난이도 : 백준 기준 실버(1~3) 개인적으로 문제 자체는 어렵지 않지만 평소 접하지 못했던 한글 초성 분리 알고리즘을 검색해서 공부해야 하기 때문에, 이 부분에서 난이도가 올라가지 않았나 싶습니다. 문제를 해결하는데 도움이 됐던 링크는 하단에 따로 걸어두겠습니다. 저는 이 문제를 map 자료구조를 활용해서 해결했습니다. 초성으로 가능한 모든 자음을 map에 key값으로 넣어주었습니다. 그다음 초성 분리 알고리즘을 적용하여 입력받은 값이 한글인 경우만을 추출하였습니다. 유니코드를 얻는 과정에서 44032를 빼는 이유는 '가'를 나타내는 유니코드가 44032이기 때문입니다. 이 숫자를 상수로 하여 뺀 값을 저장했습니다. (입력 값이 '가' 라면 uni 값은 0입니다.) 초성은 589마다 바뀌는데 배열의 시..
[백준] 14503번 - "로봇 청소기" (Java)
[백준] 14503번 - "로봇 청소기" (Java)
2021.02.28www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 설명 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는..
[백준] 14502번 - "연구소" (Java)
[백준] 14502번 - "연구소" (Java)
2021.02.27www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net - 난이도 : 골5 dfs와 bfs를 공부를 조금 했다면 충분히 풀 수 있는 문제라고 생각합니다. dfs, bfs 둘 다 활용해서 풀 수 있고 dfs만 활용하여 풀 수도 있습니다. 간단하게 먼저 설명하자면, 재귀 호출을 이용하여 map 배열을 탐색하며 벽을 3개 세웁니다. 탐색은 map 배열로 하지만, 바이러스 퍼트리기는 copy 배열로 진행합니다. 벽을 3개 세웠으면, bfs 탐색을 통해 바이러스를 퍼트립니다. 퍼트린 바..
[백준] 15681번 - "트리와 쿼리" (Java)
[백준] 15681번 - "트리와 쿼리" (Java)
2021.02.26www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 난이도 : 골5 트리 연습하기 좋은 문제라고 생각합니다. 트리 만드는 법을 배울 수 있습니다. 그리고 이 문제도 테스트 케이스 문제라서 각 테스트 케이스마다 문제를 해결하고자 하면 시간 초과가 날 수 있습니다. 미리 문제를 다 풀고 테스트 케이스 별로 결과만 출력하는 것을 추천합니다. 이 문제는 힌트가 아주 잘 나와있어 힌트에 나와있는 의사코드(ps..
[백준] 17425번 - "약수의 합" (Java)
[백준] 17425번 - "약수의 합" (Java)
2021.02.25www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net - 난이도 : 골5 약수 개념이 가미된 전형적인 테스트 케이스 문제입니다. 몇 가지 사항만 주의해준다면 충분히 풀 수 있습니다. 시간 복잡도는 해당 자연수의 약수의 합을 저장(fx)하는 코드 NlgN, 이전 약수의 합들을 저장(dp)하는 코드 N, 테스트 케이스(while) 갯수만큼 코드를 진행하는 T, 즉, NlgN + N + T에서 N은 NlgN보다 작..
[백준] 15661번 - "링크와 스타트" (Java)
[백준] 15661번 - "링크와 스타트" (Java)
2021.02.22www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 난이도 : 실버1 백준의 스타트와 링크 문제와 많이 유사합니다. 차이점은 두 팀의 인원수가 딱 절반으로 나눠떨어지는 것이 아닌, 최소 1명 이상만 있으면 팀으로 간주하고 두 팀의 능력치 차이를 구하는 것입니다. 해당 문제의 시간 제한은 2초입니다. 약 2억개의 데이터 안에서 풀 수 있습니다. 문제의 조건에 따른 최악의 시간복잡도는 (4 ≤ N ≤ 20, N은 짝수)에..
[백준] 14889번 - "스타트와 링크" (Java)
[백준] 14889번 - "스타트와 링크" (Java)
2021.02.21www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 난이도 : 실버3 브루트 포스 문제입니다. 주어진 문제의 시간 제한은 2초입니다. 즉 약 2억개의 데이터 안에서 풀 수 있습니다. 문제의 조건에 따른 최악의 시간복잡도는 (4 ≤ N ≤ 20, N은 짝수)에서 한 데이터를 선택할 수있는 경우와 없는 경우 2가지로 N개를 원소를 가진 배열을 탐색하는 것이므로, 2^20 = 1,048,576. 충분히 모든 경우를 탐색해도 풀 수 있는 문제입니다. 문제의 대표적인 조건은 각 팀은 N/2의..
[백준] 1759번 - "암호 만들기" (Java)
[백준] 1759번 - "암호 만들기" (Java)
2021.02.20www.acmicpc.net/problem/1541www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 난이도 : 골드5 조합과 브루트포스 연습용으로 좋은 문제인 것 같습니다. 문제에 주어진 대표적인 조건에 맞춰서 문제를 해결해 나가면 풀 수 있습니다. 1. 알파벳이 암호에서 증가하는 순서. 2. 최소 한 개의 모음, 최소 두 개의 자음. 첫 번째 조건은 Arrays.sort()로 해결하였습니다. 두 번째 조건은 주어진 입력 L길이의 맞게 암호가 구성되어지면 전역 변수..
[백준] 1514번 - "잃어버린 괄호" (Java)
[백준] 1514번 - "잃어버린 괄호" (Java)
2020.09.04www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 백준에서 측정한 난이도는 실버2입니다. 규칙만 찾는 것이 중요한 문제입니다. '-'를 기준으로 문자열을 파싱을 하고 그 안의 있는 수들은 모두 더해주기만 하면 됩니다. 첫 번째 배열인 arr[0]은 무조건 양수 혹은 '+'기호가 포함된 수식이 됩니다. 그 이후에 배열의 값들은 cal() 메서드를 통해서 더해주기만 하면 되지만 '-'를 기준으로 파싱해주었기 때문에 arr[0]의 값에서 전부 빼주어야 합니다...