알고리즘 분류: 구현, 시뮬레이션문제 링크: https://www.acmicpc.net/problem/21609 구현이 은근히 쉽지 않았던 문제. 일단 문제는 그냥 주어진 로직을 순서대로 구현하면 된다.필요 로직은 다음과 같다. 1. 그룹핑2. 그룹 중 가장 블록 개수가 많은 그룹 없애기(-2 로 설정했음) 3. 이때 그룹들의 블록 개수가 모두 2 미만이라면 종료4. 블록 개수의 제곱만큼 점수를 더한다.5. 블록 내리기6. 왼쪽으로 90도 회전7. 블록 내리기8. 1번으로 다시 돌아간다. 이때 주의할 점은그룹핑 할 때는 무지개 블록을 기준으로는 하면 안된다는 점,기준 블록은 무조건 그룹핑을 시작한 블록 기준이라는 점(그래서 그냥 배열을 순서대로 순회하면 된다)그룹핑 하고 나서는 무지개 블록은 방문 처리..
[백준] 15989: 1, 2, 3 더하기 4 [Java]
알고리즘 분류 : DPhttps://www.acmicpc.net/problem/15989 정수 n을 1, 2, 3의 합으로 표현하는 방법의 수를 구하는 문제이다.각각의 경우에서 숫자는 1, 2, 3을 한 번에 하나씩만 더해 나가며 만들 수 있다.여기서 주의할 점은 순서만 다르고 합을 이루고 있는 요소가 같은 경우는 카운트에서 제외해야한다. 일단 n=1, 2, 3일 때를 살펴보자. n=1 일 때,1=1경우의 수는 1가지이다. n=2일 때2=1+12=2경우의 수는 2가지이다. n=3일 때,3=1+1+13=1+23=3경우의 수는 3가지이다. 얼핏 보면, n=3일 때를 보면 n=2일 때에서 +1을 붙인 경우, n=1일 때에서 +2을 붙인 경우, n=0일 때에서 +3을 붙인 경우가 보이는 것을 알 수 있다...
[백준] 19585: 전설 [Java]
알고리즘 분류: 트라이, 해싱문제 링크: https://www.acmicpc.net/problem/19585 【 문제 】 색깔을 의미하는 문자열 c개와 유저의 닉네임 n개가 주어진다.이후 팀원들의 닉네임이 n개가 주어질 때, 색상 이름과 닉네임이 순서대로 주어진 목록에 있는지 확인하는 문제이다. 【 풀이 】 정말 쉽지 않은 문제였다.정답을 맞히는데 까지 총 3번의 리팩토링을 거쳤다. 1. 색깔은 정방향으로 트라이 탐색, 닉네임은 역방향으로 트라이 탐색 이 풀이가 거의 10분 만에 생각나서 날먹하려 했지만.. 당연히 시간초과가 났다쿼리 20000개, 색깔과 닉네임 개수 4000개, 그리고 문자열 길이 각각 1000글자 싹이니, 색깔의 길이를 L, 닉네임 길이를 K라고 한다면이 풀이는 시간 복잡도 O(q *..
[백준] 9202: Boggle [Java]
알고리즘 분류: 트라이, 백트래킹문제 링크: https://www.acmicpc.net/problem/9202 【 문제 】 4*4 격자판에 알파벳들이 주어지면, 각 문자에서 8방 탐색을 해 문자열을 구성하고, 그 문자열이 찾고자 하는 문자열 리스트에 들어있는지 여부에 따라 총 점수, 가장 긴 문자열, 찾은 문자 개수를 갱신하는 문제이다.주의해야할 점은 같은 위치의 문자를 두 번 이상 사용할 수 없다(다시 방문할 수 없다)는 것, 이미 찾은 문자열에 대해서는 점수를 올리거나 문자 개수를 올리지 않는다는 점이다. 【 풀이 】찾아야 할 단어 목록을 트라이로 구성.이때 트라이 노드에 단어의 끝을 나타내는 문자인 `*` 을 넣어줬다격자판에서 인접한 문자를 고르면서 문자열을 조합해내야 하기 때문에 DFS로..
[백준] 28422: XOR 카드 게임
알고리즘: 다이내믹 프로그래밍 문제 링크: https://www.acmicpc.net/problem/28422 28422번: XOR 카드 게임 XOR 카드 게임이란 $N$장의 카드 더미가 있을 때, 맨 위에서부터 카드를 두 장 혹은 세 장씩 가져가 점수를 획득하는 게임이다. 이 게임에서 점수는 아래 단계를 거쳐 누적해서 획득할 수 있다. 한 www.acmicpc.net 【 문제 】 주어진 카드 n장 중 2장 혹은 3장을 카드가 0장이 될 때까지 뽑는다. 뽑은 카드에 적힌 숫자들을 XOR 연산한 뒤, 2진수 값으로 변환시켜 1의 개수를 구하고 점수로 더한다. 마지막에 1장의 카드가 남을 경우 최종 점수가 0점이 된다. 이때 점수의 최댓값을 구하는 문제. 【 풀이 】 1비트의 개수를 구하는 함수를 정의한다...
[프로그래머스] 연속 부분 수열 합의 개수 [Java]
알고리즘 분류: 해시맵, 누적합, 완전 탐색 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/131701 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 【 문제 】 정수로 이루어진 배열이 주어졌을 때 이를 원형 리스트로 간주한다. 이때, 서로 다른 연속 부분 수열의 합의 개수를 구한다. 【 풀이】 첫 for 루프에서 연속 부분 수열의 요소 개수를 정한다. 두 번째 for 루프에서 부분 수열의 첫 요소를 제거하고, 다음 요소를 추가하면서 누적 합을 계산한다. 이때 그 누적합을 map에 저장..
