차곡차곡

구현 문제에 대한 알고리즘을 소스코드로 만드는 과정이 구현이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수적이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 구형 유형의 문제는 풀이는 떠올리는 것은 쉽지만 그것을 소스코드로 옮기는 과정이 어려운 문제를 의미한다. 구현 유형 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례로 직접 수행 구현 문제 풀이시 생각해야 될 점 메모리 제약 사항 채점 환경 접근 방법 파이썬의 경우 1초에 2*10^7(2000만번)의 연산을 수행한다. pypy3 지원시 사용하면 1초에 1억번의 연산을 수행할 수 있다. pypy3의 속도는 c/c++에 견줄만큼 빠르기 ..

https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 2차원 배열에 두 좌표(r1,c1) (r2,c2)사이의 값을 type에 따라 감소 또는 회복 시켜야한다. type == 1 이면 degree만큼 감소한다. type == 2 이면 degree만큼 회복한다. 모두 마친 후 0 이상인 좌표의 갯수를 return해준다. 시간 복잡도는 O(1)로 해결해야 한다. 접근법 브루토 포스로 해결할 경우 시간 복잡도가 O(N*M*K)이므로 시간초과 발생..

누적합 구간의 누적합을 구하는 문제이다. 배열의 각 원소까지의 누적 합을 미리 계산해 놓은 배열을 생성하는 기법이다. 장점 배열 특정가간의 합을 빠르게 계산할 수 있다. 이론 구간 합 알고리즘을 활용하려면 우선 누적 합 배열을 구해야 한다. 0번 인덱스에는 0을 저장하고 1번 인덱스 부터 배열을 담아야 한다. 누적 합 배열 arr를 구할 때 아래와 같이 구한다. // 1차원 배열 arr[i] = arr[i-1] + inputArr[i] // 2차원 배열 arr[i][j] = inputArr[i][j] + arr[i-1][j] + arr[i][j-1] + arr[i-1][j-1] 누적 합 배열 arr를 이용해 구간 합을 구하자고 할때에는 아래와 같이 구한다. // 1차원 배열 arr[end] - arr[s..

https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv2 문제 이해 붙어 있는 수들의 합으로 k를 만들어야 한다. 답이 여러개인 경우 길이가 가장 짧은 수열을 찾아야 한다. 길이가 가장 짧은 수열이 여러개인 경우 앞쪽에 나오는 수열을 찾는다. 접근법 투포인터 알고리즘을 사용하여 합이 k 인 부분 수열을 찾는다. right가 오른쪽 끝까지 갈때 까지 반복문을 돌린다. 1. 합이 k와 같은 경우 - 해당 부분의 수열의 길이를 계산하고 가장 짧은 길..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 정답 code # 2*n 타일링 import sys input = sys.stdin.readline n = int(input()) sol = [0]*n for i in range(1,n+1): if i == 1: sol[i-1] = 1 elif i == 2: sol[i-1] = 2 else: sol[i-1] = sol[i-2] + sol[i-3] print(sol[-1]%10007) solution 2*n 직사각형에 ..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 정답 code #ATM n = int(input()) p = list(map(int,input().split())) sum = 0 p.sort() for i in range(n): for j in range(i+1): sum += p[j] print(sum) solution 어렵게 생각할것 없이 오름차순으로 정렬을 하면 제일 대기시간이 긴고객의 시간이 포함되지 않게 된다. 따라서 오름차순 정렬후 계속 더해나가면된다. 중복으로 ..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 정답 code #토마토 import sys from collections import deque input = sys.stdin.readline dx = [-1,1,0,0] dy = [0, 0 , -1, 1] def bfs(): while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] i..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 정답 code #색종이 만들기 import sys input = sys.stdin.readline n = int(input()) paper = [list(map(int,input().split())) for _ in range(n)] result = [] def solution (x,y,n): color = paper[x][y] for i in range(x,x+n): ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 정답 code #계단오르기 import sys input = sys.stdin.readline n = int(input()) score = [0 for i in range(301)] dp = [0 for i in range(301)] for i in range(n): score[i] = int(input()) dp[0] = score[0] dp[1] = score[0] + score[1] dp[2] = max..