Jamie's CodeSprout

2023-03-19 프로그래머스 위장 파이썬 (해시) 참고: 코딩테스트 연습 - 위장 | 프로그래머스 스쿨 (programmers.co.kr) 무엇? 조합 원소 길이: 1개 ~ 의상의 종류 갯수 어떤 종류의 의상을 입을 것인지 경우의 수를 구하여 카운트 문제 요약: 매일 다른 옷을 입도록 조합 조합의 수를 return 제한사항: 의상의 이름, 의상의 종류로 구성 의상의 수: 1개 이상 30개 이하 중복 없음 문자열의 길이: 1이상 20이하 문자열의 구성: 알파벳 소문자, “_” 최소 하루 한개 이상은 입어야 함 왜? 해시 테이블 연습 어떻게? 내 코드 각각의 옷 종류의 개수를 세어 저장하는 딕셔너리를 생성 조합의 총 수를 계산 각 의상 카테고리에 포함된 의상 갯수 + 1을 모두 곱한 것이 경우의 수에 해..

2023-03-18 Codility L6_NumberOfDiscIntersections 파이썬 참고: NumberOfDiscIntersections coding task - Learn to Code - Codility 무엇? N개의 디스크를 표현하는 배열 A이 주어짐. 서로 겹치는 원 쌍의 개수를 리턴 10000000개가 넘으면 -1 리턴 어떻게? 라인 스위핑 (O(N*log(N)) or O(N)) left edge, right edge 구분 좌표상 위치와, left edge를 기준으로 오름차순 정렬(※ 중요) 정렬한 것들에 대해서 left edge를 만나면(또 다른 원이 시작한다는 뜻): 인터섹트에 액티브 디스크 수만큼 추가 액티브 디스크 += 1 right edge를 만나면(원 하나가 끝났다는 뜻) ..

2023-03-18 코딜리티 L14_MinMaxDivision 파이썬 참고: MinMaxDivision coding task - Learn to Code - Codility 무엇? 배열 A를 K개 이하의 블럭으로 나눔 반드시 1개 이상의 블럭 블럭의 길이는 0일 수도 있음 배열 A의 원소의 크기는 M 이하 (※ 최댓값이 M이라는 뜻이 아님) 블락 총합의 최댓값이 가장 작은 것을 구하기 어떻게? 이진탐색 반복문 사용 배열 나누기 확인 함수 (주어진 sum 값을 최대 sum 값으로 유지하면서 배열을 K개로 쪼갤 수 있는지 확인) A의 원소에 대해서 블럭의 합과 원소를 더한 값이 맞춰야 할 최대 합보다 크다면: 블럭을 쪼갠다 (합을 해당 원소 값으로 리셋) 블럭 개수가 K개를 넘기면: 배열을 나눌 수 없다는 ..

2023-03-17 코딜리티 L1 BinaryGap 파이썬 참고: https://app.codility.com/programmers/lessons/1-iterations/binary_gap/ 무엇? 양의 정수를 이진수로 변환 변환된 이진수에서 1과 1사이에 위치한 0의 최대 길이를 구하는 문제 어떻게? 내 코드 N을 이진수로 변환 (bin() 메소드를 사용하면 문자열로 반환) 이진수 반복문 0 갯수 세기 1을 만날 때만 최대값을 업데이트하기 def solution(N): binary_num = bin(N)[2:] max_gap = 0 temp_gap = 0 for i in binary_num: if i == 0: temp_gap += 1 else: max_gap = max(temp_gap, max_gap..

2023-02-20 백준 2470번 두 용액 파이썬 참고: https://www.acmicpc.net/problem/2470 무엇? 산성 용액 특성값: 1부터 1,000,000,000까지의 양의 정수, 알칼리성 용액 특성값: -1부터 -1,000,000,000까지의 음의 정수 같은 양의 두 용액을 혼합한 용액의 특성값: 두 용액의 특성값 합 특성값이 0에 가장 가까운 용액을 만들어라 입력 첫째 줄 N (2 0: e -= 1 print(ans1, ans2) solution(values, min_comb) try-error 절대값이 제일 작은 값을 찾는다? -> 0과 제일 가까운 수를 찾는다. binary search로 구현하기 쉬운 길을 어렵게 돌아가는 것이 아닌가하는 느낌을 받았음. 이분탐색 복습도 할 ..

백준 1914번 하노이탑 파이썬 (재귀) 참고: https://www.acmicpc.net/problem/1914 https://namu.wiki/w/하노이의 탑#fn-1 무엇? 세 개의 장대 첫 번째 장대에는 반경이 서로 다른 N개의 원판이 있음 각 원판은 반경이 큰 순서대로 쌓여있다. 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮긴다. 한 번에 한 개의 원판만 다른 탑으로 옮김 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 함 이 작업을 수행하는데 필요한 이동 순서를 출력 단, 이동 횟수 K는 최소 입력: 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 100) 출력 첫째 줄에 옮긴 횟수 K N이 20 이하인 입력에 대해서만, 둘째 줄부터 빈칸을 사이에 두고 A, B..

백준 2468번 안전영역 파이썬 (BFS) 참고: 무엇? 어떤 지역의 높이 정보 → 물에 잠기지 않는 안전한 영역은 최대 몇개? 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠김 어떤 지역의 높이 정보: 2^N * 2^N 배열 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수 안전한 영역이란 물에 잠기지 않는 지점들이 "상하좌우"로 인접하면서 그 크기가 최대인 영역 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N (2

백준 10989 수 정렬하기3 (도수정렬) 참고: https://www.acmicpc.net/problem/10989 무엇? N개의 수가 주어졌을 때, 이를 오름차순으로 정렬 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000) 둘째 줄부터 N개의 줄에는 수 수는 10,000보다 작거나 같은 자연수 왜? 정글 1주차 도수 정렬 복습 어떻게? 내 코드 수를 입력 받으면서 배열의 인덱스를 이용해 카운팅한다 카운팅 배열을 이중 for문으로 반복 count 값이 존재하면 count 값만큼 인덱스 출력 import sys input = sys.stdin.readline N = int(input()) array = [0] * 10001 # 수 입력 + 배열에 count for i in range(N): nu..

백준 1074번 Z 파이썬 참고: https://www.acmicpc.net/problem/1074 무엇? 크기가 2N * 2N인 2차원 배열을 Z모양으로 탐색 N > 1인 경우, 배열을 크기가 2^N-1 * 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문 N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력 정수 N, r(행), c(열) 1 ≤ N ≤ 15 0 ≤ r, c < 2^N 왜? 정글 알고리즘 주차때 못 풀었거나 & 정답을 참고해서 풀었던 문제들 다시 풀기 어떻게? 재귀 브레이크 (2^0 * 2^0 크기의 배열에 도착했을 때) 1,2,3,4 분면 중 어디에 속하는지 판별 → 제일 작은 Z에 도달할 때까지 count 계산 (1분면 +0, 2분면 +1 … ) import sys inpu..

백준 10971번 외판원 순회 (백트래킹) 참고: https://www.acmicpc.net/problem/10971 무엇? 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 경로를 구하려고 함 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 가장 적은 비용을 들이는 여행 계획은? W[i][j]는 도시 i에서 도시 j로 가기 위한 비용 W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. W[i][j]=0는 도시 i에서 도시 j로 갈 수 없는 경우 첫째 줄..