alpyrithm_알파이리즘

DP 9095 1, 2, 3 더하기 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍 풀이 1 제일 처음 이 문제를 풀 때는 DP라는 것을 잘 모를 때였다. 따라서, DP가 아닌 브루트 포스를 통해 접근한 풀이이다. def solve(s): global cnt for i in arr: res.append(i) if sum(res) == s: res.pop() cnt +=1 break solve(s) res.pop() return cnt T = int(input()) for _ in range(T): s = in..

DP 11727 2xn 타일링 2 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 풀기 전 공부할 것 : 다이나믹 프로그래밍(DP) 풀이 1 2 x n번째 직사각형을 타일로 어떻게 채울 수 있는가를 고민해야 한다. 먼저 2 x 1의 경우 2 x 1의 경우 1가지이다. 2 x 2의 경우 2 x 1을 2개 붙이는 경우, 1 x 2를 2개 붙이는 경우, 2 x 2 1개로 3가지이다. 2 x 3의 경우 2 x 2에 (2 x 1을 붙이는 경우) + 2 x 1에 (1 x 2를 2개 붙이는 경우..

2557 Hello World www.acmicpc.net/problem/2557 2557번: Hello World Hello World!를 출력하시오. www.acmicpc.net 문제 풀기 전 공부할 것 : 입출력, 구현 「코딩을 배울 때 가장 배우는 것이 Hello World이다. Hello World를 출력할 때, 나는 새로운 세상을 접하는 느낌이었다.(사실 그냥 작동 원리 하나도 모르고 신기하기만 함) 코딩에서 가장 기초라고 할 수 있는 입력, 출력 문제이다. 파이썬으로 다양하게 출력을 표현해볼 생각이다.」 풀이 1 print('Hello World!') 풀이 2 sys를 import 해서 출력하기 import sys sys.stdout.write("Hello World!")

10546 배부른 마라토너 www.acmicpc.net/problem/10546 10546번: 배부른 마라토너 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명 www.acmicpc.net 문제 풀기 전 공부할 것 : 자료 구조, 해쉬, 맵 풀이 for문으로 n번 돌면서 참가자의 이름을 dictionary 형태로 저장한다.(동명이인이 있을 수 있음) for문으로 n-1번 돌면서 완주한 사람의 value에 -1 한다. value가 1인 사람이 완주하지 못한 참가자이다. import sys input = sys.stdin.readline n = int(input()..

3986 좋은 단어 www.acmicpc.net/problem/3986 3986번: 좋은 단어 이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 www.acmicpc.net 문제 풀기 전 공부할 것 : 자료 구조, 스택 풀이 좋은 단어를 찾는 방법을 괄호가 바로 되어 있는지로 해석했다. 따라서 단어를 pop 하면서 하나씩 꺼내고 stk가 비어있으면 pop한 글자를 넣고 stk가 비어있지 않으면 stk의 마지막 단어와 비교하여 같으면 stk에서 그 글자를 빼고 아니면 stk에 글자를 넣는 방식으로 진행한다. stk에 글자가 들어있으면 좋은 단어가 아니다. import sys..

2910 빈도 정렬 www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫쨰 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 문제 풀기 전 공부할 것 : 구현, 자료 구조, 정렬, 맵 풀이 빈도와 몇 번째 등장하는지를 count에 dictionary로 저장한다. count의 key와 value를 저장하고 빈도, 먼저 나온 것으로 정렬한다. 그리고 해당 숫자가 나온 만큼 출력한다. n, c = map(int, input().split()) seq = list(map(int, input().split())) count = {} idx = 1 for s in s..

5568 카드 놓기 www.acmicpc.net/problem/5568 5568번: 카드 놓기 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 문제 풀기 전 공부할 것 : 자료 구조, 브루트포스 알고리즘, 재귀, 맵 풀이 순열을 이용해서 해결할 수 있다. n개 중에서 k개를 뽑을 때, 순서에 따라서 다른 숫자를 만들 수 있으므로 순열을 이용해야 한다. 같은 숫자를 만들 경우를 대비해서 set을 이용한다. from itertools import permutations import sys input = sys.stdin.readline n, k = int(input()), int(input()) cards = [input().rstrip() fo..

12605 단어순서 뒤집기 www.acmicpc.net/problem/12605 12605번: 단어순서 뒤집기 스페이스로 띄어쓰기 된 단어들의 리스트가 주어질때, 단어들을 반대 순서로 뒤집어라. 각 라인은 w개의 영단어로 이루어져 있으며, 총 L개의 알파벳을 가진다. 각 행은 알파벳과 스페이스로만 www.acmicpc.net 문제 풀기 전 공부할 것 : 자료 구조, 스택 풀이 for문을 돌면서 몇 번째 케이스인지 i를 통해 확인한다. 단어들을 list로 받고 나중에 출력할 때 역순으로 출력한다. import sys input = sys.stdin.readline n = int(input()) for i in range(1, n+1): words = list(input().rstrip().split()) ..