에메스의 숲

문제 내용 https://programmers.co.kr/learn/courses/30/lessons/72412 문제의 유형 및 풀이 방법 효율성 테스트도 있어, map 자료구조와 이분 탐색(Binary search)을 활용해야 하는 문제이다. 먼저 info 배열의 각 원소로부터 만들 수있는 모든 경우의 infoString을 key로 한 map을 만든다. key의 value는 점수를 저장할 벡터이다. 이렇게 map에다가 모든 경우의 infoString 및 score를 넣게되면, java - - pizza 150 같은 query가 들어와도 map에서 이를 찾아서 결과를 구할 수 있다. // info로부터 만들 수 있는 모든 경우의 infoString을 // map{infoString: vec{score1,..

문제 내용 https://programmers.co.kr/learn/courses/30/lessons/77485 문제의 유형 및 풀이 방법 단순 구현 문제이다. 먼저 query에 해당하는 직사각형 범위 중에서 테두리 칸인지 확인한다. bool IsBorder(int x, int y, const vector& query) { int x1 = query[IDX_X1]; int y1 = query[IDX_Y1]; int x2 = query[IDX_X2]; int y2 = query[IDX_Y2]; if (x1 == x || x2 == x || y1 == y || y2 == y) { return true; } else { return false; } } 테두리칸이라면 시계 방향으로 한 칸 회전시키고, 회전시키면..

문제 내용 https://programmers.co.kr/learn/courses/30/lessons/92335 k진수에서 소수 개수 구하기 문제의 유형 및 풀이 방법 단순 구현 문제이다. 먼저 10진수 n을 k진수 문자열로 변환한다. 아래는 k진수로의 변환 코드이다. string ConvertDecimalToBaseK(int num, int k) { int share = 0; int remainder = 0; int i = 0; string stringConverted = ""; while (num >= k) { share = num / k; remainder = num % k; stringConverted.insert(0, to_string(remainder)); num = share; } strin..

14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 백트래킹 문제이다. 첫 풀이에서는, 연산자들의 남은 사용 횟수를 dict로 만들어서 함수의 인자로 copy하여 넘겨주었다. 정답은 맞았지만 상위 등수의 소스코드와 비교해보니 실행시간이 약 2.5배정도 차이가 났다... 이 문제에서 배운 것들 copy() 사용을 지양하자. *args를 이용한 함수로의 매개변수 전달법 코드를 수정할 때, 복붙한 후 제대로 수정했는지 확인하자. 대충 확인해서 틀리면 시간이 많이 잡..

3460번: 이진수 양의 정수 n이 주어졌을 때, 이를 이진수로 나타냈을 때 1의 위치를 모두 찾는 프로그램을 작성하시오. 최하위 비트(least significant bit, lsb)의 위치는 0이다. www.acmicpc.net 2진수 문자열을 구하는 문제이다. 파이썬3 소스코드 def solution(): T = int(input()) for _ in range(T): n_bin = bin(int(input()))[2:][::-1] answer = [] # 1의 위치 찾기 for i, b in enumerate(n_bin): if b == "1": answer.append(i) print(*answer) solution()

2501번: 약수 구하기 첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다. www.acmicpc.net 기본적인 약수 구하기 문제이다. 파이썬3 소스코드 def solution(n, k): divisors = [] for i in range(1, (n//2)+1): if n % i == 0: divisors.append(i) divisors.append(n) if len(divisors) < k: print(0) else: print(divisors[k-1]) return 0 n, k = map(int, input().split()) solution(n, k)​