Gonna be my Best part

https://programmers.co.kr/learn/courses/30/lessons/17687 코딩테스트 연습 - [3차] n진수 게임 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0 programmers.co.kr 풀이 이 문제에서는 우선 진법 변환부터 해주고 그 진법 변환한 문자열을 모두 이어붙여주는 것으로 시작합니다. 사실 이부분만 하면 다 푼거나 다름 없습니다. 우선은 진법 변환에 쓸 HashMap부터 만들어 줍니다. 16진수가 최대이므로 0~15까지 의 키를 갖도록 생성했습니다. 전체 진법 변환 문자열을 저장할 total이라는 문자열에 첫번째 수인 ..

https://programmers.co.kr/learn/courses/30/lessons/12911 코딩테스트 연습 - 다음 큰 숫자 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니 programmers.co.kr 풀이 이 문제는 그냥 1씩 증가시키면서 확인하는 방식으로 풀어도 효율성을 통과합니다. n을 2진수로 변환한 후 1의 개수를 세줍니다. n+1부터 1씩 증가시키면서 2진수 변환 시의 1의 개수를 세고 이것이 n의 것과 같아지는 경우를 찾을 때까지 반복합니다. 좀 더 복잡한 방법으로 푸는 방식도 있다고 하는데 저는 안해봤습니다ㅎㅎ c..

https://programmers.co.kr/learn/courses/30/lessons/76502# 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 풀이 이 문제는 괄호로 이루어진 문자열을 왼쪽으로 회전해가면서 새로운 문자열을 만들고 그 문자열이 올바른 괄호로 이루어진지 확인하면 됩니다. 대부분 "괄호"가 나오는 문제들은 스택을 사용해서 풀립니다. 이 문제도 마찬가지구요!! X = 0 ~ len-1 까지에 대해서 모두 확인을 해야합니다. 해당하는 X만큼 회전한 문자열을 생성합니다. 스택을 이용해서 올바른 괄호 문자열인지 확인합니다 스택을 이용해 올바른 괄호 문자열인지 확인하는 함수 여는 괄호의 경우 스택에 push 닫는 괄호의 경우 스택이 비어있는지, 스택의 top이 짝이 맞는 괄호..

https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 풀이 0번째 노드를 root로 잡고 DFS를 이용해서 leaf 노드까지 내려가서 거기서부터 0으로 만들면서 점점 root로 올라오면 되는 문제입니다. 어떤 알고리즘을 선택해야할지 고민하는 과정이 어려웠습니다ㅠㅠ 우선 중요한 것은 모든 가중치를 더했을 때 합이 0이 아닌 경우엔 절대 0으로 만들 수 없다는 것입니다. 그 경우를 처리해준 뒤, 연결..

https://programmers.co.kr/learn/courses/30/lessons/77885 코딩테스트 연습 - 2개 이하로 다른 비트 programmers.co.kr 풀이 이문제는 홀수와 짝수를 나눠서 풀이하였습니다. 짝수의 경우엔 2진수로 표현할 때 마지막 자리수가 항상 0 이므로 이를 1로만 바꿔주면 됩니다. 즉, +1만 해주면 간단히 구해집니다. 홀수의 경우 2진수로 표현할 때 마지막 자리수 부터 1이 연속으로 등장하는 횟수(cnt)를 세줍니다. 그런 뒤 01 을 10으로 바꾸는 연산을 해줘야합니다. 이 때 이를 10진수의 연산으로 간단하게 구하는 식은 ans = num + 2^(cnt-1)입니다. (이유는 위의 그림 참고!) class Solution { public long[] sol..

https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 programmers.co.kr 풀이 처음엔 dfs를 사용해서 재귀로 출려고 생각을 했습니다ㅠㅠ 그러나 처참한 시간초과가 예상되어서 dp로 노선변경 dp[2][len]인 2차원 배열을 사용하였는데요, dp[0][]은 첫번째 스티커를 사용하는 경우를 저장하고 dp[1][]은 첫번째 스티커를 사용하지 않는 경우를 저장합니다. 첫번째 스티커 사용O : dp[0][0] = sticke..

https://programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr 풀이 이 문제는 좌표를 방문한지 확인하는 것이 아니라, 경로를 이미 방문한지 확인하는 문제이다. 따라서 이 문제의 풀이의 핵심은 경로를 String으로 만들어서 HashSet에 넣어주면서 중복이 제거된 경로의 수만 찾는 것이다. 이때 경로 String은 작은 좌표를 앞에 써주는 방식으로 생성해줍니다. 아래처럼 방향이 다르고 같은 길을 지나는 경우를 잘 처리하기 위한 규칙을 임의로 만든 것입니다. 즉, U 또는 R방향으로 이동할 경우엔 "현재 좌표"+"이동 후 좌표"로 생성하고 D 또는 L 방향으로 이동할 경우엔 "이동 후 좌표" + "현재 좌..

https://programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 풀이 규칙만 잘 생각해 낸다면 매우 쉬운 문제입니다. 점프는 이동에 cost가 발생하지만 순간이동은 그렇지 않기 때문에 최대한 순간이동을 이용해야 합니다. 따라서 N을 2로 나눠가면서 나머지가 생기는 경우만 한칸을 점프 이동한다는 알고리즘으로 문제를 해결합니다. import java.util.*; public class Solution {..

https://programmers.co.kr/learn/courses/30/lessons/4288# 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 풀이 스택을 이용해서 풀이하는 경우들도 있긴 하지만 저는 인덱스를 이용해서 풀이하였습니다. 앞에서부터 삭제가능한 범위에서 가장 큰 수를 하나씩 선택해서 answer 문자열에 하나씩 추가하며 삭제해 나갑니다. 이를 k개 삭제시 까지 반복하거나 아니면 남길 수 있는 숫자수 (len - k 개)를 모두 남긴 경우 까지 반복합니다. while문에서 k개를 모두 삭제한 경우, 뒤에 숫자를 더 붙여주어야 할 필요가 있습니다. 반대로 남길 수 있는 숫자 수를 모두 남긴 경우엔 뒤에 있는 숫자들을 삭제한다고 생각해야합니다. 따라서 뒤에 숫자를 추가로 붙..

https://programmers.co.kr/learn/courses/30/lessons/12952 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 풀이 이 문제는 n*n크기의 체스판에 n개의 퀸을 서로 한번에 공격할 수 없도록 놓는 경우의 수를 구하는 문제입니다. n이 12이하로 매우 작은 값이기 때문에 저는 재귀를 이용하는 백트래킹 알고리즘을 사용해서 문제를 해결하였습니다. 우선 알아둘 것은 체스에서 퀸이 이동하는 방향은 가로, 세로, 대각선 입니다. 따라서 저는 맨위 가로줄 부터 한 줄에..