알고리즘266

• 

  [BOJ_12891] DNA 비밀번호 📌 문제 링크: https://www.acmicpc.net/problem/12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: DNA 비밀번호 문자열의 길이가 최대 1,000,000으로 만약 시간 복잡도가 O(N)보다 큰 알고리즘을 적용한다면 '시간 초과'가 발생한다. 그래서 슬라이딩 윈도우와 단일 for 반복문을 사용해서 시간 복잡도을 O(N)으로 맞추고, 부분 문자열에 등장하는 알파벳의 개수를 세기위해서 딕셔너리를 사용했다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 11. 24.

• 

  [프로그래머스] 기사단원의 무기 📌 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/136798 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ✅ 내 풀이(Success) : 🧐 Review: 약수를 구하는 알고리즘을 안다면 어렵지 않게 해결할 수 있다. 🚩 Idea: 1. 약수의 개수 == 공격력 2. 공격력 1당 1kg의 철 3. 무기를 만들기 위해 필요한 철의 무게의 총합 == 무기 공격력의 총합 4. 공격력이 limit 보다 크면 미리 정해진 power만큼의 공격력을 가진 무기를 구매한다. 알고리즘 문제 풀이: 파이썬/Programmers 2022. 11. 19.

• 

  [프로그래머스] 다리를 지나는 트럭 📌 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr ✅ 내 풀이(Success) : 🧐 Review: while 반복문이 종료되고 bridge의 길이만큼 answer(초)를 더해준 이유는 마지막 트럭이 다리에 올라가고 다리를 완전히 빠져나오려면 bridge의 길이만큼의 시간이 필요하기 때문이다. 🚩 Idea: 큐에 대한 이해가 있으면 어렵지 않게 풀 수 있는 문제이다. 알고리즘 문제 풀이: 파이썬/Programmers 2022. 11. 19.

• 

  [BOJ_1926] 그림 📌 문제 링크: https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 꽤 오랜만에 풀어본 그래프 탐색 문제였지만 기존 코드를 참조하지 않고 기억에만 의존해서 문제를 해결했다. 매번 그래프 탐색 문제를 풀 때 DFS, BFS 코드 템플릿이 기억나지 않아서 기존에 내가 풀어둔 코드를 참고하곤 했는데, 오늘은 참고 없이 해결한 것으로 보아 그동안의 문제 풀이 경험이 조금은 쌓였다는 생각이 든다. 이 문제에서 주.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 11. 10.

• 

  [BOJ_11501] 주식 📌 문제 링크: https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net ❌ 내 풀이(Failure) -1: ❌ 내 풀이(Failure) -2: ✅ 내 풀이(Success) : 🧐 Review: 처음 생각했던 풀이는 주식의 가격이 최대일 때 보유한 주식을 팔고, 남은 주식들 중에서 주식의 최댓값을 갱신한 뒤 같은 방법을 이용해서 결과를 구하는 방식이었다. 하지만 이 방법은 N의 최댓값이 1,000,000으로 매우 큰데, for반복문과 sum.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 11. 9.

• 

  [BOJ_6550] 부분 문자열 📌 문제 링크: https://www.acmicpc.net/problem/6550 6550번: 부분 문자열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t가 빈칸을 사이에 두고 들어온다. s와 t의 길이는 10만을 넘지 않는다. www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 어렵게 생각하면 어렵고 쉽게 생각하면 쉬운 문제... 이 문제도 출력 형식에 주의해야 한다. 'Yes'와 'No'를 'YES'와 'NO'로 제출해서 몇 번 틀렸다. 문제를 주의 깊게 읽자! 알고리즘 문제 풀이: 파이썬/BOJ 2022. 11. 8.

• 

  [BOJ_1244] 스위치 켜고 끄기 📌 문제 링크: https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 주어진 조건에 따라 구현하면 어렵지 않게 해결할 수 있으나 출력 형식에 꼭 주의해야 한다. 스위치를 한 줄에 20개만 출력할 수 있기 때문에 20개가 넘어간다면 줄바꿈을 해줘야한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 11. 8.

• 

  [BOJ_1718] 암호 📌 문제 링크: https://www.acmicpc.net/problem/1718 1718번: 암호 Vigenere cipher이라는 암호화 방법은 암호화하려는 문장 (평문)의 단어와 암호화 키를 숫자로 바꾼 다음, 평문의 단어에 해당하는 숫자에 암호 키에 해당하는 숫자를 더하는 방식이다. 이 방법을 변 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 난이도가 낮은 문제였지만 어떻게 구현할지 생각을 좀 더 해볼 수 있는 좋은 문제라고 생각한다. 먼저 암호화 키는 deque를 이용해서 저장했고, 암호화를 진행하거나 진행하지 않거나 deque를 회전시키는 것으로 계속 사용할 수 있도록 구현했다. 문자열 s가 공백이 아닌 경우, ord() 함수를 이용해 해당 문자의 아스키코드 값.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 11. 8.

• 

  [BOJ_2512] 예산 📌 문제 링크: https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net ✅ 내 풀이(Success) : 🚩 Idea: - 1번의 경우라면, 모든 요청이 배정될 수 있으므로 예산들 중에서 최댓값을 출력한다. - 2번의 경우라면, 모든 요청이 배정될 수 없으므로 이분 탐색으로 예산의 상한액을 구한다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 11. 7.

• 

  [BOJ_3758] KCPC 📌 문제 링크: https://www.acmicpc.net/problem/3758 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net ✅ 내 풀이(Success) : 🧐 Review: 순위를 정하기 위해 팀 ID를 키(key)로 모든 문제들의 점수를 값(value)으로 갖는 score 딕셔너리와 팀 ID를 키로 [최종 점수, 제출 횟수. 제출시간]을 값으로 갖는 record 딕셔너리를 사용했다. 로그 엔트리 수인 m만큼 for 반복문을 돌면서 i, j, s(팀 ID, 문제 번호, 점수)를 입력받고, 두 딕셔너리를 적절히.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 11. 7.