728x90 반응형 파이썬438 [백준] 25682번 : 체스판 다시 칠하기 2 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 http://https://www.acmicpc.net/problem/2568 1. 문제 설명2. 풀이과정해당 문제가 누적합 문제로 분류되어 있길래 어떻게 누적합으로 해결할 수 있을지 고민을 해보았지만 쉽게 해결방법이 떠오르지 않았다.이전 체스판 다시 칠하기 문제를 기억해 보면 기본적으로 체스판은 제일 위쪽 첫 번째 칸이 검은색인지, 흰색인지에 따라 2가지 경우를 고려해야 한다는 것을 알 수 있다.그리고 각 체스판의 칸에 대해 살펴보면 행 인덱스와 열 인덱스의 합이 짝수이면 시작 칸의 색과 동일해야 하고, 홀수이면 시작 칸의 색과 다른 색이어야 한다.이를 통해 각 2가지 체스판과 주어진 보드를 비교하여 색을 다시 칠해야 하는 부분과 칠하지 않아도 되는 부분을 구별한다. (구별은 칠해야 하면 1, 칠하지 .. 2024. 6. 2. [프로그래머스] 미로 탈출 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정미로를 최적의 경로로 탈출하는 문제는 대부분 BFS 알고리즘으로 해결할 수 있다.해당 문제는 레버가 존재하는데, 이 때문에 BFS 알고리즘을 두 번 사용해야 한다.우선 레버를 먼저 당겨야 하므로 시작 위치부터 레버의 위치까지 이동하며 최적의 경로를 찾고, 다음으로 레버의 위치부터 출구의 위치까지 이동하며 최적의 경로를 찾아 두 최적의 경로를 합산하여 최종 결과를 도출한다.두 가지 경로 중 하나라도 결과가 나오지 않는다면 미로를 탈출할 수 없다는 것이다. BFS 알고리즘을 구현한 함수에서.. 2024. 5. 26. [프로그래머스] 행렬 테두리 회전하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 알고리즘을 사용하지 않고 우선 차근차근 문제를 살펴보며 문제에서 실행되는 행동을 그대로 동작할 수 있도록 코드를 작성해 본다.초기 행렬을 생성하는 함수, 회전하는 숫자들의 리스트를 생성하고 최솟값을 구하는 함수, 행렬을 회전 이후 행렬로 수정하는 함수를 각각 생성하여 활용한다. 초기 행렬을 생성하는 함수를 정의한다. def createMatrix(matrix)한 행에 해당하는 리스트를 저장할 리스트를 생성한다. li = list()숫자는 1부터 주어진 행과 열의 곱까지 들어.. 2024. 5. 19. [프로그래머스] 수식 최대화 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 각 +, -, * 연산자의 우선순위에 따라 수식을 계산한 결과 중 절댓값이 가장 큰 값을 출력하는 문제이다.3 연산자의 우선순위 조합에는 총 6가지 경우가 존재하고 각 경우에 따른 수식을 계산하고 그 절댓값을 구한다.6가지 경우의 절댓값 중 가장 큰 값을 출력하면 된다.+, -, * 연산자에 따른 수식 연산을 진행할 함수 3개를 생성하여 각 연산자에 따른 수식을 계산한다.처음에 수식 문자열을 숫자와 연산자로 구분해 주기 위한 함수를 생성하여 최초의 수식을 분리하여 연산을 수.. 2024. 5. 11. [프로그래머스] 괄호 변환 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 올바르지 않게 되어 있는 괄호를 올바르게 만들어야 하는 문제이다.문제에 나와있는 것처럼 우선 문자열을 나누고 앞부분의 문자열이 올바른 괄호이면 뒷부분의 문자열만 확인한다.앞부분의 문자열이 올바르지 않은 괄호이면 위에서 설명한 방법으로 괄호를 올바르게 수정한다.설명에 따라 문제를 해결하기 위해 총 4가지 동작이 반복되는데, 우선 문자열을 2개로 나누는 동작이 필요하고, 나눈 문자열에서 앞부분의 문자열이 올바른 괄호인지 확인하는 동작이 필요하다.또한 올바른 괄호가 아닐 때 괄호.. 2024. 5. 5. [프로그래머스] 가장 먼 노드 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 경로를 통해 노드를 탐색하며 1번 노드에서 각 노드까지 최단거리를 구한 뒤, 가장 멀리 떨어진 노드의 개수를 구하면 되는 문제이다.1번 노드에서 각 노드까지 최단거리를 구하기 위해 BFS 알고리즘을 활용하여 각 노드를 탐색해 나간다.연결된 노드를 탐색하며 다음 노드에서 최단거리는 이전 노드에서 최단거리에 1을 더해주면 된다.거리를 저장할 리스트를 생성하고 연결된 노드를 탐색해 나갈 때마다 다음 노드에서의 최단거리를 저장해 나간다. BFS 알고리즘을 활용할 때 deque 자료.. 2024. 5. 4. [프로그래머스] 섬 연결하기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 모든 섬이 이어질 때 그 비용이 최소가 되어야 한다.비용이 최소가 되어야 하므로 그리디 알고리즘을 활용하여 비용이 작은 것부터 섬을 연결하면 된다.하지만 여기서 섬들을 연결할 때 사이클이 존재하면 안 되기 때문에 이를 방지하고자 크루스칼 알고리즘을 활용하여 문제를 해결한다. 이를 유니온 파인드(union-find) 알고리즘으로 해결한다. 유니온 파인드 알고리즘은 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속.. 2024. 4. 28. [프로그래머스] 줄 서는 방법 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 가능한 모든 조합 중에서 k번째의 조합을 출력하는 문제이다.간단하게 순열을 생각하여 permutations() 함수를 사용해 모든 조합을 구한 뒤, k번째 조합을 출력하면 효율성에서 에러 즉, 시간초과가 발생하게 된다.하여 다른 방법으로 문제를 해결하기 위해 생각하던 중, 해당 자릿수는 각 n과 k의 값에 따라 n의 팩토리얼 값에 관련이 있다는 것을 알아냈다. k를 n - 1에서부터 0까지 각 팩토리얼 값으로 나눈 몫에 해당하는 숫자를 정답 리스트에 추가해 나가면 된다.이후.. 2024. 4. 25. [프로그래머스] 배달 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 1번 마을에서 각 마을까지 배달하는데 최소 시간을 모두 구하고 구한 최소 시간이 주어진 제한 시간 K보다 작거나 같은 마을의 개수를 세어주면 된다.해당 문제를 해결하기 위해서 다익스트라 알고리즘을 활용한다.다익스트라 알고리즘을 실행할 때 방문하지 않은 인접 노드를 방문하는 부분이 있는데, 이 부분에서 우선순위 큐를 사용하면 현재까지 발견된 가장 짧은 거리의 노드에 대해서 먼저 계산할 수 있고 더 긴 거리로 계산되었을 경우 스킵도 가능하다. 우선순위 큐를 사용하기 위해 hea.. 2024. 4. 21. [프로그래머스] 징검다리 건너기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 1. 문제 설명2. 풀이과정해당 문제는 이분 탐색과 슬라이딩 윈도우로도 해결할 수 있지만 정렬로 직관적으로 해결할 수도 있다.우선 리스트를 생성하여 디딤돌에 적힌 숫자(밟을 수 있는 횟수)와 디딤돌의 위치를 묶어 리스트에 추가하고 디딤돌에 적힌 숫자를 기준으로 오름차순 정렬을 한다.숫자가 적을수록 먼저 밟혀 없어질 것이기 때문이다.디딤돌의 숫자가 적은 돌부터 불러오며 다리를 건너가고 디딤돌을 제거한다.현재 디딤돌이 빠지면서 다음 디딤돌과 이전 디딤돌 사이의 길이를 확인하여 주어진 K보다 큰지 판별한다.K보다 크면.. 2024. 4. 19. 이전 1 2 3 4 5 6 7 ··· 44 다음 728x90 반응형
