본문 바로가기
반응형

전체 글70

[강의정리] [연결리스트] 실전 알고리즘 0x04 정리 바킹독의 실전 알고리즘 0x04 강의 정리. 연결리스트는 어떤 문제에 쓰일까? - 연결 리스트가 쓰이는 문제는 크게 응용해서 낼만한게 없고 원소들을 돌아다니면서 이동하다가 삭제나 삽입이 필요한 문제들 - 연습문제들 https://jjpearl.tistory.com/52 [백준 - 1406번] 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 jjpearl.tistory.com - 손코딩 문제 1 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법? -> 효율적 = 생각한 풀이의 공간복잡도와 시간복잡도.. 2022. 4. 26.
[백준 - 1158번] 요세푸스 문제 문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 예제 입력 1 복사 7 3 예제 출력 1 복사 풀이 과정 삭제가.. 2022. 4. 26.
[백준 - 5397번] 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오. 강산이는 키보드로 입력한 키는 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표이다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000).. 2022. 4. 26.
[백준 - 1406번] 에디터 문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다. 이 편집기가 지원하는 명령어는 다음과 같다. L 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨) D 커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨) B 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무.. 2022. 4. 26.
[강의정리] [배열] 실전 알고리즘 0x03 정리 바킹독의 [실전 알고리즘] 0x03강 - 배열 정리. -배열의 성질 O(1)에 k번째 원소를 확인/변경 가능 시작 주소에서 k칸 만큼 오른쪽으로 가면 되기 때문. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 다른 자료구조와 다르게 추가적으로 소모되는 메모리의 양이 거의 없다. Cache hit rate가 높음 메모리 상에데이터들이 붙어 있으니까. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 -시간 복잡도 임의의 위치에 있는 원소를 확인/변경 = O(1) 원소를 끝에 추가 = O(1) 마지막 원소를 제거 = O(1) 임의의 위치에 원소를 추가/임의 위치의 원소 제거 = O(N) -배열 전체를 특정값으로 초기화 for문으로 값을 하나하나 다 바꾸는 방식 : 무난 algori.. 2022. 4. 22.
반응형

티스토리툴바