전체 글 481

[Level 2] 카펫

programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 접근 노란색의 칸 수는 (가로길이-2) x (세로길이-2)가 된다. 2를 빼주는 이유는 양옆과 위아래로 한 칸씩 갈색 칸이 있기 때문이다. 입력받는 노란색과 갈색칸을 더해주면 전체넓이가 되고 전체넓이의 약수 중에서 가로길이를 찾은 후에 가로길이를 통해 세로길이를 찾는다. 적합한 가로길이와 세로길이를 찾았다면 위에서 노란색 칸의 수를 구하는 공식에 대입하여 일치하는지 확인한..

[백준 2407] 조합

문제 nCm을 출력한다. 입력 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) 출력 조합의 결과를 출력한다. 접근 먼저 조합은 N개의 원소 중에서 M개를 순서에 상관없이 선택하는 경우의 수다. 이를 구하기위한 공식이 존재하며 다음과 같다. 따라서 다음의 식대로 구현을 하였다. 구현 팩토리얼을 math 모듈의 factorial()을 사용하였다. import math N, M = map(int, input().split()) answer = math.factorial(N) // (math.factorial(N-M) * math.factorial(M)) print(answer)

[백준 15654] N과 M (5)

문제 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력 한 줄에 선택한 M개의 수를 나열한다. 접근 M개의 수를 선택하기위해 백트래킹을 사용하였고 선택할 수를 찾는 인덱스를 0부터 시작하여 찾도록 하였다. 구현 아직 선택하지 않은 수 중에서 숫자를 선택할 때 처음부터 탐색을 하도록 하였다. 왜냐하면 (1, 7)과 (7, 1)은 다른 조합이기 때문에 이 두 개의 조합도 출력하도록 하였다. def ..

[백준 15650] N과 M(2)

문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 N과 M이 주어진다. 1 ≤ M ≤ N ≤ 8 출력 한 줄에 선택한 M개의 수를 출력한다. 중복으로 출력할 수 없고 오름차순으로 출력한다. 접근 백트래킹으로 1차원 리스트에 저장된 수열을 M개 선택하도록 하였다. 구현 다음은 N개의 수열 중에서 M개를 선택하는 함수이다. 선택된 수는 picked라는 리스트에 저장하게되며 리스트의 길이가 M이 되었을 때 리스트 안에 있는 수를 출력한다. 만약 아직 M개를 선택하지 못했다면 선택하지 않은 수들을 골라 리스트에 넣어주고 재귀호출을 한다. de..

[백준 9461] 파도반 수열

www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 접근 변의 길이가 증가하는 규칙을 찾아보면 현재 i번째 길이를 구한다고 했을 때 (i-2) + (i-3)을 통해 구한다. 따라서 위의 점화식을 토대로 구현하도록 한다. 구현 초기 세 개의 길이를 1로 초기화하고 이후의 길이는 i = (i-2) + (i-3)이라는 점화식을 통해 구하도록 한다. test_case = int(input()) for tc in range(test_case): N = int(input()) ..

[Level 2] 네트워크

programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 접근 DFS로 연결된 컴퓨터를 탐색하였다. 방문하지 않은 컴퓨터가 있을 때 방문하여 연결된 모든 컴터를 탐색하였다. 이렇게되면 DFS 탐색을 할 때마다 최종해를 카운트해주면 된다. 구현 방문 표시를 할 visited 리스트를 초기에 False로 초기화해줬다. visited = [False for _ in range(n)] 0번부터 탐색을 하여 방문하지 않은 컴퓨터가 있으..

[Level 2] 땅따먹기

programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 접근 백준의 RGB거리와 같은 유형의 문제였다. 그 이유는 0행부터 내려오면서 땅을 밟고 연속해서 같은 행의 땅은 밟을 수 없다고 했을 때 가장 아래의 행에 내려왔을 때 최대값을 구하는 것이기 때문이다. 따라서 1행부터 이전의 행에서 밟을 수 있는 땅 중 최대를 찾아 더해가면서 밑으로 내려가도록 한다. 구현 def solution(land): answer ..

[백준 1966] 프린터 큐

문제 프린터는 다음과 같은 조건에 따라 인쇄된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 프린터의 문서 수가 주어졌을 때 어떤 문서가 몇 번째로 출력되는지 구하라 입력 첫째 줄에 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에 문서의 수와 확인하고자 하는 문서의 위치를 입력하고 이어서 문서의 중요도를 입력한다. 출력 확인하고자 하는 문서가 몇 번째로 인쇄되는지 출력한다. 접근 문서들의 위치에 따른 중요도를 큐에 담는다. 그리고 중요도가 큰 것과 같으면 pop을 하고 그렇지 않다면 front에 있는 문서를 ..

[백준 2609] 최대공약수와 최소공배수

문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 접근 유클리드 호제법을 통해 최대공약수와 최소공배수를 구해보았다. 먼저 최대공약수를 구하기 위해서 두 수 A와 B가 A>B일 때 B가 0이 될 때까지 A%B를 A에 대입한다. 그리고 A와 B의 값을 교환한다. B가 0이 되는 순간의 A값이 최대공약수가 된다. 또한 최소공배수는 A*B를 최대공약수로 나눠주면 된다. 그 이유는 A와 B의 최대공약수는 두 수 사이에 겹치는 공약수 중 ..

[백준 15829] Hashing

www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 접근 ord()를 통해 문자를 숫자로 변경 후에 각각 96을 빼주어 a가 1이 되도록 하였다. 구현 N = int(input()) word = input() answer = 0 for idx in range(N): answer += (ord(word[idx])-96) * (31**idx) print(answer%1234567891)

728x90
반응형