개발 창고(주인장: 파뱁)

https://www.acmicpc.net/problem/5692 5692번: 팩토리얼 진법 상근이는 보통 사람들이 사는 것과는 조금 다른 삶을 사는 사람이다. 상근이는 이런 사람들의 시선이 부담스럽기 때문에, 자신만의 숫자를 개발하기로 했다. 바로 그 이름은 팩토리얼 진법이다. www.acmicpc.net 팩토리얼 진법에서는 i번 자리의 값을 ai×i!로 계산한다. 즉, 팩토리얼 진법에서 719는 10진법에서 53과 같다. 그 이유는 7×3! + 1×2! + 9×1! = 53이기 때문이다. 팩토리얼 진법으로 작성한 숫자가 주어졌을 때, 10진법으로 읽은 값을 리턴하면 되는 문제이다. 입출력의 예는 다음과 같다. 예제 입력 1 719 1 15 110 102 0 예제 출력 1 53 1 7 8 8 n값이 주..

https://programmers.co.kr/learn/courses/30/lessons/17681 코딩테스트 연습 - [1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다 programmers.co.kr 2개의 비밀지도가 주어지고, 그 두개의 각 칸에 하나의 #(벽)이 있으면 그 곳은 최종적으로 벽이다. 비밀지도는 10진수로 주어지는 데, 이를 2진수로 변환해서 0이면 " "(공백), 1이면 "#"로 간주한다. 입출력의 예는 다음과 같다. 매개변수 값 n 5 arr1 [9, 20, 28, 18, 11] arr2 [30, 1, 21, 17, 28] 출력 [..

진법 변환은 10진법, 2진법 등의 수를 다른 진법의 수를 바꾸는 것을 의미한다. 우리는 일반적으로 10진법을 사용하고, 컴퓨터는 0과 1로 이루어진 2진법을 이용한다. 이것을 변환하는 것도 진법변환이라고 부른다. 기본적으로 진법을 변환할 때는 나눗셈연산과 곱셈연산을 이용한다. 예를 들어 2진수인 111을 10진수로 변환할 때는 1*2^2 + 1*2^1 + 1*2^0 = 7 이 되고, 반대로 10진수인 7을 2진수로 변환할 때는 7//2, (7/2)//2, 7/2/2 => 111 이 된다. 파이썬 기준으로 n진수에서 10진수로 변환할때는 int()를 사용하면 된다. int(string, 진법) 이런 형식으로 사용하면 된다. string에는 변환하고자 하는 n진수 수를 문자열 형태로 넣으면 되고, 그 뒤에..

탐색에 대해 이해하려면 트리 구조를 먼저 살펴보는 것이 좋다. 트리(tree)는 나무가 가지치는 것처럼 생긴 "그래프"의 일종이다. 방향성(보통 위에서 아래)이 있는 비순환 그래프라고도 말하며, 루트 노드(최상위 노드), 부모-자식간의 노드 등이 존재한다. 여기서 말하는 노드는 정점이라고도 말하는데 특정 장소를 생각하면 된다. 이런 노드를 연결하는 것을 엣지(간선)이라 부르는데, 장소를 잇는 도로라고 생각하면 쉽다. 보통 트리는 다음과 같이 생긴 것을 의미한다. 이런 트리도 여러가지 조건 등을 붙이면서 특이한 종류의 트리를 만들 수 있는데, 우선 이 포스트에서는 그 것이 중점이 아니므로 깊게 다루지는 않을 것이다. (언젠가 다른 게시물에서 다룰 예정이다.) DFS(Depth First Search - 깊..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 컴퓨터의 연결정보와 컴퓨터가 몇 개인지에 대한 정보가 주어진다. 이때 1번 컴퓨터가 웜 바이러스에 감염되었다고 하자. 바이러스가 걸린 컴퓨터와 연결된 모든 컴퓨터가 웜 바이러스에 감염된다고 할때, 웜 바이러스에 걸린 컴퓨터가 총 몇 대인지를 반환하면 되는 문제이다. 입출력의 예는 다음과 같다. 예제 입력 1 7 6 1 2 2 3 1 5 5 2 5 6 4 7 예제 출력 1 4 DFS 또는 BFS로 해결하..

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 음이 아닌 정수들이 배열로 나오고, 이 정수 들의 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들 수 있는 방법의 수를 구하면된다. 입출력의 예는 다음과 같다. numbers target return [1, 1, 1, 1, 1] 3 5 [4, 1, 2, 1] 4 2 우선 계속 더하고 빼면서 타겟과 같아지는 지 비교할 변수를 선언..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제이다. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 입출력의 예는 다음과 같다. 예제 입력 1 4 5 1 1 2 1 3 1 4 2 4 3 4 예제 출력 1 1 2 4 3 1 2 3 4 예제 입력 2 ..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 문제이다. 입출력의 예는 다음과 같다. 예제 입력 1 복사 10 6 3 2 10 10 10 -10 -10 7 3 8 10 9 -5 2 3 4 5 -10 예제 출력 1 복사 3 0 0..

https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 한자리 숫자가 적힌 종이 조각을 붙여 몇 개의 소수를 만들 수 있는지 찾는 문제이다. 0부터 9까지의 숫자가 적힌 조각이 있으며, 숫자는 중복 될 수 있다. 11과 011은 같은 숫자 취급을 한다는 것을 유의하면서 문제를 해결하면 된다. 입출력의 예는 다음과 같다. numbers return "17" 3 "011" 2 우선 소수를 판별하는 함수를 ..

완전 탐색(brute force)은 말 그대로 가능란 모든 곳을 탐색한다는 의미이다. 이해를 돕기 위해 예시를 들자면, 10개의 안이 보이지 않는 상자가 있고, 그중 일부의 상자에는 사과가 있다. 상자가 안이 보이지 않기 때문에, 총 몇개의 사과가 있는지 확인하기 위해서는 10개의 상자를 모두 열어봐야 한다. 이런 종류의 탐색을 완전 탐색이라 부른다. 완전 탐색은 결과 값이 가장 확실하지만, 모든 경우의 수를 다 확인해야 하기 떄문에 시간이 가장 오래 걸리는 탐색 방법이다. 예시 문제로는 다음과 같은 문제들이 있다. https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 ..