본문 바로가기
728x90
반응형

파이썬438

[백준] 1629번 : 곱셈 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1629 1. 문제 설명2. 풀이과정해당 문제는 큰 수의 거듭제곱을 어떤 수로 나눈 나머지를 구하는 문제이다.거듭제곱의 최종 결과를 가지고 나머지 연산을 하면 큰 숫자일 경우 그 계산이 쉽지 않다.하여 거듭제곱을 전부 계산하기 전 작은 수일 때의 나머지 연산을 활용하여 최종 나머지 값을 구한다.A * B % C의 연산을 나눠보면 ((A % C) * (B % C)) % C의 연산과 동일한 결과가 나오게 된다.이를 활용해 거듭제곱의 나머지 연산을 구한다.문제에 나와있는 예시를 활용해 보면, 10^11 % 12 연산은 ( (10^5 % 12) * (10^5 % 12) * (10 % 12) ) % 12의 연산으로도 볼 수 있다.이를 더 작은 연산으로 나누.. 2024. 7. 9.
[백준] 1780번 : 종이의 개수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1780 1. 문제 설명2. 풀이과정해당 문제는 -1, 0, 1로 이루어진 종이를 가로로 3등분, 세로로 3등분 총 9개의 조각으로 나누며 총 -1, 0, 1로만 이루어진 종이의 개수를 구하는 문제이다.해당 종이가 -1, 0, 1의 숫자 중에서 어떻게 구성되어 있는지 판단하고 만약 각각 -1, 0, 1로만 이루어진 종이라면 각 -1, 0, 1의 종이의 개수를 세어준다.반면에 해당 종이가 -1, 0, 1의 숫자 중 두 가지 이상의 숫자로 이루어진 종이라면 다시 9개의 조각으로 나누어 다시 판별하고 해당 종이의 개수를 세어준다.해당 문제는 분할의 연장선으로 볼 수 있기 때문에 분할 정복 알고리즘으로 해결할 수 있다.종이가 어떤 숫자로 구성되어 있는지 .. 2024. 7. 8.
[백준] 1992번 : 쿼드트리 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/1992 1. 문제 설명2. 풀이과정해당 문제는 이전 "2630번 : 색종이 만들기" 문제와 매우 유사한 문제이다.0과 1로만 이루어진 영상을 각 4개의 영역으로 나누어 해당 구역을 쿼드 트리 구조를 이용하여 압축하는 문제이다.4개의 영역을 압축하여 그 결과를 차례대로 괄호 안에 묶어서 표시한다.2630번 문제와 유사하므로 동일하게 분할 정복 알고리즘으로 해결할 수 있다.해당 문제도 마찬가지로 나눈 4개의 영역이 하나의 값으로 압축되지 않는다면 다시 4개의 영역으로 나누어 압축 해야 하므로 분할 정복 알고리즘을 재귀적으로 사용하여 해결하였다. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys영상.. 2024. 7. 5.
[프로그래머스] 가장 큰 정사각형 찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 1로 이루어진 가장 큰 정사각형의 넓이를 구하는 문제이다.정사각형의 넓이를 구하는 문제이므로 한 변의 길이를 구하여 해당 정사각형의 넓이를 구한다.이 문제를 해결하기 위해 DP 알고리즘을 활용하여 시작 위치부터 마지막 위치까지 탐색하며 해당 위치까지의 가장 큰 정사각형의 한 변의 길이를 저장한다.그리고 모든 탐색이 끝난 후 가장 긴 변의 길이를 구해 제곱하여 가장 큰 정사각형의 넓이를 구한다.DP 알고리즘의 결과로 정사각형 변의 길이를 저장할 때 각 위치별 값은 해당 값의 .. 2024. 7. 3.
[프로그래머스] 리코쳇 로봇 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 말이 시작 위치에서 목표 위치까지 이동할 수 있는지, 만약 이동할 수 있다면 이동하는 최소 횟수를 구하는 문제이다.해당 문제에서 가장 중요한 부분은 말을 상, 하, 좌, 우로 이동할 때 장애물이나 벽에 부딪힐 때까지 쭉 미끄러져 이동한다는 점이다.이때 목표 위치가 있더라도 장애물이나 벽이 아니면 그냥 미끄러져 이동한다는 점이다.BFS 알고리즘을 활용하여 시작 위치에서 각 4방향으로 이동할 수 있는지 확인하고, 이동할 수 있으면 미끄러져 이동한다. 이동하면 이동한 위치에 현재.. 2024. 7. 2.
[프로그래머스] 테이블 해시 함수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 처음에 정렬만 잘해주면 나머지는 쉽게 해결할 수 있다.테이블의 튜플을 정렬할 때 기준은 2개가 있는데, col 번째 칼럼의 값을 기준으로 오름차순 정렬하고 만약 그 값이 동일하면 기본키인 첫 번째 칼럼의 값을 기준으로 내림차순 정렬한다.해당 기준으로 정렬을 하려면 거꾸로 기본키 값으로 먼저 내림차순 정렬을 하고, 이후에 col 번째 칼럼의 값을 기준으로 정렬하면 원하는 정렬 후 결과를 얻을 수 있다.테이블의 튜플을 정렬했다면 S_i를 각각 구하여 모든 S_i 결과를 XOR .. 2024. 7. 1.
[프로그래머스] 거리두기 확인하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 각 대기실에 있는 모든 응시자가 거리두기를 지키고 있는지 확인하는 문제이다.응시자 간 거리가 맨해튼 거리로 2 이하이면 안되고, 만약 거리가 맨해튼 거리로 2 이하일 경우 그 사이가 파티션으로 막혀있으면 거리두기를 지키는 것이다.모든 응시자가 거리두기를 지키고 있는지 확인하려면 응시자 간 모든 거리를 판별해야 한다.만약 두 응시자 간 거리가 2 이하라면, 두 응시자는 가로로 나란히, 세로로 나란히, 대각선으로 나란히, 총 3가지 경우 중 하나로 위치해 있을 것이다.이 3가지.. 2024. 6. 26.
[백준] 2630번 : 색종이 만들기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/2630 1. 문제 설명2. 풀이과정해당 문제는 색종이를 반으로 계속 자르면서 흰색 색종이와 파란색 색종이로 나누고 그 개수를 구하는 문제이다.색종이를 반으로만 계속 잘라 새로운 정사각형 모양의 색종이를 계속 판단하며 완전한 흰색 색종이, 파란색 색종이를 구분한다.이는 분할의 연장선으로 볼 수 있기 때문에 해당 문제를 분할 정복 알고리즘으로 해결할 수 있다.해당 문제에서 중요한 점은 매번 색종이를 반으로 나누어 새로운 정사각형 모양의 색종이를 만드는 것과 새롭게 만들어진 색종이가 완전한 흰색 색종이인지, 파란색 색종이인지, 섞여 있는 색종이인지 판별하는 것이다.하여 해당 중요한 2가지 부분을 각각 함수로 만들어 문제를 재귀적으로 해결하였다.  sy.. 2024. 6. 24.
[프로그래머스] 여행경로 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 모든 경로를 탐색하는 문제이므로 dfs 알고리즘을 활용해 해결해보고자 하였다.한 경로에서 티켓은 모두 사용해야 하며, 티켓은 한 번씩만 사용할 수 있으므로 이를 저장하기 위한 방문 리스트를 생성한다.만약 경로를 저장하는 리스트의 원소 개수가 티켓의 개수 + 1개이면(시작 ICN 포함) 모든 티켓을 한 번씩만 사용한 경로이므로 정답 리스트에 해당 경로를 추가한다.그게 아니라면 티켓을 인덱스를 붙여 하나씩 불러오고 현재 위치에서 출발하는 티켓 중 아직 사용하지 않은 티켓이면 해.. 2024. 6. 15.
[백준] 13305번 : 주유소 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 https://www.acmicpc.net/problem/13305 1. 문제 설명2. 풀이과정해당 문제는 전형적인 그리디 알고리즘 문제라고 볼 수 있다.제일 왼쪽 도시에서 제일 오른쪽 도시로 가는데 최소 비용을 구하면 되는 문제이다.제일 왼쪽 도시에서 출발하여 주유를 하며 오른쪽 도시로 이동하면 되는데, 이때 2가지 경우가 존재한다.만약 해당 도시의 기름값이 제일 오른쪽 도착 도시를 제외한 나머지 도시의 기름값 중 최솟값이면 해당 도시에서 이동하려는 거리만큼 기름을 전부 넣으면 된다.반면에 해당 도시의 기름값이 최솟값이 아니라면 현재 도시 이후의 도시들 중 현재 도시의 기름값보다 낮은 기름값을 갖는 도시까지만 이동하고 또 기름을 넣어야 최소 비용으로 이동할 수 있다.이를 활용하면 최소 비용으로 제일 오.. 2024. 6. 8.
728x90
반응형

티스토리툴바