Programming
백준 11726 - 2 x n 타일링 (파이썬)
백준 11726 - 2 x n 타일링 (파이썬)
2025.02.21분류 : 다이나믹 프로그래밍https://www.acmicpc.net/problem/11726풀이점화식을 새워야 한다. 일단 An : 2 * n 타일을 1 * 2, 2 * 1 타일로 채우는 경우의 수를 생각해야한다.An = A(n - 1) + A(n - 2) 라는 점화식을 세울 수 있다.즉 이 문제를 생각해 보면, 숫자가 너무 커지기 때문에 일단 10007로 나눈다는 조건을 생각해야한다.먼저 dp 배열에 들어갈 초기 값을 생각한다.1번의 dp는 2 * 1 타일에 들어 갈수 있는 타일은 1개이다.2번의 dp는 2 * 2 타일에 들어 갈 수 있는 타일은 총 2개이다.1 * 2 타일 2개인 방법 1개2 * 1 타일 2개인 방법 1개예시를 생각해보자, 2 * 5 크기의 직사각형을 채운 한 가지 방법의 예를 확인..
백준 1759 - 암호 만들기 (파이썬)
백준 1759 - 암호 만들기 (파이썬)
2025.02.21https://www.acmicpc.net/problem/1759문제암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.바로 어제 최백..
백준 2579 - 계단 오르기 (파이썬)
백준 2579 - 계단 오르기 (파이썬)
2025.02.03https://www.acmicpc.net/problem/2579전형적인 DP 문제이다..이 문제의 조건은 다음과 같다.1. 연속된 3개 계단을 모두 밟으면 안된다.2. 마지막 도착 계단은 반드시 밟아야한다.3. 계단은 한번에 한 계단 또는 두 계단씩 오를 수 있다.위 그림의 예제에서는 6개의 계단이 주어진다.S = 10, 20, 15, 25, 10, 201. 마지막 층인 20은 무조건 밟아햔다. 그럼 10을 밟게 되면 25는 못 밟으니까, 10을 버리고 25를 밟는게 최적2. 15를 밟게 되면 10, 20을 못밟으니까, 15를 버리고, 10, 20을 밟는게 이득3. 총 4개를 밟는 것이 최선, 총 75의 값을 가지게 된다.수열로써 값을 나타내면 다음과 같다.1. aN은 N번째, 최대 점수 (바로 전 ..
백준 11725 - 트리의 부모 찾기
백준 11725 - 트리의 부모 찾기
2025.02.01https://www.acmicpc.net/problem/11725 먼저 예제 1번을 바탕으로 문제를 이해하면, 71 66 33 54 12 44 7 (그리면서 풀면 더 쉽다..)2번 노드 -> 4번3번 노드 -> 6번4번 노드 -> 1번5번 노드 -> 3번6번 노드 -> 1번7번 노드 -> 4번1번부터 N번까지의 노드가 있다. 입력받은 인접한 두 노드를 트리로 완성하고, 각 노드의 부모가 누구인지 확인하는 문제이다.import syssys.setrecursionlimit(10**6)# input = sys.stdin.readline()N = int(input())adj = [[] for _ in range(N)] # 인접리스트for i in range(N - 1) : a, b = list(map(i..
백준 2606 - 바이러스
백준 2606 - 바이러스
2025.02.01https://www.acmicpc.net/problem/2606해당 문제는 그래프로도 풀어봤고, 새로운 풀이인 DFS로 풀이를 진행하였다.N = 컴퓨터의 수, M은 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수그 이후부턴, 한줄에 한쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.해당 문제에서 DFS를 적용한 이유는 다음과 같다."단순히 그래프로도 풀이를 할수 있지만, DFS 알고리즘을 사용하면 시간복잡도가 O(2M)이 된다.'먼저 N, M을 입력받고, adj 배열에 각각 컴퓨터를 연결시킨다.N = int(input())M = int(input())adj = [[] for i in range(N)]for _ in range(M) : a, b = list(map(int,..
[명품 Java Programming] 7장 제네릭과 컬렉션
[명품 Java Programming] 7장 제네릭과 컬렉션
2022.06.17명품 자바 프로그래밍 7장 제네릭과 컬렉션 컬렉션 (Collection)은 안드로이드를 비롯한 자바 프로그램을 작성하는데 빼놓을수 없는 중요한 도구이다. 컬렉션은 대체로 다음과 같이 설명 할 수 있다. Element 객체들의 저장소 고정 크기의 배열을 다루는 어려움 해소 다양한 객체들의 삽입, 삭제, 검색 등의 관리 용이 배열의 경우 여러 개의 데이터를 다루는 데 편리한 자료 구조이지만, 삽입 삭제가 빈번하게 일어나며, 데이터의 크기를 예측 할 수 없는 응용프로그램에서 사용하기에는 불편하다. 배열 ) 고정 크기 이상의 객체를 관리할 수 없다. 배열의 중간에 객체가 삭제되면 응용프로그램에서 자리를 옮겨야 한다. 컬렉션 ) 가변 크기로서 객체의 개수를 염려할 필요 없다. 컬렉션 내의 한 객체가 삭제되면 컬렉..
[프로그래머스/JAVA] 프로그래머스 문제 모음
[프로그래머스/JAVA] 프로그래머스 문제 모음
2021.11.02언제든지 비공개 될수 있음을 명시합니다. 만약 문제 저작권에 위배된다면 바로 사라질수 있음을 미리 알려드립니다. 문제 찾기는 해당 문제 Ctrl + F 를 통해서 검색,, 홀수의 개수 함수의 인자값으로 양의 정수 n이 주어진다. 이때, 1부터 n 이하의 수들 중 홀수의 개수를 리턴하는 함수를 구현하시오. class Solution { public int solution(int n) { int answer = 0; for(int i = 1; i num2를 만족하고, 항상 큰수에서 작은수를 뺍니다. class Solution { public int solution(int num1, int num2) { int answer = 0; answer = (num1 + num2) + (num1 - num2) + (n..
[프로그래머스] 행렬의 합
[프로그래머스] 행렬의 합
2020.10.12def solution(arr1, arr2): result = [] temp = [] for i in range(len(arr1)): for j in range(len(arr1[i])): temp.append(arr1[i][j] + arr2[i][j]) result.append(temp) temp = [] return result for문에서 사실 애먹었다;; for i in range(len(arr1)): #arr1의 요소 2개 (2번 돈다.) for j in range(len(arr1[i)) # arr1의 요소 안의 요소 temp.append(arr1[i][j] + arr2[i][j] result.append(temp) temp = []#요소를 묶기 위해
[프로그래머스] 두 개 뽑아서 더하기
[프로그래머스] 두 개 뽑아서 더하기
2020.10.12def solution(numbers): numbers = sorted(numbers) result = [] for i in range(len(numbers)): for j in range(i + 1, len(numbers)): result.append(numbers[i] + numbers[j]) print(result) result = set(result) print(result) result = list(result) return (result) 처음 시도는 result를 list로 놓고, 5번을 도는 동안, i+1에서는 i값과 j값을 동시에 추가한다. 하지만 이 방법은 실패로 돌아갔고, set을 미리 지정해 주어야한다. def solution(numbers): numbers = sorted(numb..
[프로그래머스] 이상한 문자 만들기
[프로그래머스] 이상한 문자 만들기
2020.10.12def solution(s): s = s.split() temp = [] for i in s: idx = 0 for j in i: if idx % 2 == 0: temp.append(j.upper()) print(idx, j.upper()) else : temp.append(j.lower()) idx += 1 temp.append(" ") temp.pop() print(temp) print("".join(temp)) idx를 사용해서, idx의 위치에 맞는 문자를 대소문자로 변경해준다.
[프로그래머스] 정수 제곱근 판별
[프로그래머스] 정수 제곱근 판별
2020.10.11def solution(n): import math num = math.sqrt(n) if math.sqrt(n) == int(math.sqrt(n)) : #정수값이 나온다 => 제곱근의 존재 return pow(num+1, 2) #num+1 * num+1 return -1
[프로그래머스] 자연수 뒤집어 배열로 만들기
[프로그래머스] 자연수 뒤집어 배열로 만들기
2020.10.11def solution(n): return list(map(int, reversed(str(n)))) map에 대해서 자세히 공부하자
[프로그래머스] 정수 내림파순으로 배치하기
[프로그래머스] 정수 내림파순으로 배치하기
2020.10.11def solution(n): print(n) a = list(str(n)) # a라는 변수를 지정해, n의 값들을 list형태로 저장 print(a) # ['1', '1', '8', '3', '7', '2'] intList = list(map(int, a)) #intList라는 리스트를 지정해, str형태의 원소를 int형태로 지정 print(intList) #[1, 1, 8, 3, 7, 2] intList.sort(reverse=True) print(intList) #[8, 7, 3, 2, 1, 1] a = ''.join(map(str,intList)) #join을 사용하기 위해서는 다시 str형태로 지정해야한다. return int(a)
[프로그래머스] 시저 암호
[프로그래머스] 시저 암호
2020.10.11def solution(s, n): answer = [] for i in s: if i.isalpha(): if( 65 122: result = ord(i) + n - 26 answer.append(chr(result)) else : result = ord(i) + n answer.append(chr(result)) else: answer.append(' ') print(answer) return ''.join(answer)
[프로그래머스] 소수 찾기
[프로그래머스] 소수 찾기
2020.10.10def solution(n): count = 0 for i in range(1, n+1): temp_cnt = 0 for j in range(1,i+1): if i % j ==0: temp_cnt +=1 if temp_cnt == 2: count += 1 return count