코딩테스트 공부

저는 이렇게 풀었는데 다른사람들의 풀이를 확인하니 굉장히 짧게 적을 수도 있더라구요..n을 계속 7로 나누다가 n이 값이 0보다 작아지는 순간 반복문이 끝나고 카운터한 횟수만큼을 answer 에 대입해 풀었는데..다른 분들의 풀이를 보니 3항 연산자로 푸는 방법도 있었

piece라는 변수를 먼저 선언한 후 while반복문을 통해 답을 도출해내는 형식을 이용했다. piece가 사람의 수로 나누어떨어질 때까지 돌아가는 반복문으로 piece가 n으로 나누어 떨어지지 않을 때까지 piece에 6씩 더한다.piece가 6으로 떨어져 반복문에서

reverse()해주기 위해 StringBuffer 클래스를 사용해줄 것입니다.StringBuffer란 ?StringBuffer는 문자열을 추가하거나 변경할 때주로 사용하는 자료형이다.String 클래스의 인스턴스는 한 번 생성되면 변경이 불가능하기에 StringBuf

정수를 문자열로 변환하는 방법은 여러가지가 존재한다.1\. String.valueOf() 사용2\. Integer.toString() 사용3\. String.format() 사용4\. StringBuffer 또는 StringBuilder 사용이 외에도 다른 방법들이 존

김태원 님의 '자바(Java) 알고리즘 문제풀이 입문: 코딩테스트' 강의를 보고 정리한 글입니다.설명영어 알파벳과 특수문자로 구성된 문자열이 주어지면 영어 알파벳만 뒤집고,특수문자는 자기 자리에 그대로 있는 문자열을 만들어 출력하는 프로그램을 작성하세요.입력첫 줄에 길

김태원 님의 '자바(Java) 알고리즘 문제풀이 입문: 코딩테스트' 강의를 보고 정리한 글입니다.설명한 개의 문자열 s와 문자 t가 주어지면 문자열 s의 각 문자가 문자 t와 떨어진 최소거리를 출력하는 프로그램을 작성하세요.입력첫 번째 줄에 문자열 s와 문자 t가 주어

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.단순히 3진법으로만 바꾸는 것이 아닌 이를 앞뒤로 뒤집은 값을 다시 10진법으로 표현해야 하는 복잡한

김태원 님의 '자바(Java) 알고리즘 문제풀이 입문: 코딩테스트' 강의를 보고 정리한 글입니다.설명N개의 자연수가 입력되면 각 자연수를 뒤집은 후 그 뒤집은 수가 소수이면 그 소수를 출력하는 프로그램을 작성하세요.예를 들어 32를 뒤집으면 23이고, 23은 소수이다.

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디있는지 알고 싶습니다.같은 글자의 위치를 알기 위해선 중첩 반복문을 돌려야한다. 그 전에 문자열을 문자형 배열로 바꿔준 뒤 반복문을 돌려준다.answe

과일 장수가 사과 상자를 포장하고 있습니다. 사과는 상태에 따라 1점부터 k점까지의 점수로 분류하며, k점이 최상품의 사과이고 1점이 최하품의 사과입니다. 사과의 최대점수 k, 한 상자에 들어가는 사과의 수 m, 사과들의 점수 score가 주어졌을 때, 과일 장수가 얻

정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return하도록 solution 함수를 완성해주세요.먼저 두개의 수를 뽑아 더하고 우리가 지정한 배열에 값이

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.maps는 n

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대

기사단원의 수를 나타내는 정수 number와 이웃나라와 협약으로 정해진 공격력의 제한수치를 나타내는 정수 limit와 제한수치를 초과한 기사가 사용할 무기의 공격력을 나타내는 정수 power가 주어졌을 때, 무기점의 주인이 무기를 모두 만들기 위해 필요한 철의 무게를

두 정수 X, Y의 임의의 자리에서 공통으로 나타나는 정수 k(0 ≤ k ≤ 9)들을 이용하여 만들 수 있는 가장 큰 정수를 두 수의 짝꿍이라 합니다(단, 공통으로 나타나는 정수 중 서로 짝지을 수 있는 숫자만 사용합니다). X, Y의 짝꿍이 존재하지 않으면, 짝꿍은

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작

