[c++] 백준 2504 : 괄호의 값 난이도 🥈실버1 https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net ‘()’ 인 괄호열의 값은 2이다. ‘[]’ 인 괄호열의 값은 3이다. ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다. ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다. 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다. 접근1 (()[[]])([]) (()[[]]) -> 2*(2 + (3*..
[c++] 백준 10799 : 쇠막대기 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 접근 1. (은 막대가 하나씩 쌓인다고 생각한다. 스택에 값을 push한다. 2. )가 올 때, 스택 맨위에 (가 있을 경우에는 레이저로 취급된다. 이때 스택에 있는 (의 개수 만큼 막대 개수가 추가된다. size() 메서드를 이용한다. 3. 그냥 )가 오는 경우 막대 개수가 하나만 추가된다. 또한, 입력받은 문자열의 특정 인덱스에서 )가 나타날 때 그 앞 인덱스의 값..
[파이썬] 백준 3020 : 개똥벌레 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 난이도 : 골드 5 누적합 종유석(천장에 박힌 것) 석순(바닥에 박힌 것)이 특정 높이에 있을 때의 누적합을 구해야 한다. 예제 입력 1을 예시로 석순 부분만 그림으로 나타내면 다음과 같다. 개똥벌레가 파괴해야하는 장애물이 가장 많은 구간은 높이가 1일 때의 구간이다. 총 3개의 석순을 부숴야 한다. 높이가 2, 3인경우 2개의 석순을, 높이가 4, 5인 경우 1..
https://www.acmicpc.net/problem/11721 11721번: 열 개씩 끊어 출력하기 첫째 줄에 단어가 주어진다. 단어는 알파벳 소문자와 대문자로만 이루어져 있으며, 길이는 100을 넘지 않는다. 길이가 0인 단어는 주어지지 않는다. www.acmicpc.net Key point for문의 step기능을 활용하면 10개씩 끊어서 index값을 받을 수 있다. 슬라이싱 기능을 활용하여 변환된 index값을 10개씩 출력하도록 하면 된다. (슬라이싱 범위가 입력받은 문자열의 길이를 벗어나도 인덱스 에러가 나지 않는다. 아래 링크 참조) https://dallae7.tistory.com/112 코드 import sys word = sys.stdin.readline().rstrip() for..
[python] 백준 1783 : 병든 나이트(자세한 풀이) 1783번: 병든 나이트 (acmicpc.net) 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 실버 4 그리디 접근 가로가 M, 세로가 N이다. N의 크기에 따라 나이트가 이동할 수 있는 경우의 수가 제한이 되는 부분이 있기 때문에 bfs대신 그리드를 경우의 수에 따라 나눠서 적용하는 방법을 사용해야 한다. 문제 조건에 따라 나이트가 이동할 수 있는 경우의 수는 다음과 같이 4가지이다. 문제 조건을 읽어보면, 나이트의 초기 위치는 반드시 맨 왼쪽 아래 구석에 있기 때문에 세로 N의 길이에 따라 나이트의 이동 패..
[python] 백준 1543 : 문서 검색 1543번: 문서 검색 (acmicpc.net) 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한 www.acmicpc.net 실버 4 브루트포스, 그리디, 문자열 접근 예제 입력1을 예시로 접근해보자. ababababa aba 첫줄에 입력한 글자를 인덱스 0부터 끝까지 탐색할 필요가 없다. aba라는 3글자가 첫줄에 입력한 문자열에 존재하는지 확인하는 것이기 때문에 맨 처음 인덱스부터 맨 끝에서 세번째 인덱스까지 탐색하면 된다. 따라서 for i in range(len(문자열변수) - len(찾을 ..
[python] 백준 1049: 기타줄 1049번: 기타줄 (acmicpc.net) 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 실버 4 그리디 접근 먼저 기타줄의 브랜드가 여러개가 입력되었다면, 낱개 값의 가장 싼 값과 한팩 값의 가장 싼 값을 입력한 리스트로부터 골라낼 수 있어야 한다. 골라낸 두 값을 가지고 다음의 분기를 결정한다. 기타줄 낱개 가격 * 6 < 기타줄 팩이라면 무조건 낱개로만 기타줄을 사는게 싸게 친다. 그런데 기타줄 팩 하나를 사는게 더 이득이라면 최대한 기타줄 팩으로 많이 구입..
[python] 백준 10610 : 30 10610번: 30 (acmicpc.net) 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 실버 5 그리디 접근 N의 입력값 크기나 너무나 크기 때문에 안의 숫자들을 어떻게 바꿔야할지 고민이 많았는데 그냥 다음의 조건들을 참고하면 쉽게 풀 수 있었다. N이 3의 배수임을 확인하는 법 : 각 자릿수의 총합이 3의 배수면 N은 3의 배수이다. 30의 배수를 찾아야 하기 때문에 N의 숫자 중에 0이 없으면 -1을 출력하도록 한다. 두 조건을 만족하는 숫자는 순서를 바꾸어도 3..
[python] 백준 1697 : 숨바꼭질 1697번: 숨바꼭질 (acmicpc.net) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 실버 1 그래프, BFS 접근 일차원으로 이동할 수 있는 bfs문제이다. 5를 노드라고 생각했을 때, 5가 탐색할 수 있는 노드는 4, 6, 10이된다. 각각의 노드는 [3, 5, 8], [5, 7, 12], [9, 11, 20]을 탐색할 수 있을 것이다. 여기서 미리 방문했던 노드는 방문하지 않도록 해야하며 노드가 일차원 이동을 하기 때문에 문제..
[python] 백준 1325 : 효율적인 해킹(BFS) 1325번: 효율적인 해킹 (acmicpc.net) max_hack: max_hack = h hack.append([i, h]) for i, cnt in hack: if cnt == max_hack: print(i, end = ' ') 어차피 1번부터 n번까지의 노드를 돌아가면서 bfs를 돌리기 때문에 나오는 순서대로 최댓값에 해당하는 노드를 출력하면 된다.
[python] 백준 1743 : 음식물 피하기(BFS) 1743번: 음식물 피하기 (acmicpc.net) 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 실버 1 그래프, BFS 접근 이차원 배열을 사용하여 그래프를 구성하고 좌표를 한칸씩 이동하면서 음식물의 크기를 계산한다. bfs탐색이 끝나면 해당 음식물의 크기에 대한 계산이 끝난 것과 같으므로 각 bfs탐색의 반환값중 가장 큰 값을 출력하도록 한다. 코드 import sys; input = sys.stdin.r..
[python] 백준 18352 : 특정 거리의 도시 찾기 18352번: 특정 거리의 도시 찾기 (acmicpc.net) 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 실버 2 그래프, BFS 접근 단방향 그래프 구현과 특정 정점으로부터의 거리를 구현할 수 있으면 쉽게 풀 수 있는 문제이다. 코드 import sys; input = sys.stdin.readline from collections import deque def bfs(no..
