Algorithm

[문제] https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net [풀이] main 함수 graph = [[] for _ in range(n+1)] # print(graph) -> [[], [], [], [], [], []] 양방향 노드로 그래프를 만들어준다. 여기서 범위가 n+1인 이유는 노드의 번호가 0이 아닌 1부터 시작하기 때문이다. for i in range(m): a, b = map(int, s..

[문제] www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net [풀이] 처음에는 부분성공 코드로 제출한 후 아무리 생각해도 답을 모르겠어서 다른 사람 풀이를 찾아봤다. 성공한 코드는 문자열을 만들어서 비교하지 않고 s 내부에서 패턴을 찾아 비교하는 풀이이다. 풀이 중 이해가 안돼서 고민하던 부분을 주석에 숫자로 남겨놓았는데 1. cnt -= 1 : 일치할 경우 첫 번째 'IOI' 패턴 이후부터 검..

[문제] https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net [풀이] 2021.08.11 - [BOJ] - [Python] BOJ/백준 2630번 색종이 만들기 [Python] BOJ/백준 2630번 색종이 만들기 [문제] https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. ..

[문제] https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net [풀이] 분할 정복법 : 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복(Conquer) 우선 트리의 자식 노드가 4개씩 분할하는 방법을 쿼드 트리라고 한다. 작게 분할한 색종이 안에서 같은 색인지를 판단해 같지 않다면 다시 나누는 과정을 반복한다. 첫 번째 나오는 색을 color에 저장한 후 색종이를 돌면서 전체 색이 전부 ..

[문제] https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net [풀이] 2개의 리스트의 중복되는 이름을 구하는 문제이다. 이는 교집합을 구하면 쉽게 풀릴 것 같아서 set 자료형으로 풀었다. 듣보잡 명단인 result는 sorted( list( 듣도 못한 사람 & 보도 못한 사람 ) )로 구한 후 result의 길이를 출력, result를 차례대로 출력한다. sys.stdin.readline()[:-1] sys.stdin.readline().str..

[문제] https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net [풀이] 2021.08.09 - [BOJ] - [Python] BOJ/백준 2805번 나무 자르기 [Python] BOJ/백준 2805번 나무 자르기 [문제] https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,00..

[문제] https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net [풀이] 같은 코드여도 pypy3로 하면 맞는데 python3로 하면 다 시간 초과 오류 떴다.. 처음에는 brute force로 푸는 줄 알고 우왕 쉽다 하면서 풀었는데 시간 초과가 떠서 이건 이렇게 간단하게 풀 문제가 아니라는 걸 직감했다. -> 이분 탐색으로 풀어야 한다 가장 짧은 나무의 길이를 1을 start로, trees 중 가장 큰 값을 ..

[문제] https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net [풀이] 산술평균, 중앙값, 범위 구하는 법은 쉬워서 패스.. 최빈값 구하는 게 아주 조금 까다로웠다. 처음에 입력 받을 때 sorted함수를 통해 차례대로 정렬한 상태로 리스트에 저장한다. num_cnt 딕셔너리를 생성한 후 try-except문을 활용해 num_cnt에 숫자 당 빈도수를 저장했다. for문으로 num에 있는 숫자를 차례대로 꺼내 num_cnt[i] += 1을 하게 되면 num_cnt..

[문제] https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net [풀이] 문자열을 sentence 변수에 저장한다. sentence에 있는 문자 하나씩 검사한다 문자가 '(' 이거나 '[' 인 경우 (열린 문자일 경우) stack 리스트에 문자를 추가한다. 문자가 ')' 인 경우 stack 리스트가 empty이거나 stack의 마지막 원소를 꺼냈을 때 '['인 경우 flag를 False로 변환 break로 반복문 나옴 stack의 마지막..