PROGRAMMERS-962 행성에 불시착한 우주비행사 머쓱이는 외계행성의 언어를 공부하려고 합니다. 알파벳이 담긴 배열 spell과 외계어 사전 dic이 매개변수로 주어집니다. spell에 담긴 알파벳을 한번씩만 모두 사용한 단어가 dic에 존재한다면 1, 존재하지

5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할 때에는 한 번 거쳤

신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안 되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다.예를 들어 입력으로 KAKAO가

이 코드는 동적 계획법을 사용하거나 BFS를 사용해서 최소 연산 횟수를 구해야한다. BFS의 경우 이미 답을 발견했는데에도 끝까지 탐색하기 때문에 메모리로 인해 테스트에 통과하지 못한다.처음에는 어떤 방식으로 접근하는지 감이 잡히지 않아 무작정 무한루프를 통해 접근하려

처음에는 한 단어를 재배열해 다른 단어를 만들 수 있다는 조건에 초점을 맞추지 않고 모음을 제거한 문자열이 동일해야 한다는 것에 초점을 맞추어 코드를 짜니이 테스트를 통과하지 못했다.3가지 조건을 모두 만족할 수 있도록 각각의 메서드를 따로 작성해 삼항 연산자를 사용해

처음엔 사이즈별 인원 수를 셀 때이렇게 적었었다. 근데 이렇게 되면 t가 1이거나 사이즈별 인원이 0명일 때도 cnt수가 카운트 되기에 테스트에 실패를 했었다.반례 상황들을 고려해 코드를 수정했더니 통과할 수 있었다.

처음에는 중첩 반복문을 사용해 sliding window 방식을 사용해 문제를 해결하려고 하니 자꾸만 시간 초과가 떴다.이렇게 되면 시간복잡도가 기하 급수적으로 증가해서 그런 것 이었다. 그래서 카데인 알고리즘을 적용해서 문제를 풀어보았다. maxSoFar와 curre

처음에는 단순 반복문을 사용해 문제를 접근하려고 하니 시간복잡도로 인해 런타임에러가 발생하였다. 이 문제는 세그먼트 트리 알고리즘을 사용해 풀어야 하는 문제였다. 세그먼트 트리를 사용하면 시간복잡도가 O(logN) 이기 때문에 내가 마주한 시간초과 문제를 해결할 수 있

