분류 전체보기
[BOJ] 2705 - 팰린드롬 파티션
문제 출처 [BOJ] 2705 - 팰린드롬 파티션 풀이 저는 문제가 잘 풀리지 않으면 무작정 쓰면서 고민해보는 편입니다. 특히 규칙을 찾는 문제에서는 더더욱 그렇습니다. 이 문제 또한 그런 방법으로 풀었습니다. 어떤 파티션을 앞에서 읽는 것과 뒤에서 읽는 것이 같은 경우 팰린드롬 파티션이라 합니다. 그리고 왼쪽 절반과 오른쪽 절반이 재귀적인 팰린드롬이거나 비어있는 경우 재귀적인 팰린드롬 파티션이라 합니다. 이 문제는 어떤 수의 재귀적인 팰린드롬 파티션의 갯수를 찾는 문제입니다. 다이나믹 프로그래밍 알고리즘을 이용해서 푸는 문제였는데 1부터 현재 수를 2로 나눈 몫까지 각각의 재귀적인 팰린드롬 파티션의 갯수를 더해주면 현재 수를 알아낼 수 있었습니다. 이 때 각각의 재귀적인 팰린드롬 파티션의 갯수를 구하기..
[BOJ] 1043 - 거짓말
문제 출처 [BOJ] 1043 - 거짓말 풀이 다양한 풀이 방법이 존재하는 것 같은데 저는 그래프를 만들고 bfs로 탐색하는 방법으로 풀었습니다. 지민이가 모든 파티에 참여하는데 그 중 과장된 이야기를 할 수 있는 파티를 찾는 문제였습니다. 파티에는 지민이 뿐만아니라 진실을 알고 있는 사람도 참여하기 때문에 진실을 알고 있는 사람이 참여하는 파티에서는 과장된 이야기를 할 수 없습니다. 그리고 그 파티에 참여한 진실을 아는 사람을 제외한 다른 사람들 또한 진실을 듣게 되기 때문에 그 사람들이 참여한 다른 파티에서도 과장된 이야기를 할 수 없습니다. 우선 파티에 참여한 사람들을 양방향 그래프로 연결시켜 주었습니다. 모든 파티를 그렇게 한 후 진실을 알고 있는 사람들을 큐에 집어넣고 만들어진 그래프를 bfs를..
[프로그래머스] 폰켓몬
문제 출처 [프로그래머스] 찾아라 프로그래밍 마에스터 - 폰켓몬 풀이 주인공은 최대 N/2마리의 폰켓몬을 가질 수 있습니다. 근데 이때 가능한 가장 많은 종류의 폰켓몬을 들고가고 싶어합니다. 우선 폰켓몬의 종류가 담긴 배열을 정렬해주었습니다. 배열을 한번 돌아주면서 종류의 갯수를 세주었습니다. 종류가 만약 N/2보다 적다면 그대로 결과를 반환하고, 많다면 N/2만큼 결과를 반환해주었습니다. 코드 small-j/Algorithm Contribute to small-j/Algorithm development by creating an account on GitHub. github.com
[BOJ] 1911 - 흙길 보수하기
문제 출처 백준 1911 - 흙길 보수하기 풀이 입력된 웅덩이를 정렬한 뒤 웅덩이들의 목록을 처음부터 한번 돌아주는 스위핑 알고리즘을 이용해 필요한 널빤지 수를 구해주었습니다. 스위핑을 통해 다음과 같은 과정을 반복했습니다. 1. 널빤지를 놓을 시작 점을 잡아주었습니다. 2. 웅덩이의 시작이 널빤지를 놓을 시작 점보다 더 멀리있다면 시작 점을 갱신해주었습니다. 3. 하나의 웅덩이가 끝나는 부분에서 시작 점을 빼주어 필요한 널빤지의 갯수를 구해주었습니다. 4. 널빤지를 놓은 만큼 시작 점을 뒤로 갱신해주었습니다. 중요한 점은 널빤지가 여러 웅덩이에 걸쳐있을 수 있다는 점입니다. 따라서 가장 마지막으로 놓은 널빤지가 끝나는 부분으로 시작 점을 잡아 최소의 널빤지를 사용할 수 있게 했습니다. 코드 small-..
[BOJ] 9251 - LCS
문제 출처 백준 9251 - LCS 풀이 LCS(Longest Common Subsequence) 알고리즘을 사용하여 최장 공통 부분 문자열을 구하는 문제였습니다. 주어진 문자열의 공통 부분 문자열 중 그 길이가 최장인 것을 LCS라 말하는데 이 때 Substring과 Subsequence의 개념이 다릅니다. Substring은 연속된 부분 문자열이고 Subsequence는 연속되지 않은 부분 문자열입니다. 즉, 연속되지 않은 부분 문자열의 길이가 최장인 것입니다. LCS 알고리즘을 사용하여 길이를 구하면 풀 수 있는 문제입니다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development by creating an account on..
[BOJ] 16936 - 나3곱2
문제 출처 백준 16936 - 나3곱2 풀이 나3 : 3으로 나누어 3으로 나누어떨어지는 수 곱2 : 2를 곱함 이렇게 나3곱2를 한 수들을 나열하여 수열을 만들 수 있는데 그 수열을 섞어서 입력이 주어집니다. 그리고 그 수열을 찾는 것이 문제입니다. 위의 방법처럼 원래 수에 곱2한 값을 저장해주고 나3을 해주어 나누어떨어진다면 저장해주었습니다. 원래 수들을 차례대로 돌면서 각각을 시작수로 놓고 시작수에서 나3 하거나 곱2한 값이 원래 수에 존재한다면 그 원래 수에서 또다시 나3곱2한 값을 보고 다음 수를 찾아주는 방법으로 수열을 찾아주었습니다. 만약 나3곱2한 값이 원래 수에 존재하지 않는다면 멈춰주었고 한번 수열을 찾으면 멈추었습니다. 코드 small-j/BOJ_Algorithm Contribute ..
[BOJ] 20154 - 이 구역의 승자는 누구야?!
문제 출처 백준 20154 - 이 구역의 승자는 누구야?! 풀이 그대로 구현하면 되는 문제였습니다. 입력받을 때 각 문자들을 획수로 치환하여 벡터에 저장해주었습니다. 마지막 1개의 원소가 남을 때까지 벡터의 원소들을 쌍을 지어 더해주는 과정을 반복하였습니다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development by creating an account on GitHub. github.com
[BOJ] 1612 - 가지고 노는 1
문제 출처 백준 1612 - 가지고 노는 1 풀이 11, 111, 1111, 11111 .... 처음에는 큰 수 계산이 가능한 파이썬으로 위처럼 한자리씩 늘려가며 수를 만들어 계산해주려 했지만 시간초과가 납니다. 파이썬도 수가 커질수록 연산을 수행하는데 오래 걸리기 때문입니다. (11 % N 의 나머지) * 10 + 1 이 처럼 작은 단위로 나누어 계속 늘려주면서 계산하여 수가 길어지는 문제점을 해결했습니다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development by creating an account on GitHub. github.com
[BOJ] 1484 - 다이어트
문제 출처 백준 1484 - 다이어트 풀이 엔토피아가가 선물해준 저울로 젠 G 킬로그램이 주어지면 성원이의 현재 몸무게로 가능한 것을 모두 구하는 문제였습니다. G 킬로그램 = {성원이의 현재 몸무게}2 - {성원이가 기억하고 있던 몸무게}2 G는 100,000 보다 작거나 같기 때문에 무작정 큰 수까지 돌려서 제곱 - 제곱의 조합을 찾기에는 시간초과가 날 것입니다. 그래서 어떤 상한선이 있을 것이라 생각했고 수가 커질수록 제곱 - 제곱의 결과가 커진다는 것을 알아내어 제곱 - 제곱의 결과가 G보다 커지는 경우 더이상 몸무게를 찾지 않도록 해주었습니다. 코드 small-j/BOJ_Algorithm Contribute to small-j/BOJ_Algorithm development by creating ..
[BOJ] 20152 - Game Addiction
문제 출처 백준 20152 - Game Addiction 풀이 어떤 칸 x에 도달하는 최단 경로를 저장해주는 배열(map)과 x에 최단 경로로 도착할 수 있는 모든 경로들의 갯수를 저장해주는 배열(acc)을 따로 선언해주어야 합니다. - 큐에 데이터를 넣지 않는 경우 1. x에 도달했을 때 최단 경로가 아닐 경우 2. x가 이미 최단 경로가 갱신되어 있는 경우 즉, x에 최단 경로로 최초로 도달했을 때 방문 표시를 해주고 이후에 최단 경로로 도달하는 경로들은 x위치에 경로의 갯수만 저장해주는 것입니다. 위와 같이 진행했을 때 목적지에 최단 경로로 도달할 수 있는 모든 경우의 수를 구할 수 있습니다. 그 이유는 다음과 같습니다. 큐는 선입선출(FIFO) 자료구조 입니다. 먼저 들어온 데이터가 먼저 나가는 ..