[백준/23630/파이썬] 가장 긴 부분 수열 구하기 풀이 (비트마스킹, Python + 수열까지 구하는 코드 포함)
[백준/23630/파이썬] 가장 긴 부분 수열 구하기 풀이(비트마스킹, Python) 1. 문제https://www.acmicpc.net/problem/236302. 문제 풀이 1. 비트마스킹을 이용하여 푸는 문제이다. → 전체 부분 수열 조합을 구해서 보지 않고, 비트별로 공통된 1이 있는 자리의 수들만 뽑는 아이디어로 해결한다 2. AND 연산을 했을 때, 결과가 0이 되지 않도록 하기 위해서는, 선택된 수들의 모든 비트 중 적어도 하나는 공통적으로 1이어야 한다.3. 따라서 각 비트 위치(0~20)에 대해, 해당 비트가 1인 수가 몇 개 있는지를 세기 위해 길이 21짜리 count 배열을 만든다.(예: [0, 0,..., 0], 길이 21) ※ 길이가 21인 이유?N은 1,000,000가 최대이..
2025. 6. 12.
[백준/11723] 집합 비트마스킹 활용 풀이(python, javascript)
[백준/11723] 집합 비트마스킹 풀이(파이썬, 자바스크립트, python, js, javascript) 1. 문제https://www.acmicpc.net/problem/11723add 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, 2,..., 20}으로 바꾼다.empty: S를 공집합으로 바꾼다.2. 문제 풀이이 문제는, 0~20까지 집합이 있..
2025. 6. 12.
[백준/21736/JavaScript] 헌내기는 친구가 필요해 풀이 (dfs, bfs, 자바스크립트, js)
[백준/21736/javascript] 헌내기는 친구가 필요해 풀이( dfs, bfs, 자바스크립트, js) 1. 문제https://www.acmicpc.net/problem/21736 2. 문제 풀이 1. BFS 1. 큐에 시작 지점 위치를 저장한다. (I) 2. 큐가 빌 때까지 BFS를 반복한다. BFS는 ' 이동하게 될 위치를 기준으로' 확인한다. 2.1. 상,하,좌,우 탐색- 주어진 범위 (n,m)를 벗어나면 continue- 'X'이면 벽이므로 continue- 'P'이면 사람이므로 1 추가- 'O'거나 'P'이면 새로운 위치에 있는 값을 찾은 사람 수로 업데이트하고, 큐에 새로운 위치 좌표 추가 (방문처리) 2. DFS1. 시작 지점(I)에서 DFS를 수행한다. DFS는 '이동한 위치..
2025. 6. 5.
[프로그래머스/파이썬] 이중우선순위큐 풀이 (힙, Python, heap, heapq)
[프로그래머스/파이썬] 이중우선순위큐 풀이(힙, Python, heap, heapq, heappop, heappush, remove) 1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/426282. 문제 해결 아이디어 (풀이) 1. 힙을 사용한다. 2. 최소힙과 최대힙 배열을 따로 만들어서 각각 삽입/삭제를 진행한다 2.1. 값 삭제를 할 때,- 최댓값 삭제는 최대힙을 pop 해준 뒤, 최소힙에 해당 최댓값을 remove로 삭제한다.- 최솟값 삭제는 최소힙을 pop 해준 뒤, 최대힙에 해당 최솟값을 remove로 삭제한다.** 이때, remove할때 -최댓값, -최솟값 이렇게 -를 붙여줘야 한다. ** 최대힙은 구현을 위해 임시로 -를 붙이기..
2025. 5. 15.
