본문 바로가기

알고리즘

 (117)
[백준] 1948 임계경로 문제링크 : www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 출발점 s에서 e까지의 경로 중 가장 긴 길로 이동한 거리와 그 경로의 개수를 출력하는 문제이다. 간선의 방향이 존재하는 그래프이다. 위상 정렬로 출발점 s에서 어떤 x까지의 최장거리를 갱신했다. 어려운 점은 그 경로의 수를 구하는 것인데, 도착점에서 시작해서 시작점까지 가는 경로를 탐색했다. 이 때, x-> y로의 경로를 이용해서 도착점까지 갔는지를 파악하기 위해 dis..
[프로그래머스] 2021 카카오 블라인드 합승택시요금 [JAVA] 문제링크 : programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 문제 해결법은 플로이드워셜로 가능하다는 것은 명확히 알았다. 다만 무한대의 거리를 어..
[백준] 13424 비밀 모임 [JAVA] 문제링크 : www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 플로이드 워셜로 모든 거리정보를 구한 후 모든 거점에 대해서 비용을 모두 구해보고 가장 작은 거리인 거점을 출력한다 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new I..
[프로그래머스] 2021 카카오 블라인드 메뉴리뉴얼 [JAVA] 문제링크 : programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 코스 개수에 해당하는 메뉴 셋트의 가능한 조합을 카운트해서 크거나 같은 순으로 리스트에 저장했다. import java.io.*; import java.util.*; public class kakao_2021_메뉴리뉴얼 { public static HashMap hm; public static String []order; public static int [] cou..
[프로그래머스] 2021 카카오 블라인드 순위검색 [python] 문제 링크 : programmers.co.kr/learn/courses/30/lessons/72412 = query_score: right = mid else: left = mid+1 answer.append(len(scores) - left) return answer
[프로그래머스] 2021 kakao blind 신규 아이디 문제링크 : programmers.co.kr/learn/courses/30/lessons/72410?language=java 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 카카오계정개발팀에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. 네오에게 주어진 첫 업무는 새로 가 programmers.co.kr 문제에서 친절히 1~7단계 하라는 것을 그대로 코드로 옮기면 된다. 정규표현식을 잘 모르고 문자열을 다루지 못해서 문자 하나씩 바꾸어주었다. 문자열의 길이를 보니 시간문제는 없었다고 판단함. 아는 함수를 활용했다. class Solution { public String solution(String new_id) { //1 new_id ..
[백준] 1248 맞춰봐 문제링크 : www.acmicpc.net/problem/1248 1248번: 맞춰봐 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 www.acmicpc.net import java.io.*; import java.util.*; public class Main { public static int N; public static int ans[]; public static boolean visited [][]; public static String query; public static int len; public static char str[][]; publ..
[백준] 2023 신기한 소수 문제링크 : www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 처음에 문제를 보자마자 소수를 미리 구해두는 편이 편하다고 생각했지만 8자리까지 구하려고 하니 에라토스테네스의체로도 불가능할 것으로 생각했다. 메모리 제한은 4MB인 문제였다. 그래서 N자리인 수의 가장 큰 자리수부터 부분자리가 소수인 수들을 찾아갈 생각을 했다. 1부터 9까지의 수들을 넣어보고 소수이면 다음자리에 들어갈 수 있는 수를 다시 넣는 방식을 N자리의 수가 될 때까지 탐색했다...

티스토리툴바