본문 바로가기

PS

 (77)
[BOJ]12904번 : A와 B https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문제 파악 문자열 S => T로 바꿀 수 있는지 판단하는 문제이다. 브루트 포스 하게 S => T로 2가지 연산을 적용하면서 바꿔 갈 수 있지만 역으로 T=> S로 찾는 방법으로 문제를 해결하였다. 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRe..
[Programmers] 위클리 챌린지 - 1주차 (부족한 금액 계산기) https://programmers.co.kr/learn/courses/30/lessons/82612 코딩테스트 연습 - 1주차 새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이 programmers.co.kr 문제 파악 N번째 이용한다면 원래 이용료의 N배를 받기로 한다는 문구를 보고 등차수열의 합을 생각했고, 아래 예시 (3+6+9+12)를 보고 확신하였다. 등차수열의 합을 구하는 공식은 Sn = n * {2*a + (n-1)*d} / 2 이므로 문제에서는 n(횟수) = count a(초항) = price d(공차) = price로 대입하여 풀면 된다. ..
[BOJ]4358번 : 생태학 https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제 파악 EOF 가 입력되기 전까지 나무 종을 입력받아서 전체 입력 개수에서 해당 종이 차지하는 비율을 소수점 넷째 자리까지 반올림하여 출력하면 된다. 다른 분의 소스를 보면 Trie를 만들어서 사용 하신 분이 계신데 나는 (Key, Value) + Sort의 자료구조를 생각했고 TreeSet으로 해결하였다. 더보기 import java.io.*; import java.util.Tre..
[BOJ]17219번 : 비밀번호 찾기 https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 문제의 의도는 다음과 같다. 사이트마다 저장해둔 비밀번호가 있고 , 비밀번호를 찾으려는 사이트 주소가 한 줄에 하나씩 입력됐을 때, 해당 사이트의 비밀번호를 출력한다. => 자료구조 HashMap을 사용하여 해결 하였다. 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..
[BOJ] 15829번 : Hashing https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 문제 파악 1. 문자열의 길이가 주어지고 해당 길이를 만족하는 문자열이 주어진다. 2. 문제 설명에 나와있듯이 r의 값은 26보다 큰 소수인 31, M의 값은 1234567891로 정해져 있다. 3. 인덱스 위치 0부터 L-1까지 차수를 증가시키면서 ((해당 인덱스의 문자) - 'a' +1) * (31)^(인덱스) 값을 M으로 나눈 나머지를 구한다. JAVA에는 BigInteger class가 ..
[Programmers] LV2 - 소수 찾기 https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문제 파악 주어진 숫자 문자열을 가지고 소수를 몇 개 만들 수 있는지 구하는 문제이다. 순열 + 소수 찾기 문제인 것인데 1. 소수 찾는 방법은 에라토스테네스의 체로 최대 범위 10,000,000까지의 소수를 미리 구했다. ( 10,000,000 까지 구한 이유 number의 최대길이는 7 , 범위는 0~9로만 이루어져 있기 때문에 최대 9,999..
[Programmers] LV2 - 가장 큰 정사각형 찾기 https://programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 알고리즘 분류 : Dynamic Programming 문제 파악 주어진 배열에서 1로만 이루어진 가장 큰 정사각형을 찾아서 그 정사각형의 넓이를 반환하면 되는 문제이다. 문제 해결 과정에서 처음은 Brute force 하게 풀어보았고 두 번째로 DP로 문제를 해결하였다. 1. Brute Force ( 정확성 All pass , 효율성 All fail) 더보기 class Solution { public int solution(int [][]board) {..
[Programmers] LV2 - 배달 https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 문제 파악 문제의 그림에서 주어졌듯이, 그래프로써 문제를 풀어나가야 한다는 것을 유추할 수 있다. 또한, 문제를 읽다 보면 "각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다."라는 구문이 있다. 그래서 처음에는 "무방향 + 그래프" => 플로이드-와샬 알고리즘을 선..

티스토리툴바