본문 바로가기

Algorithm problems, coding test/백준

 (6)
[백준][10451][S2] 순열 사이클 기본적인 DFS 문제이며, 연결된 부분집합의 개수(사이클)을 세는 문제이다. DFS를 한 번 호출할 때마다 count를 1씩 올려서 개수를 센다. import sys T = int(sys.stdin.readline()) for i in range(T): N = int(sys.stdin.readline()) graph = list(map(int, sys.stdin.readline().split())) #graph는 1번 인덱스부터 사용한다. 0번은 더미 데이터를 넣어주자. graph.insert(0, 99999) #방문 기록 visited = [False for i in range(N+1)] visited[0] = True #---------------------------------------------..
[백준][11724][S2] 연결 요소의 개수 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 기본적인 DFS 알고리즘에 "연결 요소의 개수"를 세는 기능을 추가한다. DFS가 한 번 호출될 때 마다 연결 요소는 하나씩 늘어나게 만들면 된다. import sys sys.setrecursionlimit(5000) N,M = map(int, sys.stdin.readline..
[백준][1259][B1] 펠린드롬수 문제 어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다. 'radar', 'sees'는 팰린드롬이다. 수도 팰린드롬으로 취급할 수 있다. 수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬수다. 121, 12421 등은 팰린드롬수다. 123, 1231은 뒤에서부터 읽으면 다르므로 팰린드롬수가 아니다. 또한 10도 팰린드롬수가 아닌데, 앞에 무의미한 0이 올 수 있다면 010이 되어 팰린드롬수로 취급할 수도 있지만, 특별히 이번 문제에서는 무의미한 0이 앞에 올 수 없다고 하자. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. 출력 각 줄마다 주어..
[백준][1181][S5] 단어 정렬 문제 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. 출력 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. 사실 간단한 구현 문제는 머리를 쓰지 않아도 어떻게든 구현은 할 수 있다. 단지, 숙련도에 따라 코드를 얼마나 효율적으로 작성할 수 있는지가 문제이다. 따라서 직접 구현할 수도 있었지만, 다른 사람이 어떻게 효율적으로 코드를 구현하였..
[백준][1018][S5] 체스판 다시 칠하기 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8..
[백준][1157][B1] 단어 공부 [문제] 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. [입력] 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다. [출력] 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다. 파이썬 숙련도에 따라 코드가 천차만별로 변할 수 있는 문제이다. 그동안 배운 문법으로 구현해보자. answer = '' S = input() S = S.upper() alpha_list = ['A','B','C','D','E','F','G','H','I','J','K..

티스토리툴바