buzz

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 해설 지도 내에서 칸이 1이면 이동한다. 이동을 하면 그 전 칸의 이동한 값에 +1을 해준다. 코드 -파이썬 #백준 2178(미로 탐색) import sys input = sys.stdin.readline from collections import deque n, m = map(int, input().split()) graph = [] for i in range(n): graph.append([*map(int, str(in..

문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 해설 이 문제는 설탕을 5의 배수로 만들 수 있느냐 없느냐를 가지고 접근하면 된다. 5의 배수가 아니라면 3씩 빼줘서 5의 배수로 맞추면 되는데 설탕이 5의 배수로 맞춰지지 않고 음수가 되어버리면 5와 3으로 나눠 떨어지지 않는 것이기 때문에 -1을 출력해주면 된다. 코드 -파이썬 #백준 2839(설탕 배달) sugar = int(input()) #설탕 무게 bag = 0 #봉지 개수 while sug..

문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 가장 기본적인 dfs/bfs 문제들은 visited 배열을 만들어서 방문 여부를 저장하는데 이 문제는 그 대신 부모 노드를 저장하면 된다. 그 외에는 다른 그래프 탐색 문제 풀 듯 풀면 된다. 코드 -파이썬 #백준 11725(트리의 부모 찾기) ##dfs 풀이 import sys input = sys.stdin.readline sys.setrecursionlimit(1000000) n = int(input()) graph = [[] for _ in ..

문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 해설 누적합을 저장할 리스트를 만들고 0 ~ i까지의 누적합을 계산해 저장한다. a~b까지의 구간 합은 b까지의 누적합과 a까지의 누적합을 뺀 것이기 때문에 누적합만 계산해서 넣어두면 쉽게 풀 수 있다. 리스트에 0을 미리 넣어두면 인덱스를 헷갈리지 않고 풀 수 있다. 코드 -파이썬 #백준 11659(구간 합 구하기 4) import sys input = sys.std..

문제 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 해설 처음엔 아무 생각 없이 '('의 개수와 ')'의 개수를 세서 같으면 YES, 다르면 NO를 출력했었는데 그러면 안된다. ')'이 '('보다 먼저 있으면 괄호가 제대로 닫기지 않기 때문이다. 짝을 맞춰보려면 '('이 나왔을 경우 스택에 넣어주고 ')'이 나오면 스택에 들어있던 '('을 pop해준다. 대신 스택에 아무것도 없는데 ')'이 나오면 더이상 볼 것도..

문제 https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 프로그램은 표준입력을 사용한다. 테스트케이스의 개수는 입력의 첫 번째 줄에 주어진다. 각 테스트케이스는 한 줄에 자연수 K (3 ≤ K ≤ 1,000)가 하나씩 포함되어있는 T개의 라인으로 구성되어 www.acmicpc.net 해설 triangle 리스트에 삼각수를 1000을 넘지 않는 삼각수를 구해 미리 넣어놓고 그 중 3개의 합으로 구성된 수를 찾으면 된다. 코드 -파이썬 #백준 10448(유레카 이론) import sys input = sys.stdin.readline triangle = [n*(n+1)//2 for n in range(1, 46)] #45번째 삼각수 == 1035 eureka = [..

문제 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 해설 이 문제는 좌표를 dx, dy에 저장하고 dfs 혹은 bfs로 풀면 된다. 좌표를 이용한 그래프 탐색 문제는 처음 풀어서 어떤 식으로 풀어야 하는지 당황스러웠는데 이런건 가장 이해하기 쉽게 푼 다른 사람 코드를 보고 외우는게 최고인 것 같다. 코드 -파이썬 #백준 4963(섬의 개수) # 1 : 땅, 0 : 바다 #dfs 풀이 import sys input = sys.stdin.r..

문제 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 해설 처음에는 밑의 주석처리 된 시간 초과 코드 처럼 풀면 쉽게 해결될 거라고 생각했다. 그치만 이중 반복문을 쓰면 시간복잡도가 O(n^2)이 되어 시간 초과가 난다. 이 문제는 투포인터 문제로 리스트의 가장 처음(0)과 가장 마지막(n-1)을 각각 포인터로 설정해 위치를 옮겨가면서 원하는 값을 구하면 된다. left 위치와 right ..

문제 https://www.acmicpc.net/problem/2605 2605번: 줄 세우기 점심시간이 되면 반 학생 모두가 한 줄로 줄을 서서 급식을 탄다. 그런데 매일 같이 앞자리에 앉은 학생들이 앞에 줄을 서 먼저 점심을 먹고, 뒷자리에 앉은 학생들은 뒤에 줄을 서 늦게 점심을 www.acmicpc.net 해설 이 문제의 핵심은 뽑은 번호대로 그 위치에 줄을 선다는 것이다. 리스트의 insert()를 이용하면 특정 위치에 요소를 삽입할 수 있다. 번호의 순서가 제일 오른쪽이 가장 빠른 번호가 위치 하기 때문에 리스트를 역순으로 뒤집어서 출력해주면 끝이다. 코드 -파이썬 #백준 2605(줄 세우기) n = int(input()) #학생 수 num = [*map(int, input().split())..

문제 https://www.acmicpc.net/problem/2810 2810번: 컵홀더 첫째 줄에 좌석의 수 N이 주어진다. (1 ≤ N ≤ 50) 둘째 줄에는 좌석의 정보가 주어진다. www.acmicpc.net 해설 SLLLLSSLL을 나눠서 보면 S / LL / LL / S / S / LL로 나눌 수 있다. S는 한 좌석에 컵홀더 1개, L은 두 좌석에 컵홀더 1개. 그렇다면 * / S* / LL* / LL* / S* / S* / LL* 로 표현할 수 있다. 결국 S는 1개당 컵홀더 1개 더해주면 되고, L은 L//2개당 컵홀더 1개를 더해주면 된다. 가장 왼쪽의 첫번째 컵홀더도 빼먹으면 안된다. 총 컵홀더의 개수를 구하고 나면 컵홀더와 사람 수 둘 중 작은 값을 출력해주면 된다. 문제에서 물어..