알고리즘/백준(BOJ)
[백준/BOJ/알고리즘/파이썬(python)]#2675:문자열 반복
https://www.acmicpc.net/problem/2675 2675번: 문자열 반복 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다 www.acmicpc.net 파이썬 코드 #2675_문자열 반복 T = int(input()) for _ in range(T): R, S = list(map(str, input().split())) R = int(R) for i in S: print(R*i, end='') print() ABCABCABC가 아닌 AAABBBCCC를 출력하고자 한다면 반복문을 안에서 한번 더 돌리면 된다.
[백준/BOJ/알고리즘/파이썬(python)/C++]#11654:아스키 코드
https://www.acmicpc.net/problem/11654 11654번: 아스키 코드 알파벳 소문자, 대문자, 숫자 0-9중 하나가 주어졌을 때, 주어진 글자의 아스키 코드값을 출력하는 프로그램을 작성하시오. www.acmicpc.net 파이썬 (Python) chr()함수를 쓰려고 했는데 ord()함수를 쓰면 됐다. ord() : 문자의 아스키 코드값을 리턴하는 함수이다. chr() : 아스키 코드값 입력으로 받아 그 코드에 해당하는 문자를 출력하는 함수이다. 참조 https://wikidocs.net/32 (점프 투 파이썬-WikiDocs) #11654 아스키코드 x = input() print(ord(x)) C++ chr자료형을 int로 출력하면 바로 아스키코드로 나온다는 것은 C언어를 많..
[백준/BOJ/알고리즘/파이썬(python)]#2740_행렬 곱셈
https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 행렬의 곱셈을 계산하는 문제로 반복문과 배열을 행렬곱연산에 맞게 구조를 잘 짜면 된다. 파이썬 코드 #2740_행렬곱셈 import sys input = sys.stdin.readline N, M = map(int, input().split()) A_element = [] for _ in range(N): A_element.append(list(map(int,input().spl..
[백준/BOJ/알고리즘/파이썬(python)]#2941_크로아티아 알파벳 [문자열]
https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 센스껏 replace()라는 함수를 사용해서 푸는 문자열 문제다. 이상하게 이 문제는 stdin.readline()하면 카운트가 한 번 더 된다... 이유를 모르겠다ㅠ 그냥 input으로 입력을 받으면 된다. 파이썬 코드 #2941_크로아티아 알파벳 cro = input() alph=['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=',..
[백준/BOJ/알고리즘/파이썬(python)]#3273_두 수의 합
https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 정렬/두 포인터 문제로 역시나 그냥 반복문을 돌리니 시간초과가 떴다 이분탐색하여 두 포인터로 탐색해서 풀면 된다. 반복문 조건을
[백준/BOJ/알고리즘/파이썬(python)]#8595_히든 넘버[문자열]
https://www.acmicpc.net/problem/8595 8595번: 히든 넘버 첫째 줄에 단어의 길이 n (1 ≤ n ≤ 5,000,000)이 주어진다. 둘째 줄에는 단어가 주어진다. 단어는 알파벳 대/소문자와 숫자(0-9)로 이루어져 있다. www.acmicpc.net 파이썬 코드 #8595 히든넘버 import sys input = sys.stdin.readline n = int(input()) st = input() number = '0123456789' hid = '' for i in range(n): if st[i] in number: hid += st[i] else: hid += ' ' res = 0 hidfind = list(map(str, hid.split(' '))) for i..
[백준/BOJ/알고리즘/파이썬(python)]#10809_알파벳 찾기
https://www.acmicpc.net/problem/10809 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 파이썬 코드 import sys input = sys.stdin.readline S = input() alph = list(range(97,123)) for i in alph: print(S.find(chr(i)), end=' ') alph = 'abcdefghijklmnopqrstuvwxyz' 이런식으로 해서 짜는 것도 가능하지만 아스키코드를 활용하면 된다. 97은 소문자 a, 12..
[백준/BOJ/알고리즘/파이썬(python)/C++]#1920_수 찾기[이분탐색]
https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이 문제는 많은 분들이 저를 포함해서 첫 시도에 (쉬운문제네~)하고 시간초과를 맛보셨을 것 같습니다 ^^;;; 이분탐색으로 풀어야한다고 문제에 적어줘야하는거 아니냐구~ㅋㅋㅋ 시간초과 나서 실패한 파이썬 코드 import sys input = sys.stdin.readline N = int(input()) n_list = [] n_list = map(..
[백준/BOJ/알고리즘/파이썬(python)/C++]#1932_정수 삼각형
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 그리디 알고리즘으로 DP로 짜면 되는 문제다. 어렵게 자꾸 생각하니까 로직이 막 꼬이고 한참 헤맸다...휴 그냥 단순하게 생각해도 되는 문제는 단순하게 생각하자! 파이썬 코드 import sys input = sys.stdin.readline n = int(input()) tri = [] for _ in range(0, n): tri.append(list(map(int, input().split()))) row = 2 for i in range(1, n): for j ..
[백준/BOJ/알고리즘/파이썬(python)]#7785_회사에 있는 사람
https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net import sys input = sys.stdin.readline dic = {} n = int(input()) for _ in range(n): person, log = map(str,input().split()) if log == 'enter': dic[person] = 'enter' if log == 'leave': del dic[person] res..
[백준/BOJ/알고리즘/파이썬(Python)]#10212:Mystery
https://www.acmicpc.net/problem/10212 10212번: Mystery "Yonsei"혹은 "Korea"(이번에는 연세대를 앞에 해드렸습니다.)중 하나를 출력한다. 따옴표는 출력하지 않는다. www.acmicpc.net 말 그대로 Mystery인 문제ㅎㅎ... 재밌는 문제다 딱히 알고리즘 공부 느낌보다는 재미로 간식 먹듯이 풀어볼 만한 문제랄까... 출력문은 고려대 연세대가 번갈아 나타난다. (고려대를 앞에 두어야죠...) 처음엔 문제보다 딱 3초만 직관적으로 생각난 풀이는 무한 루프 안에서 time()이랑 sleep()함수를 사용하는 것이었다... 그런데 질문 게시판을 보니 rand()를 쓰는게 출제의도라는 스포를...!! 그런데 또 random.random()으로 쓰면 틀린다..
[백준/BOJ/알고리즘/파이썬(python)]#9148:신나는 함수 실행[재귀]
https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 재귀 호출을 하는 문제로 1. 리스트배열 할당을 20만큼씩 (20이 넘으면 어차피 조건문에서 걸리므로) 하는 것 2. 재귀배열이 있다면 재귀배열을 리턴, 아니면 구하는 조건문으로 넘어가는 것 이 두 가지를 신경써야한다. 파이썬 코드 import sys sys.stdin.readline arr = [[[0]*21 for _ in range(21)] for _ in range(21)] def w(a,b,..
[백준/BOJ/알고리즘/파이썬(python)]#1978_소수 찾기[수학/에라토스테네스의 체]
https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 에라토스테네스의 체: 에라토스테네스의 체는 소수를 찾는 방법으로 알고리즘은 다음과 같다. x의 배수를 모두 지우고(위의 사진처럼 컬러링) 마지막으로 살아남은 녀석들이 소수(prime number)다. import sys input = sys.stdin.readline N = int(input()) num_list = [] num_list=map(int, input().split()) prime_cnt=0 for i in num_list: #에리토스테네스의 체 fla..
[백준/BOJ/알고리즘/파이썬(python)]#11725_트리의 부모 찾기[트리/그래프]
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 루트 1부터 시작해서 dfs로 탐색하는 알고리즘으로 풀었다. 방문유무 정보 저장하는 배열을 하나 만들고 방문하지 않았다면 부모노드를 업뎃하면서 dfs탐색하면 된다. 재귀로 한 번 풀고 큐로 한 번 풀었다. 파이썬 코드_재귀 풀이(recursion) #11725_recursion import sys input = sys.stdin.readline sys.setrecursionlimit(10**9) N = int(input()) tree = [[] for _ in..
[백준/BOJ/알고리즘/파이썬(python)]#1197_최소 스패닝 트리[MST/트리/그래프]
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net MST 문제를 풀어보려고 했는데 다 다이아몬드 문제 뿐이라.. 골드 문제를 찾아서 풀어보았다. 스패닝 트리(Spanning Tree)란 1. 모든 정점을 포함하고 2. 사이클(Cycle)이 존재하지 않는 트리다. 최소 스패닝 트리(Minimum Spanning Tree_MST)는 3. 가중치가 최소 되는 트리다. 크루스칼 알고리즘(Kruskal Alg..
[백준/BOJ/알고리즘/파이썬(python)]#15649,#15650,#15651,#15652_N과M(1)(2)(3)(4)[순열/조합]
https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net https://www.acmicpc.net/problem/15651 15651번: ..
[백준/BOJ/알고리즘/파이썬(Python)]#9372_상근이의 여행[트리/그래프]
https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 최소신장트리 문제를 찾아서 풀려고 했는데 다 다이아몬드 아니면 엄청 쉬운 문제 뿐.... 위의 스케치 그림과 같이 모든 국가를 순회하려면 노란색 선분만큼 지나야 한다. 그런데 모두 연결되어 있는 그래프가 예제로 나오므로 DFS BFS 순회를 하지 않아도 그냥 N-1(국가 수-1)만큼이 노란색 선분이다. import sys input = sys.stdin.rea..
[백준/BOJ/알고리즘/파이썬(python)]#14888_연산자 끼워넣기
https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 백트래킹으로 분류되어 있는 문제로 연산자 4개의 순열조합을 통해 연산을 진행하는 탐색 문제다. 재귀를 사용하는 방법도 있지만 시간적 비용을 줄이기 위해 반복을 사용하여 풀었다. 파이썬은 permutation이라는 매우 편한 itertools 라이브러리가 있어서 중복제거를 위한 조합 로직을 C나 C++처럼 다 짤 필요가 없다. 재귀를 사용한다면..
[백준/BOJ/알고리즘/파이썬(Python)/C++]#14889_스타트와 링크
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 파이썬은 combinations라는 아주 편~한 라이브러리로 코딩할 수 있다.(파이썬최고) start를 먼저 배정하고 나머지 빈 배열에 link를 배정하였다. 파이썬 코드 import sys from itertools import combinations input=sys.stdin.readline arr = [] N = int(input()) for i in range (N): arr.append(list(map(in..
[백준/BOJ/알고리즘/파이썬(python)/C++/백트래킹]#15649_N과M(1)
https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹 문제로 파이썬으로하면 permutation으로 몇줄컷이 되는데 C++로 짜면 좀 더 복잡해진다. 파이썬 코드 import sys from itertools import permutations input = sys.stdin.readline N, M = map(int, input().split()) P = permutations(range(1, N+1), M) for i in P: pri..