본문 바로가기

전체보기

 (126)
[백준] 1629번: 곱셈 - JAVA 🔗 문제 링크 BOJ 1629번: 곱셈 📝 풀이 과정 주어진 숫자를 제곱해야 하는데 단순하게 반복문으로 제곱수를 구하게 되면 시간복잡도는 B의 크기만큼 소요되게 되고 B의 최대 크기는 $2^{31}-1$로 시간 제한을 초과하게 된다. 따라서 정해진 제곱을 분할하는 방식을 사용해 시간을 줄여야 한다. $$ A^{10} = A^{5 + 5} = A^5 \times A^5 $$ 먼저 제곱은 위의 식처럼 분할이 가능하다. 따라서 제곱을 순차적으로 하나씩 곱하면서 구하지 않고, $A^5$를 구한 뒤 그 수를 제곱하면 $A^{10}$을 쉽게 구할 수 있는 것이다. 만약 제곱수가 11(홀수)이라면 $A^5$(절반)를 제곱한 뒤 그 수에 $A$를 곱하면 되기 때문에 빠르게 답을 구할 수 있게 된다! static lon..
[백준] 18119번: 단어 암기 - JAVA 🔗 문제 링크 BOJ 18119번: 단어 암기 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 📝 풀이 과정 단어가 알고있는 알파벳으로 구성되어 있을 때 아는 단어라고 한다. 따라서 단어를 알파벳을 기준으로 보고 단어에 포함되는 알파벳을 비트마스킹을 통해 처리하려고 하였고, 현재 알고 있는 알파벳도 비트연산을 통해 계속 누적하였다. 알파벳은 총 26자리로 이루어져있으며 처음에는 모든 알파벳을 알고있기 때문에 (1 = word) cnt++; 이후, for문으로 단어마다 기억하고 있는 알파벳과 &연산을 통해 비..
[백준] 15663번: N과 M (9) - JAVA 🔗 문제 링크 BOJ 15663번: N과 M (9) 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 📝 풀이 과정 permutation을 활용해 수열을 구하는 문제이다. 사전순으로 출력하기 위해 Arrays.sort를 활용해 입력이 들어온 숫자들을 오름차순 정렬해주었고, visit배열을 통해 같은 숫자가 수열에 포함되지 않도록 했다. input 3 1 4 4 2 -------- output 2 4 이전의 N과 M 문제들과 다른 점은 중복되는 수열이 출력되면 안된다는 점이다. 모든 수열을 구하게 되면 2,4,4..
[백준] 1800번: 인터넷 설치 - JAVA 🔗 문제 링크 BOJ 1800번: 인터넷 설치 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 📝 풀이 과정 처음에는 방문할 때마다 가격을 저장하고 해당 가격순으로 정렬하여 K개만큼 제외하는 등의 작업이 굉장히 오래걸렸기 때문에 당연하게도 시간초과가 발생했다... 계속 고민하며 아이디어가 떠오르지 않아 고생하던 중 한가지 힌트를 보게 되었다. 최소값을 미리 정한 뒤 탐색을 하라는 것이었다. 최소값을 x로 두고 가격이 x이하인 선은 그냥 연결을 하고, x이상인 선은 K개..
RAID와 RAID Level RAID Redundant Array of Inexpensive/Independent Disk, 복수 배열 독립 디스크 저장장치를 여러개 묶어 고용량, 고성능 저장장치와 같은 효과를 얻기 위해 개발된 기법 과거에는 저렴한 디스크를 모아 고성능의 디스크처럼 사용하자는 생각이었지만 현재는 경제적인 이유보다 높은 신뢰성과 높은 데이터 전송율에 사용 장점 중복을 통한 신뢰성 향상 중복을 허용(미러링, mirroring)해 디스크 고장이 발생했을 경우 분실된 정보를 재구축하기 위해 사용해 디스크 고장이 발생하더라도 데이터가 분실되지 않음 병렬성을 통한 성능 향상 읽기 요청을 두 디스크 중 하나에서 처리할 수 있기 때문에 읽기 요청의 처리율은 2배가 된다 💡 미러링(mirroring) 하나의 논리 디스크는 두 개의..
[CS 정리] 운영체제 (3) 파일 시스템 파일 보조 저장장치에 기록된 관련 정보의 정명된 집합, 사용자 관점에서 논리적 보조 저장장치의 가장 작은 할당 단위 접근 방법 순차 접근(Sequential Access) 파일의 정보가 레코드 순서대로 차례대로 처리되는 것 가장 간단한 접근방법 읽기(read next) : 파일의 다음 부분을 차례대로 읽어나간다 쓰기(write next) : 파일의 끝에 추가, 새로운 파일의 끝으로 파일 포인터가 이동 직접 접근(Direct Access), 상대 접근 직접접근을 위해 파일은 고정 길이의 논리 레코드로 구성되고 특별한 순서없이 빠르게 레코드를 읽고 쓸 수 있다 디스크가 무작위 파일 블록에 임의적 접근을 허용하기 때문에 파일의 디스크 모델에 기반 14→53→7 등의 접근이 가능 읽거나 탐색할 블록..
[프로그래머스] 방금그곡 / 2018 KAKAO BLIND RECRUITMENT(3차) - JAVA 🔗 문제 링크 [프로그래머스] 방금그곡 / 2018 KAKAO BLIND RECRUITMENT(3차) 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 📝 풀이 과정 주어진 멜로디를 포함하는 악보를 가진 음악을 구하는 문제이다. 문제에서 중요한 점은 C와 C#은 다르기 때문에 #이 붙어있는 음을 바꿔주어야 문자열을 찾게 될 때 오류가 없어지게 된다. 주어진 문자열에서 변환음을 모두 바꾸어 반환해주는 changeStr(str) 함수를 만들어 사용하였다. 음악은 재생된 시간만큼 멜로디가 구성되는데, 만..
[프로그래머스] 캐시 / 2018 KAKAO BLIND RECRUITMENT(1차) - JAVA 🔗 문제 링크 [프로그래머스] 캐시 / 2018 KAKAO BLIND RECRUITMENT(1차) 코딩테스트 연습 - [1차] 캐시 3 [Jeju, Pangyo, Seoul, NewYork, LA, Jeju, Pangyo, Seoul, NewYork, LA] 50 3 [Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul, Jeju, Pangyo, Seoul] 21 2 [Jeju, Pangyo, Seoul, NewYork, LA, SanFrancisco, Seoul, Rome, Paris, Jeju, NewYork, Rome] 60 5 [Jeju, Pangyo, S programmers.co.kr 📝 풀이 과정 가장 최근 참조하지 않은 것을 교체하는 LRU 알고리즘을 구현해보는 문제이..

티스토리툴바