오뚝이개발자

문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 나의 풀이 단순히 두 배열의 합을 구해 일일히 비교하면서 합이 T가 되는지 구해보는 방식은 O(n^2m^2)만큼의 시간복잡도가 걸려서 통과되지 않는다. 연산시간을 줄여야 하는데 A의 부분합에 대한 dictionary를 만든 뒤 (T-B의부분합)이 A의 부분합 dictionary 내에 있는지 파악해 가짓수에 더해주..

문제 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 나의 풀이 백트래킹을 사용해서 탐색을 해주면 된다. 검사할 항목은 가로, 세로, 3x3 사각형 안에 사용된 숫자들이 무엇인지이다. 이를 c1, c2, c3에 기록해두고 겹치지 않는 숫자 candidate들을 하나씩 넣어보면서 조건에 위배되는지를 살펴보고 위배된다면 백트래킹으로 다시 값들을 복구하고 다음 후보 숫자를 넣어 탐색하면 된다. 코드 # https://www.acmicpc.net..

문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 나의 풀이 그냥 n개의 원소 중 임의의 3개를 뽑아서 합을 구하는 방식으로 하게 되면 시간복잡도가 O(n^3)까지 올라가게 된다. 따라서 투 포인터를 사용해서 O(n^2)으로 풀어야 통과할 수 있다. i를 0~n-2까지 순회하면서 left와 right를 바꿔주어야 한다. 아래 코드는 python으로는 시간초과가 나왔고 pypy로 통과하였다. 서치를 해보니 대부분의 해답들..

문제 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 나의 풀이 전형적인 유니온 파인드(union find) 문제이다. 유니온 파인드 알고리즘은 그래프가 사이클을 갖는지 여부를 판별하는 알고리즘이다. 약간 헷갈렸던 부분이 사이클을 판별하기 위해선 연결하려는 두 노드 x,y가 같은 부모를 갖는지를 먼저 확인하고 unionParent 함수를 call해야 된다는 점이다. 처음에 unionParent를 먼저 실행하고 isSameParent를 실행..

아나콘다(Anaconda)는 AI나 데이터 과학 패키지를 많이 포함하고 있다. 아나콘다를 통해 이들을 일괄적으로 편리하게 설치할 수 있다. 이 글에선 리눅스에 아나콘다를 설치하는 방법을 소개한다. Step #1 : 아나콘다 사이트에 접속해 installer 다운로드 https://www.anaconda.com/products/distribution Anaconda | Anaconda Distribution Anaconda's open-source Distribution is the easiest way to perform Python/R data science and machine learning on a single machine. www.anaconda.com 위 공식 사이트에 접속해서 자신의 OS에..

아나콘다(Anaconda)는 AI나 데이터 과학 패키지를 많이 포함하고 있다. 아나콘다를 통해 이들을 일괄적으로 편리하게 설치할 수 있다. 이 글에선 리눅스에 아나콘다를 설치하는 방법을 소개한다. Step #1 : 아나콘다 사이트에 접속해 installer 다운로드 https://www.anaconda.com/products/distribution Anaconda | Anaconda Distribution Anaconda's open-source Distribution is the easiest way to perform Python/R data science and machine learning on a single machine. www.anaconda.com 위 공식 사이트에 접속해서 자신의 OS에..

문제 https://codingcompetitions.withgoogle.com/kickstart/round/00000000008caa74/0000000000acee89 Kick Start - Google’s Coding Competitions Hone your coding skills with algorithmic puzzles meant for students and those new to coding competitions. Participate in one round or join them all. codingcompetitions.withgoogle.com 나의 풀이 1. 약수를 구하는 함수 findFactors()를 만든다. 2. 팰린드롬인지를 판별하는 isPalindrome() 함수를 만든다..

문제 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 나의 풀이 BFS를 사용하여 풀었다. 걸린 시간 외에도 경우의 수를 카운트해야 하므로 방문 체크를 일반적인 방식으로 하면 안된다. 일반적인 경우처럼 방문한 곳은 다시 가지 않도록 하면 K까지의 경우의 수는 언제나 1이 되기 때문이다. 따라서 visit 체크를 2가지 경우로 나누어주어야 한다.(아래 코드 참고) 코드 # https://www.acmicpc...