KEEP CODING

연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 수와 연산자들을 입력받은 후 해야할 일을 정리해봤다. 1. 개수로 입력받은 연산자를 사용할 수 있도록 바꿔준다 2. 연산자를 중복없이 배열한다 3. 입력받은 숫자 순서대로 연산한다 문제에서는 연산자 순서(* / 먼저, + - 나중)상관없이 앞에서부터 계산해야 한다고 했다. 1 2 3 4 5 6 7 8 9 N = int(inpu..

스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제를 해결하기 위해 단계를 나눠보았다. 1. N명을 두 팀으로 나눈다. 2. 두 팀의 능력치를 구한다. 3. 능력치의 차를 구한다. 각각 함수로 만들었다. 1. N명을 두 팀으로 나눈다. 이전에 푼 문제를 변형했다. 15650번 문제는 1부터 N까지의 자연수 중 M개를 중복없이, 오름차순 수열을 구하는 문제였다. 이 문제는 1부터 N까지의 자연수 중 N/2개를 중복없이 고르는 것과 같다. (참고: ht..

N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 일단 체스에서 퀸은 수직, 수평, 대각선으로 이동할 수 있다. 문제에서는 N개의 퀸을 N*N칸에 배열해야 한다. 수직/수평에 있으면 공격할 수 있기 때문에 같은 행, 같은 열에는 퀸이 하나씩만 있을 수 있다. 그렇기 때문에 퀸의 위치를 N*N인 2차원 배열이 아닌, 1차원 배열로 표현할 수 있다. N=4일때 가능한 이 배치에 대해서는 (2, 0, 4, 1)로 각각 (첫 번째 행, 두 번째 행, 세 ..

N과 M (4) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이번엔 수열이 중복된 수로 구성될 수 있지만, 앞의 수보다 뒤의 수가 커야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 N, M = list(map(int,input().split())) numbers = [] def add_number(num): if len(numbers) == M: print(' '.join(map(str, numbers))) re..

N과 M (3) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15651번이 이전 문제들과 다른 점은 수열을 중복된 수로 구성할 수 있다는 점이다. 이전에 만든 코드에서 함수 내부만 조금 바꾸면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 N, M = list(map(int,input().split())) numbers = [] def add_number(): if len(numbers) == M: print(' ..

좌표압축 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 좌표 압축이라는 것이 자신의 좌표값보다 큰 서로 다른 좌표의 개수라고 한다. 예제 입력 2를 확인하면 알 수 있듯이, 999의 경우 1000이 3개가 있지만 출력에서는 1로 표시되어야 한다. 그래서 처음엔 입력받은 자료들에서 중복된 값을 제거한 후 정렬해서 입력받은 수 보다 큰 숫자가 몇 개 있는지 세는 방법으로 구했다. (시간초과한 코드..

N과 M (2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 15649번을 풀 때 찾아봤던 재귀함수를 떠올리며 코드를 작성해봤다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 N, M = list(map(int,input().split())) numbers = [] def add_number(num): if len(numbers) == M: print(' '.join(map(str, numbers))) return fo..

N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 재귀함수를 만들어야되나 생각했는데 코드를 작성하다보니 다른 방법으로 함수를 만들었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 N, M = map(int, input().split()) def add_number(): # 중복되지 않은 수들로 수열을 만드는 함수 global result # 전역변수에 저장된 값 가져옴 ..

나이순 정렬 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 정렬 기준은 1. 나이에 따라 오름차순 2. 가입한 순서에 따라 이다. 입력은 가입한 순서로 주어진다고 했고, sort로 정렬되는 배열의 경우 안정적임이 보장되어 같은 정렬 기준일 경우 원래 순서가 유지된다. 위 조건들에 따라 코드를 작성하면 다음과 같다. 1 2 3 4 5 N = int(input()) members = [list(input().split()) for _ in range(..

단어 정렬 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 정렬의 기준을 살펴보면 다음과 같다. 1. 중복된 단어가 없어야 한다. 2. 단어의 길이가 짧은 것 부터(단어의 길이에 따라 오름차순) 3. 단어의 길이가 같다면 사전 순으로 단어를 정렬하기 전에 단어를 입력받을 때 부터 중복된 값이 있는지 확인한 후, 없으면 저장하도록 했다. 1 2 3 4 5 6 7 8 9 10 N = int(input()) words = [] for _ ..