Algorithm & 자료구조

[알고리즘] 모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)

문제 S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하 세요. 아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다. 입력설명 첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다. S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다. bacaAacba abc 풀이 function compareMaps(map1,map2){ // 두 map의 사이즈가 같은지 비교 if(!map1.size === map2.size) return false; // 두 map의 key, value 값이 같은지 확인 for(let [key,val] of map1){ if(!map2.has(key) || ..

[알고리즘] 백준 11723번: 집합 (비트마스크) W_node.js

문제 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다. remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다. check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20) toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20) all: S를 {1..

[알고리즘] 비트마스크 Bit Mask

비트마스크 꺼져있다 = 0, 켜져있다 = 1 로 표현할 수 있는 2진수의 특성을 활용해 자료구조로 활용하는 기법. 비트를 마스킹처리하여 비트 연산을 활용해 2진 비트를 처리하는 작업이다. 장점 1. 수행 시간이 빠르다. 다른 자료구조에 비해 수행 시간이 빠르다. 비트 마스크 연산은 비트Bit 연산으로 O(1)로 동작한다. 2. 간결한 코드 다양한 집합 연산들을 비트연산자 한 줄로 작성할 수 있기 때문에 코드가 간결해진다. 3. 적은 메모리 사용량 2진수의 특성상 하나의 정수로 많은 경우의 수를 표현할 수 있기 때문에 메모리를 효율적으로 활용할 수 있다. 비트연산자 [JavaScript] 비트 연산 Bit Operation 비트연산자 비트(bit)단위, 즉 2진수 단위로 논리연산을 위해 사용하는 연산자 비..

[알고리즘] 순열구하기

문제 10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 풀이 function solution(m, arr){ let answer = ''; const n = arr.length; const visited = new Array(n).fill(0); let tmp = new Array(m).fill(0); function DFS(L){ if(L===m){ answer+=`${tmp}\n`; } else{ for(let i = 0; i < n; i++){ if(visited[i]===0){ visited[i]=1; tmp[L]=arr[i]; DFS(L+1); visited[i]=0; } } } } DFS(0); return answer; } let arr =[3,..

[알고리즘] 백준 9095번: 1, 2, 3 더하기 (완전탐색,재귀) W_node.js

문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력예시 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 3 4 7 10 출력예시 각 테스트 케이스마다,..

[알고리즘] 중복순열 구하기

문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다. 입력 첫 번째 줄에 자연수 N(3

[알고리즘] 최대점수 구하기(DFS)

문제 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) 입력설명 첫 번째 줄에 문제의 개수N(1

[알고리즘] 합이 같은 부분집합(DFS)

문제 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합(Disjoint Set)이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. 입력설명 첫 번째 줄에 자연수 N(1=arr.length){ for(let i = 0; i0)cnt.push(tmp); } else{ visited[n]=1; DFS(n+..

[알고리즘] 프로그래머스 Lv.1 - 모의고사

문제 https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 풀이 function solution(arr) { const supo = [[1, 2, 3, 4, 5],[2, 1, 2, 3, 2, 4, 2, 5],[3, 3, 1, 1, 2, 2, 4, 4, 5, 5]]; let answer = []; let points = [0,0,0]; for(let i = 0; ia+b); } let answers = [1,2,3,..

[알고리즘] 아나그램 (해쉬)

문제 Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다. 예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다. 길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다. 강사님의 풀이 function solution(str1, str2){ let answer='YES'; let hash = new Map(); for(let x of str1){ if(has..