1. 문제 코딩테스트 연습 - n + 1 카드게임 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 무작위로 뒤섞인 1부터 n까지 카드가 n장 있고, coin개의 동전을 가지고 있는데 처음에 n/3장을 가지고 시작 각 라운드가 시작할때 카드를 2장 뽑는데 카드 1장당 동전 1개를 소모해서 가지거나 버릴 수 있다 가지고 있는 카드에 적힌 수의 합이 n+1이 되도록 카드 2장을 내고 다음 라운드로 넘어간다. 카드를 내지 못하거나 모든 카드를 뽑아 더 이상 뽑을 수 없으면 게임 종료 게임을 가장 ..
1. 문제 31091번: 거짓말 (acmicpc.net) 31091번: 거짓말 당신 앞에는 $N$명의 사람들이 있다. 각 사람은 자신을 포함하여 몇 명 이상이 거짓말을 하고 있다고 말하거나, 몇 명 이하의 사람이 거짓말을 하고 있다고 말한다. 예를 들어, 각 사람이 다음과 www.acmicpc.net 2. 풀이 K명이 거짓말 한다고 가정하자. K = 0,1,2,3,..,n이다. 각각의 경우에 대하여 실제로 각 사람들의 말과 비교할때 누가 거짓말을 하는지 알 수 있다. 이때, 정말로 거짓말하는 사람 수가 K명으로 일치한다면 그러한 K값은 정답에 포함될 것이다. 예를 들어 2명이 거짓말을 한다고 하면... "1명 이상이 거짓말하고 있다."는 참이다. 실제로 2명이 거짓말하고 있으니까 "1명 이하가 거짓말하고..
1. 문제 31287번: 장난감 강아지 (acmicpc.net) 31287번: 장난감 강아지 U, D, L, R로 이루어진 길이 $N$의 문자열 $S$가 주어진다. 문자열 $S$를 $K$번 이어 붙인 문자열을 $T$라고 하자. 장난감 강아지 타카하시는 2차원 좌표평면의 원점에서 시작해서 $T$에 적힌 문자를 하 www.acmicpc.net 2. 풀이 의외로 생각을 요구해서 배울 점이 있는 문제 위,아래,왼쪽,오른쪽으로 강아지가 움직이는데.. 문제는 길이 2000인 문자열 S를 최대 $10^{9}$번 반복시켜서 2000*1000000000번 강아지가 움직일 수 있다 이때 원점에서 움직이는데 다시 원점으로 돌아올 수 있는지 확인해야하는 문제 2000*1000000000번을 1초안에 다 해볼수는 없을 것 근데..
1. 문제 코딩테스트 연습 - 도넛과 막대 그래프 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 핵심은 눈치 잘 챘는데.. 시간의 압박에 못이겨서 그런건지 시간초과에서 못벗어났다.. 다시 풀어보니까 시간복잡도를 생각해서 기본에 충실하게 DFS 그래프 탐색을 구현한다면 생각보다 쉽게 풀 수 있더라고 평면에 도넛, 막대, 8자모양 그래프가 여러개 있는데.. 이 그래프와 무관한 하나의 정점을 생성하고 이 정점과 각 그래프의 임의의 정점 중 하나에 연결시켰다 무관한 하나의 정점 번호와 도넛, 막..
1. 모든 원소 쌍의 XOR 합 $A_{0}, A_{1}, ... , A_{n-1}$에 대하여 $\sum_{i=0}^{i=n-1} \sum_{j=i+1}^{j=n-1} A_{i} \oplus A_{j}$을 구하는 문제 단순하게 풀면 $O(N^{2})$이지만 조금 더 생각해본다면 $O(N)$에 가깝게 해결할 수 있다. 결국 구하고자 하는 값은 $V = A_{i} \oplus A_{j}$라고 할 때, 이 V들의 합이다. 그런데 V를 2진수로 나타낸다면.. $$V = a_{k}2^{k} + a_{k-1}2^{k-1} + ... + a_{1}*2 + a_{0}$$로 나타낼 수 있다. 여기서 $a_{i} = 0$이거나 $a_{i} = 1$이다. 만약 모든 $V = A_{i} \oplus A_{j}$에 대하여 최대..
1. 연속하는 부분열에 대한 XOR n개의 음이 아닌 정수 $A_{1}, A_{2}, ... , A_{n}$에 대하여 L번부터 R번까지의 XOR $A_{L} \oplus A_{L+1} \oplus ... A_{R}$의 값은? 만약 $V_{0} = 0, V_{i} = A_{1} \oplus A_{2} \oplus ... \oplus A_{i}$라고 하자. $V_{L-1} = A_{1} \oplus A_{2} \oplus A_{3} .... \oplus A_{L-1}$이다. 그러면, $0 \oplus x = x, x \oplus x = 0$이므로.. 0을 xor해도 값이 달라지지 않는다. $$A_{L} \oplus A_{L+1} \oplus ... A_{R} = 0 \oplus (A_{L} \oplus A_..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
