[BOJ] 2143 두 배열의 합 - Java
2022. 7. 19. 17:03
Algorithm/백준
🤔 문제 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 😀 풀이 본 문제는 백준에 표기된 알고리즘 분류와 다르게 Map 자료구조를 사용하여 풀이했습니다. 문제에서 원하는 바는 주어진 두 배열의 부분합의 합이 문제에서 주어진 값(T)과 같아지는 경우가 몇 가지인지를 구하는 것 입니다. 문제에서 주어진 입력의 크기가 1,000 임을 고려해보았을 때 브루트 포스로 풀이하게 되면 시간초과가 날 것이라 판단하여 아래와 같은 풀이를 사용했..
[BOJ] 14500 테트로미노 - Java
2022. 6. 11. 13:58
Algorithm/백준
🤔 문제 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 😀 풀이 위 문제는 적절한 구현과 완전 탐색을 하여 풀이하였습니다. 주어진 종이 정보에 도형 5가지를 각각 놓아보아야 하는데 이 때 각 도형을 회전, 대칭시켜서 놓아보는 작업 역시 해봐야 합니다. 저의 풀이에서는 편의를 위해 도형을 회전하는 과정은 종이 정보를 회전하는 방식을 사용해 풀이했습니다. 풀이 과정을 간략하게 요약하면 아래와 같습니다. 종이의 모든 점에 도형을 하나씩 놓아본다. 점수를 계산한다. 1번 과정에서 도형을 회전하고 대칭해보는 과정을 포..
[BOJ] 9663 N-Queen - Python
2022. 5. 4. 05:01
Algorithm/백준
🤔 문제 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 😀 풀이 위 문제는 백트래킹으로 유명한 N-Queen 문제입니다. 처음에는 해당 문제를 2차원 배열을 사용하여 퀸들의 위치 정보를 담아 풀이를 하려했는데 구글링 도중 1차원 배열을 사용해 푸는 좋은 방법이 있어 해당 부분을 차용해보았습니다. 자세한 내용은 아래와 같습니다. rows라는 1차원 배열을 가지고 퀸들의 정보를 담습니다. 만약 rows[i] = j 라는 값을 가진다면 이는 i 행의 j 열에 퀸이 놓여져있다라는 의미가 됩니다. 또한 문제 풀이 과정에서 두 가지 ..
[BOJ] 16987 계란으로 계란치기 - Python
2022. 1. 8. 04:38
Algorithm/백준
🤔 문제 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 😀 풀이 위 문제는 주어진 N값과 시간 제한, 문제 상황을 고려해보았을 때 완전탐색이 가능합니다. 상황 종료 조건이 명확하고 비슷한 행동을 반복적으로 수행하므로 재귀 함수를 이용하여 문제를 풀어보았습니다. 재귀 함수( crash )에 대한 설명은 아래와 같습니다. 1. crash 함수의 nowIndex 인자는 현재 들고 있는 계란의 인덱스 입니다. 2. 가장 오른쪽 계란을 ..
[BOJ] 14712 넴모넴모 - Python
2022. 1. 4. 02:28
Algorithm/백준
문제 https://www.acmicpc.net/problem/14712 14712번: 넴모넴모 (Easy) 네모는 뿌××× 게임에 깊은 감명을 받아, 직사각형 모양의 격자판과 “넴모”라는 수수께끼의 생물을 이용하는 “넴모넴모”라는 게임을 만들었다. 이 게임의 규칙은 아주 간단하다. 격자판의 www.acmicpc.net 풀이 위 문제를 처음 봤을 때 전체의 경우에서 넴모가 2X2 사각형을 이루는 경우를 뺀 값을 답으로 구하려 했습니다. 즉 여집합 개념을 사용하여 답을 구해보려 했는데 생각보다 여집합을 구하는 과정이 복잡하다고 생각하여 시도 중 다른 풀이로 전환하였습니다. 풀이 전환 과정이 좀 더 빨랐다면 좋았을 텐데 힌트를 보고 여집합에 꽂혀버려서 시간을 조금 많이 보낸 것 같습니다. 왜 여집합을 구하는..
[BOJ] 14889 스타트와 링크 - Python
2022. 1. 2. 15:43
Algorithm/백준
문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 문제의 상황, 주어지는 입력의 크기, 제한 시간을 모두 고려해보면 완전 탐색을 이용하여 문제 풀이가 가능함을 알 수 있습니다. 따라서 아래와 같은 로직으로 간단하게 문제를 풀이할 수 있습니다. 1. combination을 사용하여 사람들을 두 팀으로 나눈다. 2. 두 팀에 대한 점수를 각각 구하고 점수 차이가 현재 답보다 작을 시 갱신한다. 풀이 코드는 아래와 같습니다. from itertools impor..
[BOJ] 1655 가운데를 말해요 - Python
2021. 12. 5. 04:34
Algorithm/백준
문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 이 문제를 보고 가장 먼저 떠오른 방식은 입력을 받을 때마다 배열에 추가하고 배열을 정렬하여 가운데 값에 해당하는 인덱스를 출력으로 내보내는 것이었습니다. 하지만 문제에서 주어진 N의 최댓값과 시간 제한을 고려해보았을 때 위와 같은 방식은 시간초과가 날 것이 뻔하여 다른 풀이로 호다닥 전환했습니다. 문제에서 요구하는 가운데 숫자는 그 값을 기준으로 좌측과 우측 숫자의 개..
[BOJ] 2075 N번째 큰 수 - Python
2021. 12. 4. 15:52
Algorithm/백준
문제 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 해당 문제는 N의 최대 크기가 1500으로 시간 제한만 고려한다면 입력되는 숫자 모두를 받아서 정렬하는 방식을 사용해도 풀이가 가능합니다. 하지만 메모리 제한으로 인해 위와 같은 풀이를 제출 시 메모리 초과가 납니다. 따라서 N^2 개의 숫자 모두를 배열에 저장하고 그 후에 문제 조건에 따라 무언가를 처리하는 방식으로는 해당 문제를 풀기 어렵습니다. 이에 N^2의 숫자들을 모두 살펴보면서 로직..
[BOJ] 1927 최소힙, 11279 최대힙 - Python
2021. 12. 2. 03:12
Algorithm/백준
문제 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 풀이 위 두 문제는 python의 heapq 모듈을 사용하면 쉽게 풀 수 있는 문제입니다. 문제 제목에서도 풀이를 유추할 수 있었지만 입력으로 주어지는 최대 N이 100,000..
[BOJ] 22781 징검다리 건너기 - Python
2021. 11. 20. 01:03
Algorithm/백준
문제 https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 풀이 문제를 처음 보면서 첫 번째 돌에서 마지막 돌까지 가는 모든 케이스(조합)를 체크해보면 답을 구할 수 있겠다라는 생각은 쉽게 떠올릴 수 있었습니다. 하지만 이러한 방법은 N의 크기와 시간 제한때문에 불가능함을 알 수 있습니다. 경험상 문제가 특정 원소를 선택하거나 하지않거나(이 문제의 경우 발판으로 특정 돌을 선택 할지 말지)..