전체 글30

• [백준 1013] Contact import sys input = sys.stdin.readline T = int(input()) for _ in range(T): code = input().rstrip() l = len(code) i = 0 ch = True while i < l : # 시작이 0인경우 바로 뒤에 1이 안오면 실패 if code[i] == "0": #남은 수가 2개가 안될 때 실패(01이 최소 길이기 때문) if l-i < 2: ch=False break elif code[i+1] != "1": ch=False break else: i+=2 # 시작이 1이 올경우 else: #남은 수가 4개가 안될 때 실패(1001이 최소 길이기 때문) if l-i < 4: ch=False break # 다음 2개가 0이 아닐결우 실.. 알고리즘 문제풀이/백준 2021. 5. 7.

• [백준 2257] 화학식량 www.acmicpc.net/problem/2257 2257번: 화학식량 첫째 줄에 화학식이 주어진다. 화학식은 H, C, O, (, ), 2, 3, 4, 5, 6, 7, 8, 9만으로 이루어진 문자열이며, 그 길이는 100을 넘지 않는다. www.acmicpc.net s = input() d = { "H" : 1, "C" : 12, "O" : 16 } stack = [] for i in s: if i in d: stack.append(d[i]) elif i == "(": stack.append(i) elif i == ")": temp = 0 while True: p = stack.pop() if p == "(": break temp += p if temp == 0: continue else: stack.. 알고리즘 문제풀이/백준 2021. 5. 7.

• [백준 5347] LCM (최소공배수) www.acmicpc.net/problem/5347 5347번: LCM 첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BJ5347 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in).. 알고리즘 문제풀이/백준 2021. 5. 7.

• [백준 10610] 30 www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; public class BJ10610 { public static void main(String[] args) throws IOException { Bu.. 알고리즘 문제풀이/백준 2021. 5. 5.

• [2019 카카오 개발자 겨울 인턴십] 불량 사용자 programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr def change_v_to_bit(v): bit = "" for i in range(len(v)): bit += str(v[i]) return bit def is_in(bit): global result if bit in result: return True return False def match(ban,user): if len(ban) != len(user): return.. 알고리즘 문제풀이/프로그래머스 2021. 5. 5.

• [백준1238] 파티 www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net import heapq,sys input = sys.stdin.readline N,M,X = map(int,input().split()) INF = 987654321 graph = [[] for i in range(N+1)] for _ in range(M): s,e,w = map(int,input().split()) graph[s].append([w,e]) def f(graph,S.. 알고리즘 문제풀이/백준 2021. 5. 5.

• [백준14465] 소가 길을 건너간 이유 5 www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net import sys input = sys.stdin.readline N,K,B = map(int,input().split()) arr = [0]*(N+1) for i in range(B): arr[int(input())] = 1 s=[] cnt = 0 for i in range(N+1): cnt+=arr[i] s.append(cnt) answer = B for i in range(N+1-K): answer = min(answer,s[i+K] - s[i]) print.. 알고리즘 문제풀이/백준 2021. 5. 5.

• [백준1747] 소수&팰린드롬 www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 풀이 문제에서 요구하는대로 N보다 큰 소수를 찾고 그 소수리스트 중 팰린드롬 수를 찾으면 된다. 소수를 찾는 방법은 에라토스테네스의 체를 참고한다 에라토스 테네스의 체는 간단히 설명해서 1~N까지 반복하면서 배수들을 모두 제거하는 것이다. 소수는 어떤 숫자의 배수가 아니기 때문이다. 이렇게 소수리스트를 만든 후 찾는 범위의 숫자 중 작은것부터 하나씩 뽑아 팰린드롬인지 검사한.. 알고리즘 문제풀이/백준 2021. 5. 5.

• [백준2872] 우리집엔 도서관이 있어 www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근 www.acmicpc.net 풀이 정렬문제인줄 알고 한참 헤맸다. 또한 문제에서 요구하는대로 그대로 구현하니 시간초과가 떳다. 법칙을 찾아야한다. 45123 순서로 책이 들어온다고 하면, 45는 그대로 두고 123을 위로 올려야 할것이다. 3 2 1 순으로 뽑아야 겠지만 순서는 중요하지 않다. 책을 뽑는 횟수를 세는것이기 때문에 3개라는게 중요하다. 12453 이면 어떨까? 이것도 45만 남겨두고 나머지를 다 위로 올리는 작업을 해야.. 알고리즘 문제풀이/백준 2021. 5. 5.

• [백준3980] 선발 명단 www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 풀이 S의 ij는 i번 선수가 j번 포지션에서 뛸 떄의 능력이다 visited에 이미 방문한 포지션을 체크한다. 방문한 포지션, 자신이 뛸 수 없는 포지션을 제거하고 가능한 포지션들을 재귀적으로 호출한다. 즉, 백트래킹 기법을 사용해 모든 경우를 탐색한다. 함수의 매개변수는 (맵, 선택한 인원, 능력치합, 방문체크)로 구성한다. 시간복잡도 재귀가 최대로 깊어진다고 해보자 가능한 포지션이 최대 5개이고 11명이 있다. 그러므로 재귀는 최대 55번보단 작게 .. 알고리즘 문제풀이/백준 2021. 5. 5.

• [프로그래머스lv.3] 정수 삼각형 programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 깊이를 i 라고 봤을 때 i-1 번째 깊이엣 ㅓ어떤 숫자를 선택했느냐에 따라 결과값이 달라진다. 즉 dp 문제이다. 깊이를 i, i번째 배열에서의 인덱스를 j라고 해보자 i번째깊이의 j번째 수의 합의 최대값은 무엇일까? 답은 i-1번째 깊이의 j-1번째수까지의 최대값과 j번째수까지의 최대값중 큰 값 + i번째깊이의 j번째 수일 것이다. dp[i][j] = i번째 깊이의 j번째 인덱스가 가지는 합의 최댓값이다. 즉 dp[i][j] = max(dp[.. 알고리즘 문제풀이/프로그래머스 2021. 5. 4.

• [프로그래머스lv3] [2020 카카오 인턴십] 보석 쇼핑 programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 풀이 gems에서 보석을 차례대로 반복문에 넣는다. 큐에 차례때로 보석을 넣어준다. 또한 보석의 수를 효율적으로 계산하기 위해 dict를 따로 만들어 요소의 수를 기록한다. set을 통해 큐에 모든 보석이 들어갔는지 확인한다. 모든 요소가 들어갔다면 현재 상태를 저장한다. 나중에 답 비교를 위해 우선순위 큐에 [큐길이, 시작위치] 로 저장한다. 큐의 첫번째 보석의 수가 2 이상이라면 현재 큐를 한 번 pop를 해주고 해당 보.. 알고리즘 문제풀이/프로그래머스 2021. 5. 4.