이 문제는 에라토스테네스의 체를 응용하여 풀어야하는 문제이다.에라토스테네스의 체 알고리즘은 어떤 수를 배수로 가지는 숫자는 소수가 될 수 없다는 원리를 사용해 문제를 해결한다.그렇기에 우리는 min ~ max까지 모두 고려할 필요가 없고 min~Math.sqrt(max

이 문제는 동적계획법을 사용해 접근해야 한다.두 문자열의 공통 문자들을 하나씩 누적시키면서 값을 증가시켜야 한다.내가 한번에 접근하지 못한 이유 중 하나가 2차원 배열로 만들어서 접근해야했었다는 점이다.두 문자열 모두 방문해야 하기 때문에 2차원 배열을 생성했어야 했는

이 문제도 동적계획법을 사용해 접근해야 한다.먼저 점화식을 만들어야 이 문제를 풀 수 있다.입력받은 n 크기만큼의 coin 배열과 k+1 크기 만큼의 dp 배열을 만들어준다.이와 같이 각각 동전의 가치를 이용해 dp의 값을 갱신해준다.이와 같이 도출한 점화식이 dp\[

n = 1k=1 : 1가지k=2 : 2가지(0+1, 1+0)k=3 : 3가지(0+0+1, 0+1+0, 1+0+0)위와 같은 dp 배열을 얻을 수 있다. n = 2 k=1 : 1가지k=2 : 3가지(0+2, 2+0, 1+1)k=3 : 6가지(0+0+2, 0+2+0, 2

원생들의 키가 오름차순 정렬이 되어 입력되기 때문에 우리는 인접한 원생들끼리의 키 차이를 통해 최소 비용을 구할 수 있다.인접한 원생들 사이의 키 차이를 구하고 구한 키 차이를 오름차순 배열로 정렬해 k개 만큼 result에 더해주면 최소 비용이 나온다.이때 5명을 3

처음에는 큐에 넣어서 풀어야하나 따로 Point 클래스를 만들어 각 점을 저장해야하나에 대한 고민이 많았는데 Union-Find 알고리즘을 사용해봐야 겠다는 생각이 들었다.경로 압축을 통해 각 노드들에 연결된 최상위 노드와 연결시켜 결론적으로 최상위 노드와 입력받은 두

세그먼트 트리를 사용해 문제를 해결했다. 이 전에도 세그먼트 트리를 사용해 각 노드의 합을 갱신하는 문제를 푼 적이 있었다. 하지만 이번 문제는 최대값과 최소값을 구하면 되는 것이기 때문에 각각 최솟값과 최댓값을 저장할 minTree, maxTree 배열을 선언해주었다

만약 GCF가 주어지면 (100 \* G) + (10 \* C) + (1 \* F) 와 같은 형태로 나타내면 될 것 같다는 생각이 들었다.이렇게 되면 G=9, C=8, F=7일 때에 최대값을 구할 수 있다.이렇게 선언된 배열을 오름차순으로 정렬 후 뒤에서부터 9, 8

동적 계획법을 사용해 접근해야 하는 문제이다. 먼저 dp 배열을 선언해준다.이때 dp\[i]\[i]는 자기 자신을 곱하는 연산이기에 0으로 지정해준다. arr배열에는 입력받은 행렬의 크기를 저장한다.점화식은 dp\[i]\[j] = Math.min(dp\[i]\[j],

처음엔 동적계획법 방법으로 풀려고 하니 재귀호출때문에 메모리, 시간복잡도 문제로 자꾸 런타임 에러가 발생했다. 그래서 반복문으로도 접근하려고 했는데 이 방법 또한 시간 복잡도 문제 때문에 런타임 에러가 발생했다 !!!!!알아보니 행렬의 거듭제곱을 사용하면 시간 복잡도가

연결된 최상위 노드를 구하면 된다는 생각이 들어서 유니온 파인드 알고리즘을 사용해 접근하였다.하지만 예시로 나와있는 두번째 입력의 결과 값이 자꾸 2로 나와서 어떻게 해결해야하는지에 대한 고민이 많았다.노드 2와 3은 나중에 연결되기 때문에 노드 6은 갱신되지 않은 문

처음에는 문제를 제대로 못읽고 그래프 탐색만 사용해서 최상위 부모 노드만 출력했는데 알고보니... 바로 이전의 부모 노드를 출력하는 문제여서 조금 헤맸다.너비우선탐색을 사용해서 바로 상위 노드의 부모 노드를 parent 배열에 저장하도록 하였고 상위 노드가 정해진 애들

PriorityQueue를 사용해서 문제를 접근했다.그리고 보석의 가치가 높은 순서부터 넣을 수 있는 작은 가방에 넣도록 했다. 그래서 큐에 값을 삽입할 때 내림차순 정렬이 되도록 Collections.reverseOrder()를 명시해줬다.먼저 작은 무게의 보석부터

수업의 시작 시간과 끝나는 시간을 저장하기 위한 클래스를 따로 만들어 주었다. Time 클래스의 배열을 입력받은 n의 크기로 지정해주었다.먼저 이 문제의 중점은 최소 강의실의 수를 사용하는 것이다. 즉, 한 강의의 시작 시간이 어떤 강의의 끝나는 시간보다 늦게 시작되면

DFS 알고리즘을 사용해 풀이하면 금방 쉽게 풀 수 있는 문제였다.이때 물에 잠기지 않은 안전한 영역의 최대 개수를 구해야하는데, 위/아래, 왼쪽/오른쪽 인접한 영역만 고려를 하면된다.이때 물에 잠기는 높이가 1 이하라고 하면 입력이 위의 사진과 같을 때 잠기지 않는

처음에는 유니온-파인드 알고리즘을 사용해 문제를 풀어가려고 하였으나 자꾸 어딘가 막혀서 문제가 풀리지 않았다. 그래서 결국 혼자 힘으로 문제를 풀이 하는 것이 아닌 다른 사람의 풀이를 참고하여 문제를 풀었다.이 문제는 플로이드 워셜 알고리즘을 사용해 문제를 풀어야 했다

고속도로 위에 n개의 센서를 설치한 후 최대 k개의 집중국을 세울 수 있다는게 중점이다.이 때 수신 가능 영역 길이의 합이 최소가 되어야 한다.우리는 입력받은 k개의 센서를 오름차순으로 정렬해준 뒤, 각 센서 사이의 거리를 계산한 뒤 오름차순으로 정렬해준다.이때, 두

이 문제는 비트 마스크로 접근하면 쉽게 풀린다.자바에서는 Int 타입을 2진수로 바꾸려면 Integer.toBinaryString() 메서드를 사용하면 된다.이때 왜 비트 마스크를 사용해야 하나면 물병 두개를 합쳐 하나의 물병으로 만들수 있는 구조는 이진수 덧셈과 같은

처음에는 그냥 배열로 풀려고 하다가 주어진 범위를 보고 세그먼트 트리를 이용하여 풀었다. 풀다보니 백준 2042번 구간 합 구하기 문제의 형식과 비슷함을 알게 되었다.처음에는 트리를 초기화 해준 후, 주어진 x ~ y 사이의 합을 먼저 구해준다. 초기화와 합을 구해주는

먼저 이 문제를 풀기 위해서는나이를 방향 그래프로 표현이때 나이라고 생각하지 않고 갈 수 있는 방향이 있는지 없는지 확인없다면 "gg" 출력입력이 다음과 같이 주어졌을 때를 생각해보자.그럼 다음과 같은 id가 getId() 메서드에 의해 생성된다. 4는 불리지 않았기에

문제에서 주어진 문자열이 (100+1+|01)+ 의 형태와 일치하는지 검사해야 한다.보통 자바에서는 정규표현식과 매칭되는지 알아보기 위해 String.matches() 메서드를 사용한다.문자열 전체가 정규표현식과 일치해야 true 반환부분 일치가 아닌 완전 매칭 !이

먼저 좋은 구간이 무엇을 뜻하는지 알아야 한다.A < BA, B에 속하는 수는 모두 S에 포함되지 않아야 한다.일단 어떤 수 x가 있을 때 x보다 작은 가장 가까운 원소와 x보다 큰 가장 가까운 원소를 찾아야 한다.그래서 다음과 같은 방법을 사용했다.1\. S 정

먼저 문제를 풀기 위해 4블록이 연속하다면 삭제해주는 과정과 이렇게 삭제된 블록들이 어떻게 아래로 떨어지는 것을 구현할 지를 고민했어야 했다.removed 배열 : 각 칸이 삭제 대상인지 여부를 true/false 로 저장한다.2×2 탐색 중 조건에 맞으면 해당 영역

먼저 홀수, 짝수일 때를 고려해야 한다.짝수의 경우 맨 오른쪽 비트가 0이기에 +1을 해주면 된다.하지만 홀수의 경우 +1을 해줬을 때 2비트 이상 바뀌는 경우가 존재할 수 있기에 값을 보강해줘야 한다.그래서 시프트 연산자와 XOR 연산자를 사용해 가장 작은 수를 구하

일단 문제 접근을 위해 new int\[n]\[n] 2차원 배열을 생각한다.각 2차원 배열에 반시계 방향으로 채워넣은 값들을 넣고, 이를 추후에 answer 배열에 넣어주는 방식으로 접근했다.이렇게 총 3방향으로 나눌 수 있는데, 이 방향은 i 변수를 사용해서 각각 x

이 문제는 그림을 그려보면서 점화식을 도출하면 동적 계획법 방법으로 쉽게 풀 수 있는 문제였다.그림처럼 dp\[n-2]+dp\[n-1]의 값이 dp\[n]이 됨을 확인할 수 있었다.이때 여기서 1000000007 이 값을 나눠줘야 하는데 그 이유는 무엇일까?바로 정수