본문 바로가기

acmicpc28

[Java] 백준 1644번 소수의 연속합 952hi의 접근방법 1. 문제접근 1)2이상 N이하 소수를 구해야 합을 구할 수 있겠다. 소수를 구하려면 에라토스테네스의 체를 사용해야겠다고 생각이 바로 들었다. 에라토스테네스의 체를 간단하게 설명하자면 2부터 N의 제곱근까지 범위에서 체크하지않은 수가 들어오면 소수로 판단하고 소수의 배수 전부를 체크배열에서 체크해 다음 소수판단에서 삭제하는 알고리즘이다 시간복잡도가 O(N/2)으로 굉장히 빠르다. 2)구한 소수를 연속으로 합쳐 주어진 N을 만들 수 있는지 판단해야겠다. 구한 소수 체크배열을 통해 체크안된 값은 소수이므로 리스트로 구현해 N이 굉장히 클때 탐색시간을 줄여야겠다고 생각했고 슬라이딩윈도우방식으로 매번 소수의 합을 구하고 N보다 작으면 윈도우 크기를 크게만들고 N보다 커지면 중지시켰다. 2. 느낀점 처음에 목표값.. 2022. 6. 13.
[Java] 백준 1765번 닭싸움 팀 정하기 문제 952hi의 접근방법 https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 1. 문제접근 내 친구는 친구다 , 원수의 원수는 친구다 라는 표현을 보고 그룹을 나눈다라는 느낌을 받았고 서로소개념인 유니온 파인드 개념을 사용해야겠다고 생각이 들었다. 입력받을때 친구는 바로 유니온 해주고 각 인덱스별 원수가 2명이상있다는것은 그룹으로 처리해줘야 한다는 말이기때문에 원수의 수를 세주고 2이상이면 그 원수를 유니온 해주는 방식으로 풀었다. 위 그림은 예제 입력 1을 바탕으로 배열을 표현한 것 입니다. 각 원소가 뜻하는 바는 0은 관계없음, 1은 친구, .. 2022. 5. 20.
[Java] 백준 11505번 구간 곱 구하기 문제 952hi의 접근방법 https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 1. 문제접근 구간 합이나 곱은 기존 for문 방식으로 더하거나 곱하면 만약 1~n까지의 합을 구해야 한다면 시간이 O(n) 소요된다. 하지만 이문제같은경우 100만개의 원소를 업데이트와 값갱신까지 계속 해서 한다면 더욱 많은 시간이 소요되기 때문에 세그먼트 트리 문제라고 확신을 가지고 문제를 풀게 되었습니다. 세그먼트 트리의 개념을 .. 2022. 5. 19.
[Java] 백준 2096번 내려가기 문제 952hi의 접근방법 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. 접근방법 문제를 읽자마자 백준에서 RGB거리라는 문제가 생각이 났다. 크게 다를게 없어서 바로 dp 다이나믹 프로그래밍 알고리즘을 사용해서 문제를 풀었다. 간단하게 1번열은 직전 1,2 열 2번열은 직전 1,2,3열 3번열은 직전 2,3열의 영향이 다음으로 합쳐지는 방식이기 때문에 dp를 사용했고 3차원배열을 사용해 최소 최대를 구해줬다. 2. 느낀점 다 풀고 3차원배열안쓰면 더 빠를거 같은 느낌이 들긴했.. 2022. 5. 12.
[Java] 백준 1194번 달이 차오른다, 가자. 문제 952hi의 접근방법 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 1. 접근방법 길 찾기 문제는 bfs라는 공식을 매번 기억하고 있었는데 왠지 dfs로 재귀를 타고 싶었다. dfs나 bfs 문제 둘다 중복방문 처리가 핵심이라고 생각했다. 처음 문제를 읽고 알파벳 a~z 모두 등장한다고 생각해서 알파뱃 개수인 26개 배열과 키의 개수를 가지고 재귀를 돌리면서 매번 4방탐색을 해준다면 가뿐하다고 생각했다. 그런데 시간초과를 발생했다. .. 2022. 5. 12.
[Java] 백준 9935번 문자열 폭발 952hi의 접근방법 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 1. 접근방법 문자열 비교 방식처럼 투포인터를 두고 체크하면서 진행하면 쉽게 풀수 있겠다라고 생각하고 배열로 접근을 했습니다. 근데 삭제처리를 했을때 남아있는 문자열이 있을때 인덱스 관리가 쉽지가 않아서 스택으로 방향을 바꿔서 생각했습니다. 스택을 통해서 구현을 하면 무조건 pop으로만 접근가능하다고 생각하고 접근했는데 스택 함수 쓰면서 get이라는 함수가 있어서 사용해보니 원하는 .. 2022. 5. 6.
[Java] 백준 13168 내일로 여행 952hi의 접근방법 https://www.acmicpc.net/problem/13168 13168번: 내일로 여행 첫 번째 줄에는 한국에 있는 도시의 수 N(1 ≤ N ≤ 100)과 1인당 내일로 티켓의 가격 R(1 ≤ R ≤ 1,000,000)이 주어집니다. 두 번째 줄에는 N개의 도시의 이름이 주어집니다. 도시의 이름은 알파벳 대소 www.acmicpc.net 1. 접근방법 모든 경우의수를 돌면서 값을 구하는 알고리즘인 플로이드워샬을 사용해야겠다고 가장먼저 생각함 다익스트라로 사용해줄 수 있을것 같은데 모든 도시를 전부 한번씩 돌려주면 더 손해라고 생각해서 플로이드 워샬을 사용하기로 생각했음. 문자열 -> 해쉬맵을 통해서 지역에 맞는 인덱스를 만들어서 3중배열의 인덱스로 사용해야겠다고 생각이듬 교통수단 문자열을 받아서 .. 2022. 4. 28.
[Java] 백준 1520 내리막 길 952hi의 접근방법 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 접근방법 보자마자 그저그런 최단거리 BFS 문제라고 판단하고 바로 큐에 넣어서 최단거리를 구해줬다. 예제 입출력 또한 잘나오지만 시간초과가 맞왜틀 발생한다. 단순하게 50*50*4 = 100,000 이라고 생각했지만 약 4의50약 2^100 => 엄청나게 큰수가 나와서 터지는 게 당연했다. 이 문제는 스스로 풀었다기 보다는 여러 정보를 조합해 스스로 풀어봤다. 메모이제이션과 DFS를 활용해 문제를.. 2022. 4. 21.
[Java] 백준 1414 불우이웃돕기 952hi의 접근방법 https://www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 1. 접근방법 처음 설명을 읽을때 이해가안돼서 이해안된상태로 시작하는게 아닌 충분히 이해가 될때까지 문제만 읽었다. 문제를 읽으면서 가장 최소 랜선의 길이를 구하고 각 컴퓨터가 모두 연결을 시켜야 한다는 점에서 MST 최소신장트리 알고리즘이 생각이 났다. 결론적으로는 크루스칼과 프림 둘중 하나를 선택해서 구현해야했다. 나는 크루스칼을 선택해서 사용했는데 프림은 간선이 많을때 이득이라고 생각했.. 2022. 4. 21.
[Java] 백준 12865 평범한 배낭 952hi의 접근방법 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 접근방법 배열을 여러개 사용하고 싶지 않다는 생각이 들어서 하나로 해결할 수 있는 방법을 고민했고 초기 1차원 배열을 무게만큼 생성하고 1~N개 모두 0으로 초기화한후 물건 1~M까지 차례로 끝 인덱스 부터 접근해 넣었을때 가치와 넣고 남은 무게의 가치 즉 직전 회전의 가치를 활용해 계산함 ex) 물건2 무게 4 총 배낭 무게.. 2022. 4. 18.
[Java] 백준 16463 13일의 금요일 https://www.acmicpc.net/problem/16463 1. 접근방법 윤년인지 아닌지에 따라 365일이냐 366일 이냐가 달라지므로 하루가 달라지면 3월부터 생각한 요일이 나오지 않을 것이다. 가장중요한부분 이라고 생각했다. 그래서 따로 함수를 둬서 12월이 지나고 새해가 오면 그해를 체크해주는 함수를 구현해 월별 마지막날을 배열로 관리해줘야겠다고 생각했다. 그 후로는 초기 1월1일 화요일 이므로 최초 금요일은 1월 4일로 4일에 7씩 더해서 계속 금요일만 만나서 13일인지 아닌지 체크해 주는 방법을 사용했다. 한달도 괜찮을거같은데 조금 복잡해서 주단위로 해야겠다 생각했다. 2.느낀점 크게 어렵지는 않았지만 더 효율적으로 짠다면 수식을 사용하면 될거 같다는 생각이 들었다. 3. 코드 impo.. 2022. 4. 18.
[Java] 백준 4195번 친구 네트워크 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 문제바로가기 1. 접근방법 친구 네트워크라는 단어 친구 사이가 된다 이런 단어의 느낌에서 서로소집합의 느낌이 많이 났다. 그래서 유니온 파인드 사용해서 1번 2번 친구를 연결 후 부모를 갱신 부모가 같은 개수를 세서 값을 출력하하면 되겠다. -> 정상적으로 값은 출력이 가능했다. 하지만 시간초과 -> 시간을 잡아먹은부분은 갱신을 해주고 부모 배열을 1~n까지 모두 확인하기 때문이라 생각.. 2022. 4. 14.

티스토리툴바