728x90 반응형 BOJ71 [BOJ] 1946번 신입 사원 / 사용언어 : 파이썬(python) ※ 문제링크 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 해당 문제는 그리디 알고리즘과 관련된 문제로, 브루스포트 알고리즘을 접목해서 해결할 수 있는 문제였다. 문제에서 제시된 조건은 서류와 면접성적 중 1가지는 반드시 다른 지원자들보다 높은 성적이어야 합격이 가능하다는 점이었다. 서류심사 성적 또는 면접성적을 오름차순으로 정렬하여 반복문을 돌리면 1가지 성적만 가지고도 비교가 가능했기에 서류심사 성적을 오름차순으로 정렬한 후 그리디 알고리즘을 활용하여 모든 경우의 수를 비교하며 문제.. 2022. 3. 12. [BOJ] 9663번 N-Queen / 사용언어 : 파이썬(python) ※ 문제링크 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해당문제는 백트래킹 알고리즘의 대표적인 문제로 DFS, 브루스포트 알고리즘을 추가로 활용하여 해결할 수 있는 문제였다. 처음에는 2차원 배열을 활용하여 문제를 해결하려고 하였으나, N의 값에 따라 탐색할 경우의 수가 급격하게 증가하기 때문에 문제 해결방안으로 부적절한 것을 알게되었다. 다른 방법의 풀이를 생각하던 중 퀸의 동작원리 상 한개의 행에는 1개의 퀸밖에 들어갈 수 없고, N x N 체스판에 N개의 퀸을 놓기위해서는 각 행에 퀸이 하나씩 반드시 들어가야한다는.. 2022. 3. 12. [BOJ] 15654번 N과 M(5) / 사용언어 : 파이썬(python) ※ 문제링크 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 해당 문제는 백트래킹과 관련된 문제로 DFS를 활용한 재귀를 통해 해결할 수 있는 문제였다. 백트래킹의 기본적인 원리를 구현할 수 있다면 쉽게 해결할 수 있었고, 중복을 허용하지 않고, 숫자가 같아도 순서가 다르면 다르다는 점을 고려하여 해결하면 되는 문제였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값들을 리스트에 저장하고, 오름차순으로 정렬해준다. 2. 숫자들의 순열조합을 작성할 DFS함수를 백트래킹을 적용해서 작성하고, 조.. 2022. 3. 9. [BOJ] 2539번 보물섬 / 사용언어 : 파이썬(python) ※ 문제링크 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 해당 문제는 브루스포트 알고리즘과 BFS를 활용하여 푸는 문제였다. 간단하게 말해서 그냥 BFS로 탐색할 수 있는 함수를 구현하고, 모든 좌표에서 모든 경우의 수를 찾아서 비교한 후 결과값을 출력하면 되는 문제였다. 문제 조건에서 보물은 서로 가장 멀리 떨어져있고, 최단거리로 이동하라고 나와있는데, 해당 조건은 그냥 가장 먼 좌표 2개의 거리를 구하면 된다는 걸 두번 말하고 있는 것이니 가장 거리가 먼 육지좌표 2개의 거리를 출력할 수 있게 하면 된다... 2022. 3. 7. [BOJ] 1339번 단어 수학 / 사용언어 : 파이썬(python) ※ 문제링크 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 해당 문제는 그리디 알고리즘과 브루스포트 알고리즘과 관련된 문제로 둘 중 1개만 활용해도 풀 수 있는 문제였다. 브루스 포트 알고리즘은 모든 경우의 수를 탐색해야하기에 시간제한이 빠듯할 것 같다 생각하여 그리디 알고리즘 쪽에 초점을 맞춰 논리성을 찾는데 보다 주안점을 두고 해결하였다. 해결을 위해 사용한 논리적 조건은 아래와 같다. 1. 입력받은 알파벳별로 자릿수를 분류하고, 알파벳들이 등장할 때마다 자릿수를 기록하여 더해준다. 2. 입력값들에.. 2022. 3. 6. [BOJ] 1644번 소수의 연속합 / 사용언어 : 파이썬(python) ※ 문제링크 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 해당 문제는 에라토스테네스의 체로 숫자의 범위안의 소수 리스트를 작성하고, 투 포인터를 활용하여 연속된 소수의 합이 조건에 만족하는지 확인하면서 풀 수 있는 문제였다. 문제 조건 중 소수의 중복사용이 불가능하고 연속한 수들만 사용가능하다고 하였기에 해당 내용을 활용하여 문제에 대입하였으며, 채점결과 문제없이 작동하였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값을 바탕으로 소수리스트를 출력할 함수를 작성하고, 변수 값을 저장해준다. 2. 포인터와 카운트해줄 변수를 작성하고, while 반복문을 통해 조건을 걸어 만족하는 수들의 조합 수를 확인한다. (0부.. 2022. 2. 28. [BOJ] 1806번 부분합 / 사용언어 : 파이썬(python) ※ 문제링크 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 해당문제는 투 포인터를 활용하여 해결할 수 있는 문제였다. 주의해야할 점은 2가지 정도였는데, 1. 부분합을 이루는 숫자들의 개수가 1개일 수도 있다. 2. sum함수를 사용하면 시간초과가 난다.(sum함수 호출없이 문제를 해결해야함) 처음에는 리스트형태로 변수를 선언하고 sum함수로 풀어보려다 시간초과가 나와서 코드를 변형하여 해결하였다. 즉, 조건을 충족하면서 문제를 해결하기 위해서는 결과값이 리스트형태가 아니라 한개의 변수형태로 .. 2022. 2. 27. [BOJ] 2470번 두 용액 / 사용언어 : 파이썬(python) ※ 문제링크 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 해당 문제는 투 포인터와 관련된 문제로 2개의 포인터를 사용해서 값을 체크하고 조건에 충족하면 갱신하는 식으로 해결할 수 있는 문제였다. 용액의 성질을 리스트에 저장하고, 정렬한 후 좌측끝과 우측끝 각각 포인터를 지정하고 값을 확인하는 방식으로 문제를 해결했으며, 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값을 리스트와 변수로 지정하여 저장한다. 2. 용액들의 성질을 저장한 리스트를 오름차순으로 정렬한 후.. 2022. 2. 26. [BOJ] 3273번 두 수의 합 / 사용언어 : 파이썬(python) ※ 문제링크 채점 현황 www.acmicpc.net 해당 문제는 투 포인터를 활용하여 해결할 수 있는 문제였다. 사실 반복문만으로도 결과는 출력할 수 있지만 당연하게도 시간초과가 되었다. 핵심은 정렬 후 양쪽 끝에서부터 하나씩 쌍을 만들어 값을 비교하는 것으로 포인터를 0과 n-1로 주어 숫자쌍의 합에 따라 포인터를 이동시키면 된다. 자세한 문제풀이방법과 코드는 아래와 같다. 1. 입력받은 값들로 변수와 숫자리스트를 생성하여 저장한다. 2. 포인터들로 숫자쌍을 생성하여 숫자쌍의 합이 x보다 크면, 우측 포인터를 -1하고, x보다 작으면 좌측 포인터를 +1하여 비교하다가 좌측과 우측포인터의 차이가 1이면 조건문을 종료한다. 3. 조건문 종료 후 결과값을 출력한다. n = int(input()) number.. 2022. 2. 23. 이전 1 2 3 4 5 ··· 8 다음 728x90 반응형
