[프로그래머스] 단어 변환 파이썬 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 가장 먼저 두 단어의 서로 다른 철자 개수를 세는 함수를 만들자 현재 단어 current에서 다른 단어로 변환하기 위해선 current와 다른 단어는 딱 1개만 서로 다른 철자를 가져야 한다. 따라서 변환할 수 있는 단어를 찾기 위해 해당 함수가 필요하다. 재귀를 돌려서 계속 words 단어 내 단어를 탐색하자 재귀 함수 종료 조건은 현재 단어 current와 target이 같을 때이다..
[프로그래머스] 소수 찾기 파이썬 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 모든 가능한 순열을 구하자 위 그림처럼 011이 입력으로 주어지면, 길이가 각 1, 2, 3인 다양한 순열이 존재한다. 순서가 중요하기 때문에 조합이 아니라 순열을 구해야 한다. 각 숫자는 문자열로 취급하므로 011이라는 것이 존재할 수 있다. 각 순열로 만들어진 숫자가 소수인지 판별하자 (with 집합) 위에서 만들어진 모든 조합을 int 타입으로 형변환하고, 이것이 소수인지 판별하자..
[백준] 4195번 친구 네트워크 파이썬 풀이
https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 1. 접근 방식 parents는 리스트 대신 딕셔너리를 사용하자. 일반적인 union-find 방식은 리스트의 인덱스를 통해 부모를 탐색하는 작업을 진행했지만, 이 문제에선 인덱스로 부모를 표현할 수 없다. 따라서 딕셔너리 자료형을 사용하여 a의 부모가 누구인지 표현하자. 이때 부모란, a가 속한 네트워크의 대장이라고 생각하면 된다. 어떤 네트워크에 속한 인원 수를 구하기 위해 딕셔너리..
[백준] 1976번 여행 가자 파이썬 풀이
https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 1. 접근 방식 도시 번호가 1부터 N까지이지만, 편의를 위해 0부터 N - 1까지로 변환하자. 도시 정보를 담은 2차원 리스트(maps)의 행과 열의 인덱스는 0부터 N - 1까지이다. 따라서 개발의 편의를 위해 도시 번호를 0부터 시작하게 변경하자. 다만 마지막에 여행 계획이 담긴 도시들의 번호는 문제에서 정한 대로 번호가 1부터 시작하므로, 그 번호에 1을 감소시킨 도시 번호로 연결 정보를 ..
[백준] 1717번 집합의 표현 파이썬 풀이
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 1. 접근 방식 union-find 방식 인덱스를 원소 값으로 갖는, 길이 (n + 1)짜리 리스트를 생성한다. 인덱스가 3이라면, 인덱스 3은 정수, list[3]은 해당 정수가 속한 집합을 의미한다. 따라서 정수 1과 3을 합치고, 정수 4와 5를 합치면 리스트는 위와 같아진다. 이처럼 여러 숫자(노드)가 있고, 두 개의 숫자를 선택하여 두 개가 같은 집합..
[백준] 1992번 쿼드트리 파이썬 풀이
https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 1. 접근 방식 문제 해결 흐름을 대략적인 슈도 코드로 파악하자. 1. is compressible? 2. if so, print 1 or 0 3. else, a. print ( b. split into 4 c. then go back to 1 d. print ) 코드를 작성하기 전에 먼저 문제를 읽으며, 어떤 흐름으로 코드를 작성해야 하는지 정리했다. 가장 먼저 압축 가능 여부를 파..
[백준] 1074번 Z 파이썬 풀이
https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 1. 접근 방식 방문하는 r행 c열이 위치하는 사분면에만 집중하자. N = 3, r = 7, c = 7일 때를 예시를 들면 다음과 같다. 7행 7열은 첫 번째 그림에서 제 4사분면에 위치한다. 따라서 나머지 제 1, 2, 3사분면에 있는 임의의 칸을 몇 번째로 방문하는지는 알 필요가 없으며, 7행 7열이 속한 제 4사분면이 48번째부터 방문한다는 사실만 중요하다. 재귀를 통해 제 4사분면..
[백준] 1991번 트리 순회 파이썬 풀이
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 1. 접근 방식 왼쪽 자식, 오른쪽 자식을 가지는 Node 클래스를 구현하자. 배열로 이진 트리를 표현하는 것보단 실제 이진 트리와 비슷하게 구현하는 편이 더 수월할 것이라고 생각했다. 따라서 실제 이진 트리의 노드처럼 왼쪽 자식, 오른쪽 자식을 갖는 Node 클래스를 작성했다. 딕셔너리로 트리를 표현하자. key는 해당 노드의 value, value는 해당 노드 인스턴스를 저장한다. ..
[백준] 10994번 별 찍기 - 19 파이썬 풀이
https://www.acmicpc.net/problem/10994 10994번: 별 찍기 - 19 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net 1. 접근 방식 가장 바깥쪽 그림을 그리는 함수를 만들자. 이 문제에서 별의 패턴은 사각형이 n번 그려진다는 것이다. 사각형 각 변의 길이는 length = 1 + (4 * (n - 1) )이다. 따라서 먼저 빈 도화지 역할로, 행과 열이 length 크기인 빈 리스트 table를 생성한다. 처음 별표(*)를 그리기 시작하는 위치(x, y)는 (0, 0)이고, 사각형의 길이는 length이다. 그림 그리는 논리는 이러하다. ① 사각형 위쪽과 아래쪽은 모두 *를 채워넣는다. 즉, table의 첫 번째 행과 마지막 행은 모든 열을..
[백준] 2730번 색종이 만들기 파이썬 정답 코드
2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 1. 문제 내용 2. 접근 방식 제 1, 2, 3, 4사분면으로 나뉘는 프렉탈 구조 데이터 리스트에서 0과 1이 모두 존재한다면, 해당 데이터 리스트를 4개의 사분면으로 나누어 각각 재귀 함수를 호출한다. 이때 사분면은 중간 인덱스 i를 기준으로 나누면 된다. 데이터 리스트가 0 또는 1로만 이루어져 있다면 각 개수를 세는 count 변수에 +1 한다. 3. 정답 코드 divide( ) : data의 제 quadrant사분면을 구한다...