끄적끄적 개발로그

📖 문제 링크 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net ✅ 최종 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(2000) t = int(input()) def dfs(x): check_dfs[x] = True for i in arr[x]: if check_dfs[i] == False: dfs(i) f..

📖 문제 링크 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 👩‍💻 문제풀이 처음엔 DP문제라고 생각하고 풀었는데, 가뜩이나 잘 못하는 DP인 데다 정답도 나오지 않았다. 찾아보니 BFS 활용문제.... BFS는 더 못해서 산 넘어 산^^.. 각종 블로그를 통해 정답코드를 분석해봐도 너무나도 방대한 양으로 진행되어 파악 불가...... 그래서 BFS 기본코드를 디버깅하면서 돌아가는 모습을 확인했다. # bfs 기본 ..

📖 문제 링크 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 👩‍💻 문제풀이 백준 2630 - 색종이 만들기 문제를 먼저 풀면 쉽게 해결할 수 있다. 2630번은 각 변을 2개로 나눠가는 문제였다면, 본 문제는 3개로 나눈다. 9사분면을 만들 수 있도록 행렬을 나눠주면 쉽게 해결 가능! ✅ 최종 코드 import sys input = sys.stdin.readline n = int(input()) paper = [list(map(i..

📖 문제 링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 👩‍💻 문제풀이 이분 그래프란 간단히 말해서, 한 간선의 양쪽 정점이 각각 다른 색(그룹) 이어야 한다는 것! 아래의 두 그래프를 보자. 왼쪽 그래프는 한 간선에 빨강, 파랑 점이 하나씩 연결된 반면(이분그래프), 오른쪽 그래프는 주황색 화살표가 가리키는 간선이 빨강-빨강 점으로 연결된 것을 알 수 있다(이분 그래프가 아님). 이러한 특징을 염두에 두고 DFS로 풀이를 시작했지만 도..

📖 문제 링크 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 👩‍💻 문제풀이 일반적인 DFS, BFS문제였고, 연결된 그래프의 개수를 찾아 카운트해주면 되는 간단한 문제였다. 하지만 런타임 에러 때문에 원인을 찾느라 오래 걸렸다. 배열의 인덱스 문제도 아니었고, 정답도 vscode에서는 정확히 나오고 있었기에 구글링을 시도.. 파이썬은 재귀제한이 걸려있기 때문에 재귀 허용치를 넘어..

📖 문제 링크 https://www.acmicpc.net/problem/11576 11576번: Base Conversion 타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 www.acmicpc.net 👩‍💻 문제풀이 문제 이해가 안되서 한참을 들여다봤다. 질문도 많은걸 보니 좀 불친절한 문제인듯하다...^^;; 어쨌든 간단히 입력된 값을 설명해보자면 아래와 같다. 첫번째 줄 : A는 17진법, B는 8진법을 사용한다. 두번째 줄 : A진법으로 나타낸 수의 자리수는 2개(ex. 216(17)일때 2와 16이라는 두개의 숫자로 이루어져있다는 말) 세번째 줄 : 자리..

📖 문제 링크 https://www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 👩‍💻 문제풀이 파이썬 int함수에는 10진법 변환 기능이 있다. int(문자열로 변환된 숫자, 해당 숫자의 진법) 을 넣으면 10진법으로 변환된다. print(int('1010', 2)) 위와 같이 입력하면 10이 출력된다. 1010(2)를 10진법으로 변환한 수다. 문제의 조건은 2진수를 10진수가 아닌 8진수로 변환하는 프로그램이므로, 파이썬의 oct함수를 다시한번 사용한다. 여기서 파이썬 진법 함수 정리! bin() : 2진수 oct() : 8진수 hex() : 16진수 2진수 ..

📖 문제 링크 https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 👩‍💻 문제풀이 진법변환2(11005번)문제를 거꾸로하면 된다고 생각했는데, 생각보다 오래걸린 문제이다. 이렇게 10진법으로 돌려놓는 방식을 그대로 구현했다. 다만 문자열인지 숫자인지 구분하기위해 isdigit()함수를 사용하였고, 문자열인 경우 55를 빼주어 문제의 조건을 맞추었다. ✅ 최종 코드 from curses.ascii import isdigit n, b = input()...

📖 문제 링크 https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 👩‍💻 문제풀이 맞긴 맞았는데, 속도가 느려서(140ms가 나옴) 다시 풀어본 문제이다. 비슷한 풀이라고 생각했는데, 다른 풀이와 속도가 2배 정도 차이가 난다. 처음 코드는 알파벳 대문자를 리스트로 먼저 만든 후 진행했다. (ascii_uppercase 사용) 다른 분들의 풀이를 보니 리스트로 만들지 않고, 나머지를 구함과 동시에 아스키코드로 계산해 바로 배열에 넣어주었다. ..

📖 문제 링크 https://www.acmicpc.net/problem/9613 9613번: GCD 합 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진 www.acmicpc.net 👩‍💻 문제풀이 수를 배열에 입력받고, 모든 쌍의 경우의 수를 조회하기 위해 이중 for문을 만들었다. for문이 돌아갈때마다 gcd를 구하고, 합을 sum에 저장한 후 출력! ✅ 최종 코드 from math import gcd t = int(input()) arr = 0 sum = 0 while t!=0 : arr = list(map(int, input()...