본문 바로가기

code

 (114)
std::next_permutation()으로 조합 만들기 주어진 크기 n의 배열 A에서 r개의 원소를 선택하고 싶을 때(nCr), // 오름차순 조합 생성 3C2 예시 (1, 2) (1, 3) (2, 3) bool cbn[n]; fill(cbn, cbn + r, 0); fill(cbn + r, cbn + n, 1); do { for (int e = 0; e < n; ++e) { if (!cbn[e]){ // 선택된 선택지 A[e]에 대한 처리 } } } while (next_permutation(cbn, cbn + n)); // 내림차순 조합 생성 : 3C2 예시 (2, 3) (1, 3) (1, 2) bool cbn[n]; fill(cbn, cbn + n - r, 0); fill(cbn + n - r, cbn + n, 1); do { for (int e = 0..
백준 17140 이차원 배열과 연산 문제 링크: 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 코드: /* 오답-파악 1. r, c는 1부터이므로 -1해주기 */ /* 오답-문법 2. for문의 body가 2줄 이상이면 중괄호 생략 불가! */ /* 오답-설계 3. sz 갱신 시점 잘 잡기 */ /* 오답-파악 4. 0은 연산에 포함시키지 않기 */ /* 5. 마지막에 padding된 연속된 0만 skip, 나머지는 연산에 반영해야 한다. */ /* 6. container 상 아주 큰 값 -> boundary, traverse 방향..
백준 17144 미세먼지 안녕! 문제 링크: 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 왼쪽 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼 www.acmicpc.net 코드: /* 1. -1(공기청정기)일 경우에도 skip해야 */ /* 2. 공기청정기는 따로 copy해야 */ /* 3. loop 초기화에 이전 loop 탈출 조건 보정 필요*/ /..
순열과 조합 - 점층 처리 선택 전 처리 백준 15812 침략자 진아 백준 16949 벽 부수고 이동하기 4 점층 처리(선택지간 독립) => undo 필요(undo가 간편해야) 백준 14500 테트로미노 백준 14889 스타트와 링크 2 ^ 20 * 20 = 20971520 백준 15661 링크와 스타트 스타트와 링크 2 ^ 19 * 20 = 10485760 백준 15683 감시 백준 15686 치킨 배달 SWEA 2112 보호 필름 선택 후 처리(선택지간 의존) 백준 15684 사다리 조작(누적 불가 = 부분 처리 의미 없음) 백준 14502 연구소(선택횟수가 3번 고정, 부분 처리 의미 없음) C(64,3) * 8 * 8 = 2,666,496 백준 17142 연구소3(선택지간 중첩 가능) C(10,r) * 50 * 50 = 6..
백준 17472 다리 만들기 2 문제 링크: 불러오는 중입니다... 코드: /* 1. visited 체크 누락 */ /* 2. boundary */ /* 3. 배열 boundary chk시에는 왠만하면 < 부호 쓰기 */ #include #include #include #include using namespace std; int dn[] = { -1, 0, 1, 0 }; int dm[] = { 0, 1, 0, -1 }; int N, M; vector isl; bool map1[12][12]; int map2[12][12]; int V = 1; int cst[7][7]; set cnct; bool cbn[15], adj[7][7], vst[7]; int v, CST, ans = 50; void DFS1(int n, int m) { map..
백준 17135 캐슬 디펜스 문제 링크: 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 코드: /* 1. back()은 !empty() 조건 하에 사용할 것! */ /* 2. 매 k가 바뀔 때마다 ans 갱신하려면 for(k) body 밖이 아니라 안 맨 끝에서 갱신해야 */ /* 3. 매 k가 바뀔 때마다 초기상태로 바꾸려면 원본과 임시 2개 자료구조 생성해야 */ /* 4. x에 대해 dst_init이 여러번 수행 되기에, memoization하기 */ #include #include #include #include #include using ..
[프로그래머스] 2019 카카오 블라인드(2018 시행) 2번 실패율 문제 링크: 코딩테스트 연습 - 실패율 | 프로그래머스 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 programmers.co.kr 해설 링크: 2019 카카오 신입 공채 1차 코딩 테스트 문제 해설 작년에 이어 올해도 블라인드 전형으로 카카오 개발 신입 공채가 시작되었습니다! 그 첫 번째 관문으..
[프로그래머스] 2019 카카오 블라인드(2018 시행) 1번 오픈채팅방 문제 링크: 코딩테스트 연습 - 오픈채팅방 | 프로그래머스 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. [닉네임]님이 들어왔습니다. 채팅방에서 누군가 나가면 다음 메시지가 출력된다. [닉네임]님이 나갔습니다. 채팅 programmers.co.kr 해설 링크: 2019 카카오 신입 공채 1차 코딩 테스트 문제 해설 작년에 이어 올해도 블라인드 전형으로 카카오 개발 신입 공채가 시작되었습니다! 그 첫 번째 관..

티스토리툴바