전체 글

1253 - 좋🤙다👍https://www.acmicpc.net/problem/1253문제N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 좋다(GOOD)고 함=> N개 수가 주어지면 그 중에서 좋은 수의 개수 몇 개?(수 위치 다르면 값이 같아도 다른 수)입력첫째 줄: 수의 개수 N (1 두 번째 줄: i번째 수 나타내는 A_i가 N개 주어짐 (|A_i| 출력: 좋은 수의 개수 풀이어떤 수 A[k]가 서로 다른 두 수 A[i] + A[j]로 표현되면 좋다-> 두 수 합이 특정 값(target)이 되는 경우 => 투포인터 or 이분탐색 or 해시 수 범위: -10^9 ~ 10^9 => `long[] arr` Two Pointers(투포인터)투포인터는 정렬된 상태에서만 가..

605 - Can Place Flowers풀이앞 / 현재 / 뒤 0 -> 현재 위치에 꽃 심기 가능 => 꽃 심기(`flowerbed[i] = 1`)`i == 0 || flowerbed[i - 1] == 0`: 맨 앞이면 왼쪽 자동 통과 / 아니면 왼쪽 0이어야 함`i == flowerbed.length - 1 || flowerbed[i + 1] == 0`: 맨 끝이면 오른쪽 자동 통과 / 아니면 오른쪽 0이어야 함flowerbed[i] == 0 &&(i == 0 || flowerbed[i - 1] == 0) &&(i == flowerbed.length - 1 || flowerbed[i + 1] == 0))코드class Solution { public boolean canPlaceFlowers(in..

1182 - 부분수열의 합https://www.acmicpc.net/problem/1182문제N개의 정수로 이뤄진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수입력첫째 줄: 정수의 개수 N, 정수 S (1 둘째 줄: N개의 정수 (|주어지는 정수| 출력: 합이 S가 되는 부분수열의 개수 풀이비트`1 -> 부분집합 개수: 2^N개 -> 0 ~ (2^N - 1) `(mask & (1 mask: 부분집합 선택 정보 저장한 숫자 / 비트 하나: 해당 원소 선택했는지 여부ex. mask = 5 = 101 / 1 -> mask & (1 AND 연산 규칙: 두 비트 모두 1일 때만 1-> i번째 비트가 1이면 true = i번째 원소를 포함한다는 의미int cn..

11723 - 집합https://www.acmicpc.net/problem/11723문제비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램- add x: S에 x 추가- remove x: S에서 x 제거- check x: S에 x가 있으면 1/ 없으면 0 출력- toggle x: S에 x가 있으면 x를 제거/ 없으면 0 출력- all: S를 {1, 2, ..., 20}으로 바꿈- empty: S를 공집합으로 바꿈(1 입력첫째 줄: 수행해야 하는 연산의 수 M (1 둘째 줄 ~ M개의 줄: 수행해야 하는 연산출력: check 연산 주어질때마다, 결과 출력풀이숫자 1 ~ 20 저장전등 켜져 있으면 숫자가 집합에 있음 / 꺼져 있으면 집합에 없음ex. {1, 3} -> 전등 상태: 1(3) 0(..

2268 - 수들의 합 7https://www.acmicpc.net/problem/2268문제N개의 수 A[1], A[2], ..., A[N]이 주어졌을 때Sum(i, j) -> A[i] + A[i + 1] + ... + A[j] / Modify(i, k) -> A[i] = k입력첫째 줄: N, 수행한 명령의 개수 M (1 M개 줄: 수행한 순서대로 함수 목록 ㄴ어느 함수 사용했는지(0: Sum 함수/ 1: Modify 함수), 함수의 인자 (i, j) or (i, k)A[1] = A[2] = ... = A[N] = 0Modify인 경우에 1 출력: Sum 함수의 개수만큼 각 줄에 Sum 함수의 리턴값 출력풀이0 a b -> a ~ b 구간 합1 a b -> A[a] = b (값 변경) 펜윅 트리(Fen..

석유 시추https://school.programmers.co.kr/learn/courses/30/lessons/250136풀이덩어리 찾기0: 빈 칸 / 1: 아직 처리 X 석유 / 2부터 덩어리 번호 사용HM에 덩어리 번호와 크기 저장Map HM = new HashMap();int id = 2;for (int i = 0; i BFS(r, c)에서 시작하는 석유 덩어리 크기 계산`land[r][c] = id`: `land`에 `id`(덩어리 번호) 기록public int bfs(int r, int c, int id) { Queue q = new ArrayDeque(); q.offer(new int[]{r, c}); visited[r][c] = true; land[r][c] = id..