알고리즘,PS

https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr [문제] [풀이] 신고기준 횟수k 를 넘어 신고를 당한사람을 블랙처리하고 그 결과를 신고한 사람에게 배열형태로 알려주는 문제이다. 우선 Map를 사용함으로써 의 형태로 상황을 유지시킨다. 같은사람이 여러번 신고한 경우를 필터링하기위해 key를 신고당한사람, value를 HashSet으로 함으로써 중복을 기본적으로 걸러낸다. HashMap은 기본적으로 데이..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net [문제] [풀이] 주어진 배열과 명령을 가지고 결과값을 출력 해내는 문제이다. n의 합이 70만개 이므로 R 연산이 들어올 때 마다 reverse 연산을 시행하면 시간초과가 발생한다. reverse 연산을 마지막에 출력할 때만 하기위해 R연산이 들어오면 뒤집는 대신 , direction 이라는 방향상태를 나타내는 상태 변수 하나를 정해두고 양 방향에서 접근할 수 있게 list 대신 deque를 사용한다. 이번엔 뭔가 더 객체지향스럽게 풀어내기위해 Arr..

https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr . [문제] [풀이] 낮은 스코빌 지수의 음식 2개를 뽑아서 새로운 음식을 만드는데 스코빌 지수가 K 보다 높을 떄 까지 반복한다. 계속 해서 낮은 수치의 값이 필요하므로 우선순위큐를 사용. 음식을 섞으려면 2개를 뽑아야 하는데 2개가 없다면 -1 를 리턴 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2..

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net [문제] [풀이] 스도쿠 요약 : 가로줄, 세로줄, 부분 정사각형 모두 1~9까지 숫자가 한번씩만 있어야 함. 백트래킹으로 접근해야한다 빈칸에 숫자하나 넣어보고 아니면 되돌아가서 다른숫자선택하고 ... 반복 1. 빈칸은 0으로 하므로 0인 좌표들을 List에 add 2. List를 순회하면서 DFS 시작. 3. 해당 좌표에 1~9 까지 숫자가 들어갈 수 있는지 확인. 4. DFS 의 depth가 ..

https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net [문제] [풀이] 현재 연료상태를 curFuel 이라고 하면 , 이 연료로 어느 주유소까지 갈 수 있는지 검사해야한다. 연료가 많은 순으로 정렬된 우선순위큐를 fuelQ라고 하자. 주유소 거리순으로 정렬한 뒤에 하나씩 뽑아보면서 1. 만약 갈수 있다면 연료큐(fuelQ)에 push 2. 갈수 없다면 2-1. 연료큐가 비어있으면 끝. (연료가 모자라서 갈수 없음..

https://www.acmicpc.net/problem/2152 2152번: 여행 계획 세우기 첫째 줄에 네 정수 N, M, S, T가 주어진다. 다음 M개의 줄에는 각각의 비행로에 대한 정보를 나타내는 서로 다른 두 정수 A, B(1 ≤ A, B ≤ N)가 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 항공 www.acmicpc.net [문제] [풀이] SCC + DP 문제이다. 최대한 많이 여행하기 위해선 왔던곳을 경로만 있다면 몇번이든 돌아다녀서 최종적으로 얼마나 돌아다녔는지를 구해야한다. 1. SCC 생성 SCC를 이루고 있는 도시들을 하나의 큰 Node로 취급하는 SCC를 여러개 만들어준다. 2. SCC 그래프 연결 SCC Node 끼리 그래프를 형성하는데 , 이 때 가중치를 그 SCC안..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net [문제] [풀이] 만약 , 1번과 2번이 같은 팀이 된다면 능력치의 합은 S12+S21 = 5이다. 만약 , 1, 2, 3번이 같은 팀이 된다면 능력치의 합은 S12+S21+S23+S32+S13+S31 이다. 즉 , 완전탐색으로 모든 조합을 맞춰보면서 , 진행한 깊이(depth)가 한 팀(n/2) 만큼 진행했을 때, visit=true 인 팀의 시너지 총합을 A팀 이라 하고 , 이때 visit=false 인 팀의 시너..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net [문제] [풀이] 완전탐색 기초문제이다. 주어진 K 개의 숫자 중 6개만 뽑아서 모든 경우의 수를 만들어주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 import java.util.*; import java.io.*; import..