문제. https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 아이디어 : n kg의 설탕을 n = 3*(3kg 봉지 개수) + 5*(5kg 봉지 개수)로 나타낼 수 없으면 -1 출력 나타낼 수 있는 경우에는 3kg 봉지 개수 + 5kg 봉지 개수 를 더한 결과를 리스트에 전부 저장해 가장 작은 값 출력 n kg 설탕을 3kg 봉지를 사용하지 않는 경우부터 ~ 최대로 사용하는 경우의 3kg봉지의 개수 = [0 ~ n//3개] 5kg 봉지를 사용하지 않는 경우부터..

문제. https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 아이디어 : 시간제한 3초 = 6000만번 연산 가능 1 등장 횟수가 곧 나이가 같을 경우 가입한 순서 seq가 된다. 다중 리스트의 sort()는 더 작은 index를 기준으로 먼저 정렬하므로 name보다 seq를 더 앞에 두고 정렬 구현 : import sys n = int(input()) member = [] range_age = [0] * 200 # idx + 1 = 나이 for i in..

문제. https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 아이디어 : 시간제한 2초 = 8000만번 연산 가능 O(N^2) = 250억번 >>> 8000만번 -> 불가 O(NlogN) = 약 300만번 > 원소 종류의 개수 이므로 계수 정렬 구현 : import sys n = int(input()) arr = [] cnt ..

문제. https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 아이디어1 : 수는 10000 이하의 자연수가 입력되는데, 원소 개수는 최대 1000만개이다. -> 원소의 종류 개수 배열은 입력 받은 n의 개수를 저장하는 용도로만 사용 구현 : import sys N = int(input()) count = [0] * 10000 for i in range(N) : n = int(sys.stdin.readline().strip()) count[n-1] += 1 # count..

문제. https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 아이디어 : 시간제한이 2초인데 1 index를 보고 입력받은 값을 O(1)로 바로 알 수 있는 일종의 해시테이블을 초기화한다. ex) result의 0번째 index가 숫자 -100만을, 200만 index가 숫자 100만을 의미한다. 입력으로 들어온 수 전부 해당 index에 추가해주면, update된 원소들만 입력으로 들어왔음을 의미한다. 즉, update한 원소만을 출력하..

문제. 8 x 8 크기의 체스판이 있다. 행 위치는1~8로, 열 위치는 a~h로 표시한다. (가장 왼쪽 위는 a1, 가장 오른쪽 하단은 h8이다) 나이트가 이동할 수 있는 경우는 2가지이다. 1. 수평으로 두 칸 이동 후 수직으로 한 칸 이동 2. 수직으로 두 칸 이동 후 수평으로 한 칸 이동 나이트의 위치가 입력으로 들어올 때, 나이트가 이동할 수 있는 경우의 수를 출력하라 (체스판을 벗어나는 움직임의 경우의 수는 무시한다) 입력 예시) a2 출력 예시) 2 - 시도 1 처음엔 상하좌우 한칸씩의 움직임을 dx, dy라는 리스트로 만들어 수직이동 -> dx[:2], dy[:2] 에서 선택, 수평이동 -> dx[2:], dy[2:] 으로 나누어 선택하려 했다. 그런데 또 수직이동을 1번하거나 or 2번하는..