알고리즘
[백준/알고리즘] #1325: 효율적인 해킹 [파이썬(python)/그래프/DFS/BFS]
https://www.acmicpc.net/problem/1325
[백준/알고리즘] #7795: 먹을 것인가 먹힐 것인가 [파이썬(python)/이분탐색(binary search)
https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 이분탐색을 이용해서 정렬하는 로직을 짜는 문제다. 파이썬 코드 #7795_먹을것인가 먹힐것인가 import sys input = sys.stdin.readline def bin_search(target, data): start = 0 end = len(data)-1 res = -1 while start
[백준/알고리즘] #2548: 대표 자연수 [브루트포스]
https://www.acmicpc.net/problem/2548 2548번: 대표 자연수 첫째 줄에는 자연수의 개수 N이 입력된다. N은 1 이상 20,000 이하이다. 둘째 줄에는 N개의 자연수가 빈칸을 사이에 두고 입력되며, 이 수들은 모두 1 이상 10,000 이하이다. www.acmicpc.net 이 문제는 대표 자연수가 중간값이라는 것을 캐치하면 굉장히 간단하게 풀 수 있는 문제다. divmod()라는 함수를 사용하면 쉽게 구할 수 있다. 파이썬 코드 #2548_대표 자연수 import sys input = sys.stdin.readline N = int(input()) real = list(map(int,input().split())) real.sort() left, right = divmo..
[백준/알고리즘] #2910: 빈도 정렬
https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net set를 이용해서 정렬할 줄 알면 되는 문제다. 파이썬 코드 #2910_빈도 정렬 import sys input = sys.stdin.readline N, C = map(int, input().split()) message = list(map(int, input().split())) cnt = {} for i in message: if i not in cnt: cnt[i]=0 cnt[i] += 1 cnt=sorted(cnt.items(),..
[백준/알고리즘] #10821: 정수의 개수 [문자열]
https://www.acmicpc.net/problem/10821 10821번: 정수의 개수 숫자와 콤마로만 이루어진 문자열 S가 주어진다. 이때, S에 포함되어있는 정수의 개수를 구하는 프로그램을 작성하시오. S의 첫 문자와 마지막 문자는 항상 숫자이고, 콤마는 연속해서 주어지지 www.acmicpc.net S= input() num = S.split(',') print(len(num))
[백준/알고리즘] #1448: 삼각형 만들기 [파이썬(python)/수학]
https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 중학교 수학에서 배우는 삼각형의 개념을 통해 풀면 된다. 가장 긴 변의 길이 < 나머지 두 변의 길이 합 파이썬 코드 #1448_삼각형 만들기 import sys input = sys.stdin.readline N = int(input()) straw=[] for _ in range(N): straw.append(int(input())) straw.sort(reverse=T..
[백준/알고리즘]#2659: 십자카드 문제 [파이썬(python)/구현]
https://www.acmicpc.net/problem/2659 2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 십자수를 구하는 로직 하나 짜고, 입력된 값의 십자수가 1111부터 몇번째 십자수인지 구하면 된다. 처음엔 문제를 잘못 이해해서 입력된 값의 십자수가 1111부터 몇번째 값인지만 구했는데 틀렸다. 틀린 파이썬 코드 #2659_십자카드 문제 import sys input = sys.stdin.readline clknum = int(''.join(input().split())) clk=list(map(int,str(clknum..
[백준/알고리즘]#6896: 절사평균 [파이썬(python)/부동소수점]
https://www.acmicpc.net/problem/6986 6986번: 절사평균 첫째 줄에 절사평균(N, K)를, 둘째 줄에 보정평균(N, K)를 각각 소수점이하 셋째 자리에서 반올림하여 둘째 자리까지 출력한다. 예를 들어 결과값이 9.667인 경우 9.67로, 5인 경우 5.00으로, 5.5인 경우 www.acmicpc.net 절사평균과 보정평균을 구하는 방법은 쉬운데 float를 사용한다는 점을 유의해야한다. 첫 시도에는 round()로 단순하게 반올림을 했다가 실패했는데 테스트케이스 답이 다 맞아도 틀리는 이유가 부동소수점 밖에 없겠다는 생각이 들었다 float를 다루어 나누기 때문에 정수로 먼저 숫자를 바꾸어 (10이상의 수를 곱해주기) 계산해주고 마지막에 다시 그 숫자로 나누어준다. (C..
[백준/알고리즘]#11652: 카드 [파이썬(python)]
https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net try except문을 사용하여 카운트하였다. 정렬을 한 후에 첫번째 인덱스를 출력하면 된다. 파이썬 코드 #11652:카드 import sys input = sys.stdin.readline N = int(input()) card=[] for _ in range(N): card.append(int(input())) cnt={} for i in card: try: cnt[i]+=1 excep..
[백준/알고리즘]#2331: 반복수열 [파이썬(python)/수학]
https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 문제 이해하는 것만 한참 걸린 문제였다... 실버에서도 헤매는 알린이 ㅠㅠ 먼저 각 자릿수로 분리하기 위해 10씩 나누는 작업을 진행했고 자릿수 별 숫자로 계산한 res 결과값이 perm리스트에 존재한다면 break로 루프를 빠져나갔다. 그 해당 인덱스까지 출력. 파이썬 코드 #2331 반복수열 import sys input = sys.stdin.readline A, P = map(int, input().split()) perm = [A] while True: res = 0 A=perm[-1] while(A..
[백준/알고리즘]#1051: 숫자 정사각형 [파이썬(python)/브루트포스]
https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 www.acmicpc.net 브루트포스 알고리즘 문제로 브루트 포스는 "Brute Force", 즉 무식한 강제(?)라고 직역할 수 있습니다. 그리디 알고리즘과 다르게 완전 탐색으로 BFS, DFS,이분탐색처럼 모든 노드를 탐색하는 방법입니다. 그러므로 이 문제에서는 직사각형의 꼭짓점을 모두 탐색하도록 알고리즘을 구현하면 됩니다. 파이썬 코드 import sys input = sys.stdin.readline N, M =..
[백준/알고리즘]#10816: 숫자 카드 2 [해쉬]
https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 해쉬를 이용하거나 이분 탐색을 통해 풀 수 있는 문제다. 나는 해쉬를 사용하여 풀었다. 파이썬 코드 #10816 import sys input = sys.stdin.readline N = input() real_card = list(map(int, input().split())) real_card.sort() M = input() pred_card = list(m..
[백준/알고리즘]#2908: 상수 [수학/파이썬(python)/BOJ]
https://www.acmicpc.net/problem/2908 2908번: 상수 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 www.acmicpc.net 배열을 거꾸로 출력하는지 알면 풀 수 있는 문제다. C++이나 C언어였다면 반복 루프를 돌려서 하나씩 출력해줘야 하지만 파이썬은 간편하게 [::-1] 로 뽑을 수 있는 자료구조다. (외쳐 갓파이썬!!) #2908 상수 import sys input = sys.stdin.readline a, b = input().split() a = int(a[::-1]) b = int(b[::-1]) if a>b: print..
[백준/알고리즘]#1152: 단어의 개수 [문자열/파이썬(python)/BOJ]
https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열 www.acmicpc.net #1152 단어의 개수 import sys input = sys.stdin.readline sen = [] sen = list(map(str, input().split())) print(len(sen))
[백준/알고리즘] #6996: 애너그램 [문자열/파이썬(python)/BOJ]
https://www.acmicpc.net/problem/6996 6996번: 애너그램 첫째 줄에 테스트 케이스의 개수(
[백준/BOJ/알고리즘/파이썬(python)]#1100: 하얀 칸 [문자열]
https://www.acmicpc.net/problem/1100 1100번: 하얀 칸 체스판은 8*8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램 www.acmicpc.net 처음엔 국어능력이 부족해서.. 문제가 무슨 소리인지 이해하는데 걸려서 문제를 반복해서 계속 읽었다ㅋㅋㅋㅋㅋ 체스판 모양의 흰색 위에 있는 말 개수만 세면 된다. 처음엔 흰색의 열이 다 짝수 0 2 4 6 이라고 생각했는데 출력이 11인거 보고 뭔가 잘못 되었다는 걸 알았다 ^^;; 하얀 칸은 행과 열의 위치가 [0,0] [0,2] [0,4] [0,6] [1,1], [1,3].... 이런식으로 체..
[백준/BOJ/알고리즘/파이썬(python)]#11441: 합 구하기[누적 합]
https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 처음에는 바로 합을 구해서 출력하도록 했는데 시간초과가 났다. 시간초과 코드 #11441 합 구하기 import sys input = sys.stdin.readline N = int(input()) A = [] A =list(map(int, input().split())) M = int(input()) for k in rang..
[백준/BOJ/알고리즘/파이썬(python)]#1157: 단어 공부 [문자열]
https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 브론즈 등급의 문제라서 금방 풀 줄 알았는데 생각보다 구조를 짜기가 어려웠다. 처음엔 아스키코드를 이용해서 ord()함수를 이용해서 풀고있는데 잘 안되서 카운트한 정보 넣은 리스트를 만들고 max의 인덱스를 리스트에서 뽑아서 출력하는 구조 짜는 방향으로 바꾸었다. 대소문자 상관없다고 했으므로 upper()함수를 사용하면 대소문자 따로 카운트하지 않아도 된다. 파이썬 코드 #1157_단어공부 word = input().upper()..
[백준/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언어를 많..