전체 글

💻 Problem문제 보러 가기 당신은 N개의 반지를 가지고 있다. 각각의 반지는 대문자 10 문자로 이루어진 문자열이 새겨져 있다. 반지는 문자열의 시작과 끝이 연결된 형태로 문자가 새겨져 있다. 반지에 각인된 문자열을 거꾸로 읽는 걱정은 없다.찾고자하는 문자열이 주어졌을 때 그 문자열을 포함하는 반지가 몇 개인지를 발견하는 프로그램을 작성하라. ✏️ Solution 1import sysinput = sys.stdin.readlinefind = input().rstrip()n = int(input())length = len(find)cnt = 0for _ in range(n): ring = input().rstrip() for i in range(len(ring)): targe..

💻 Problem문제 보러 가기 김한양은 마지막에 남은 한 명과 같이 해야 한다.학생들은 모두 자신의 최애의 팀원을 찾기로 했다. 김한양을 제외한 N명의 학생들은 일렬로 선 다음, 가장 앞에 선 학생부터 자신의 최애의 팀원을 한 명씩 찾아간다. 최애의 팀원을 찾는 방법은 다음과 같다.가장 앞에 선 학생은 뒤돌아 서서 나머지 학생들을 마주본다. 마주보고 있는 학생들 중 가장 앞 사람(즉, 현재 팀원을 찾고 있는 학생과 가장 가까운 학생)이 자신의 팀원이면 둘이 손을 잡고 떠난다. 만약, 자신의 팀원이 아니면 "패스"를 외친다. "패스"를 외치면 팀원 후보 중 가장 앞 사람은 한 바퀴 돌아서 다시 줄의 맨 끝에 서면 된다. 가장 앞에 선 학생의 학번 마지막 두 자리가 X일 때, 이 학생의 팀원은 X−1명의..

💻 Problem문제 보러 가기 상훈이는 N개의 선물 상자를 가지고 있다. 선물 상자에는 현재 담겨있는 선물의 개수가 적혀있다.선물을 받을 아이들이 M명 있다. 아이들은 각자 1에서 M까지의 서로 다른 번호를 하나씩 부여받았다. 1번 아이부터 M번 아이까지 한 번에 한 명씩, 현재 선물이 가장 많이 담겨있는 상자에서 각자 원하는 만큼 선물을 가져간다. 이때, 앞서 누군가 선물을 가져갔던 선물 상자에서 또다시 가져가도 상관없다.하지만 상자에 자신이 원하는 것보다 적은 개수의 선물이 들어있다면, 선물을 가져가지 못해 실망한다.상훈이는 한 명이라도 실망하지 않고 모두가 선물을 가져갈 수 있는지 궁금하다. 💡 Approachheapq 모듈을 활용하여 최대 힙을 구현했다.최대 힙의 경우 최소 힙과 동일하게 구..

💻 Problem문제 보러 가기 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다. 💡 Approachheapq 모듈 활용하여 최소 힙을 구현했다. ✏️ Solutionimport sysimport heapqinput = sys.stdin.readlinen = int(input())heap = []for _ in range(n): x = int(input()) if x == 0: print(heapq.heappop(heap) if heap else 0) else: ..

💻 Problem문제 보러 가기 화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.자주 나오는 단어일수록 앞에 배치한다.해당 단어의 길이가 길수록 앞에 배치한다.알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자. 💡 Approach먼저 딕셔너리에 단어와 그 단어의 빈도수를 저장했다.그 후 sorted 함수..

💻 Problem문제 보러 가기  가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.  💡 Approach아래는 백준 예제 입력을 기반으로 그린 그래프의 모습이다.그림으로 보면 각 노드가 어떻게 이어져있는지 더 쉽게 이해할 수 있다. 플로이드 워셜 알고리즘으로 풀었다.플로이드 워셜의 키워드는 경출도!!3중 for문을 경유지-출발지-도착지 순으로 적어야 한다. 처음 입력받은 인접 행렬에는 직접적으로 이어지는 간선이 존재하는지 저장되어 있다.이 인접 행렬에서 간접적으로 이어지는지(경유지를 통해)를 업데이트하면 그게 정답이다. 출발지와 경유지가 이어져있고 경유지와 도착지가 이어져있으면 출발지에서 ..

💻 Problem문제 보러 가기  방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.  💡 Approach간선 정보(간선의 양 끝점)를 입력받고 있기 때문에 간선 정보를 가지고 graph를 만들어야 한다.만든 그래프를 바탕으로 정점 1부터 그래프 탐색을 시작한다. 만약 연결 요소가 하나인 그래프라면 첫 탐색에서 모든 정점에 방문 처리가 됐을 것이다.하지만 연결 요소가 2 이상인 그래프라면 첫 탐색 이후에 방문 처리가 되지 않은 정점이 있을 것이다.그렇게 방문 처리 되지 않은 정점을 찾아서 해당 정점을 기준으로 그래프 탐색을 하는 것을 반복하여 그래프 탐색을 몇 번했는지 세면 된다. 아래는 연결 요소에 대한 이해를 돕기 위한 필기이..

💻 Problem문제 보러 가기 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 💡 Approach처음에 생각이 잘 안 났다..그리디인 줄도 몰랐는데 모든 경우의 수를 따지는 게 아니라 괄호가 들어가야 하는 최선의 선택만을 따져야 해서 그리디인 것 같다. 문제의 목표는 식의 값을 최소로 만드는 것이다.식의 값을 가장 작게 만들기 위해서는 최대한 큰 수를 빼야 한다.즉, '-' 뒤에는 항상 괄호를 치는 것이 좋다. 예를 들어, 5+4-5-10+20 라는 식이 주어졌다고 치자.가장 작은 수를 만들기 위..