Algorithm - Java

Programmers에서 sql을 풀고 나서 알고리즘을 도전중이다. 실행 & 테스트 환경이 편한 장점이 있다. 효율성까지 고려한 정답은 아래와 같다.

맨 처음에 뒤집을 문장의 개수를 입력하고, 이후에 입력한 문장들의 단어를 뒤집어서 개행으로 리스트 출력한다. 클래스 이름이 Main이어야 한다. import한 클래스들은 포함해야 한다.오답 이유 뒤집기는 성공했는데 1줄만 고려해서 짰다. length를 추가 안 함.개행

결과 : 정답 (를 넣는 leftStack와 )를 넣는 rightStack을 별도로 선언하고 줄마다 괄호를 쪼개는 것은 for문과 charAt()메서드를 사용해서 nextToken()을 처리하는 방식을 썼다.

결과 : 예시 결과는 제대로 출력했지만 오답 cnt를 이용한 for문에서 k 초기화에서 cnt + 1하지 않아서pop하는 조건 분기처리를 틀려서 (값이 다를 경우 바로 NO를 출력하도록 하기)cnt++이 아니라 inputNum값으로 엎어치기하는 것이다. 중간에 NO인

명령어에 따라 커서를 바꿔가며 문자를 추가 또는 삭제한다. 최종적으로 문자열을 출력한다.시간초과로 실패.substring과 StringBuilder 조작을 해서? 더 나은 방법을 찾다가 2개의 스택으로 풀라고 해서 다시 풀었다. 훨씬 코드가 간결하다. leftStack

큐를 직접 구현하기 성공 구현과 로직은 머리 안에 있었는데 문제를 제대로 안 읽어서 헤맸다. push는 print하면 안되고 문제 제출할 때 클래스명과 제출할 때 문제 확인하는 걸 잊었다;;push x와 같은 명령어의 경우 명령어와 파람을 분리해야 하는데 기존에는 ch

결과 예제는 제대로 출력하지만 틀렸음. 오답노트 소요 시간 1.5일

업로드중.. 스택 결과 정답 어려웠던 점 스택은 정적과 동적으로 나뉘는데 arrayList로 구현은 가능한데, 배열로 구현하는 것이 어려웠다. 배열은 선언순간부터 크기를 지정해야 하기 때문에 length가 항상 값들이 다 들어있는지 확신할 수 없다. 그래서

업로드중.. 덱(Deque) 덱을 util 쓰지 않고 구현하기 덱(Deque)이란? 스택과 큐만 들어보고 덱은 처음이었다. 덱은 양방향 큐와 같다. 앞뒤로 선입선출이 가능한 구조이다.

띄어쓰기를 기준으로 단어 내부 순서만 뒤집기태그로 감싸져 있는 경우 태그의 순서는 그대로 두고 <>안의 단어만 내부 순서 뒤집기(띄어쓰기 내부 적용 마찬가지)처음에 if문이 3중 이상으로 복잡해 지길래 ' '를 처리하는 경우와 <>를 추가하는 경우로 나누어서

업로드중..주어진 소문자 영어 단어를 보고, 단어에 없는 알파벳은 -1로, 있는 알파벳은 영어 단어 내의 index를 출력하라. 정답 원하는 값을 출력하기 위해서는 2가지를 알아야 한다. 1\. 알파벳의 아스키 코드 - 97 (소문자이기 때문에 -97을 한다)2\. 문

주어진 소문자 영어 단어를 보고, 단어에 든 알파벳의 개수를 배열로 나타내기. 정답 아래 부분과 배열 초기화를 0으로 한다는 점만 제외하면 알파벳 찾기 문제와 동일하다. 알파벳의 등장 횟수만큼 ++한다. 5분 내

문자열 N개가 주어졌을 때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하기 정답 알파벳 단어 문제에서 사용했던 빼기 방법을 사용해 보았다. (charAt(i) - 97) 보통 백준은 N으로 먼저 입력할 문장 등의 수를 입력받는데 이번에는 제한이

ROT13 알파벳 + 13번째 자리의 알파벳으로 문자열을 암호화하기.

접미사 배열 문자열 S가 주어졌을 때, 모든 접미사를 사전순으로 정렬한 다음 출력하는 프로그램을 작성하시오.

네 수 a+b와 c+d를 더한 값을 출력하여라.

중위 표기법을 후위 표기법으로 바꿔보자.

오큰수 해당 숫자의 오른쪽에 있는 숫자들 중에서 큰 수이며, 동시에 가장 왼쪽에 있는 수를 출력해야 한다. 결과 오답 -> 시간 초과(이중 for문) 오답 분석 스택에 항상 값만 담는 것이라고 생각했는데 배열 주소, 즉 인덱스를 담을 생각은 전혀 못 했다. 소요

위 문제는 백준 기초 > 소수 찾기와 관련이 있다. https://www.acmicpc.net/problem/1978 소수 구하기 풀이 Q. 에라토스테네스의 체 소수 판별 알고리즘으로 유명하다. 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)

주어진 숫자 배열에서 소수가 몇 개인지 찾아보자.

주어진 두 수의 최소공배수 구하기

첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000)첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다.정답

최대공약수와 최소공배수 유클리트 호제법이란? 최대공약수를 구하는 공식이다. 최소공배수는 주어진 로 쉽게 구할 수 있다. 결과 소요 시간 30분내

진법 변환을 한다는 것은 2진법은 2로, 8진법은 8로 지정된 숫자를 계속 나눈다는 것이다.

난 -2진법이라길래 2진법으로 이루어진 수의 보수를 구하는 것이라고 생각했다.

결과는 동일한데 틀렸다가, 답보고 제출했다가 몇 달 지나서 까먹은 채로 재도전해서 로직 맞추고, println() 형식만 틀림. > System.out.printf("%.2f", numberStack.pop()); 문제가 소수점 2번째 자리까지 출력이라

BigInteger의 두번째 매개변수로 원하는 진법의 숫자를 넣으면 그 값으로 변환할 수 있다.

BigInteger와 toString()을 쓰면 된다.

엉망진창 미래 진법 풀기

주석 달아가면서 열심히 풀었음.

나는 수빈이 기준으로 동생들 사이의 거리를 가지고 계산하는 줄 알았는데, 수빈이가 첫번째 동생부터 차례로 각 동생들 위치로 가면서 계산을 해야 한다.

어떻게 풀어야 하는지는 맞았는데 입력값 맨 앞의 수까지 연산에 넣어서 망함;;

문제 링크 https://www.acmicpc.net/problem/1676 최종 코드

백준 사이트의 테스트 케이스는 통과했으나, 20% 정도 채점하다가 틀렸습니다 판정받음

개인적으로 동적 프로그래밍은 처음 진입하기가 너무 어려운 알고리즘이었다.

빨간집은 이전 집이 초록색이거나 파란색일 때 가능하다. 초록집은 이전 집이 빨간색이거나 파란색일 때 가능하다. 파란집은 이전 집이 빨간색이거나 초록색일 때 가능하다.

dp[][]와 data[][]와 paint[]가 필요하다.

왜 i-j를 하냐면, i는 전체 카드팩의 수를 나타내고, j는 현재 사려는 카드팩의 개수이기 때문이다.

먼저 1,2,3을 나타내는 방법을 구해보자. 1 = 12 = 1+1, 23 = 1+1+1, 1+2, 2+1, 3그렇다면 4는?

나는 머리가 나빠서 손으로 해결하려들기에 또 일일이 다 그렸다.

풀이그림을 그려도 이해가 어려웠다. 일단 1, 2, 3의 경우를 직접 그려봐야 한다.

피보나치 수열이랑 풀이가 똑같다. 처음에 1~N자리의 이친수를 모두 구하는 줄 착각했다가 다시 풀었다. 궁리를 해보니 결국 피보나치였다.

2가지 방법이 있는데, 재귀 함수를 사용해서 푼다. 아님 초기화를 한 다음에 이중 for문으로 처리한다.

)가 나오면 stack.pop()을 하든 변수값을 --하든 해야 한다.이게 왜냐면, ()가 완성되어서 쇠막대기들이 일괄로 잘릴 때도...

01,2,3 더하기 시리즈 중 하나인데, 같은 숫자가 2번 이상 연속되면 안된다는 조건이 문제를 더 어렵게 만들었다.

처음 한 생각은 그냥 좌대각선 우대각선 중에 큰 값을 골라서 dp에 저장하면 되지 않을까였다. 물론 안된다.

아래 2가지 Action으로 끝낼 수 있다. 2차원 dp를 만들어 1자리수의 경우 1로 초기화한다. ...

풀이오르막 수랑 비슷한 거 같아서 진짜 혼자 풀려고 이 악물었던 문제렷다. 대충 아래처럼 표를 만들어서 점화식을 만들었다.

이 문제의 경우 기준점을 정하는 것이 중요했다. 이게 알고 나면 굉장히 간단함.

개인적으로는 하향식(bottom-up)을 선호한다. 포도주를 마시기 위한 3가지 조건을 잘 알아야 하는데, 하나도 모르겠어서 난항을 겪었던 문제.

이번에는 연관된 수열 문제 3개를 한꺼번에 정리해보겠다.

사실 2차원 dp를 선언하고 본인의 왼쪽 값과 위쪽 값을 더한 값으로 본인을 갱신하면 된다. 근데 그 점화식에 도달하기에 실패한 부분;;

위에서부터 왼쪽 대각선 또는 오른쪽 대각선으로 내려오면서 최댓값을 구하는 케이스다. 같은 층을 선택할 수 없다. 이 문제는 전형적인 dp로서 RGB류의 문제가 생각이 났다.

수학을 못해서인지 괄호를 칠 수 있는 범위를 잘못 생각했다. 난 단지 괄호랑 숫자를 한 페어로 생각해서 돌아갈 거라고 생각했는데~ 55-(50+40)결론적으로 덧셈끼리 먼저 계산해야 한다.

Arrays.sort() 또는 Counting Sort 알고리즘을 써서 배열을 정렬해서 이중 for문으로 본인 + 이전 값들 더하면 끝

국룰 탐욕 알고리즘 문제. ATM과 마찬가지인 방법으로 풀었다.값들이 오름차순으로 정렬되어 있을 때, for문을 돌려서 가장 큰 동전부터 나눈 몫을 count에 더하고, 나머지값으로 기존 K를 갱신했다.

처음에는 이전 회의실 끝나는 시간이랑 다음 회의실 시작하는 시간만 비교하면 될 것이라고 생각했는데 아님. 일단 회의실 배정 시간을 끝나는 시간이 큰 순으로 정렬을 한다.

DP와는 다르게 먼저 어떻게 정렬을 한 다음에 연산을 할 지를 생각해야 했다. 기존 연산 결과를 재사용하지 않는다, 다만 아직도 탐욕스럽게 가장 좋은 방법을 고른다의...

https://www.acmicpc.net/workbook/view/4380원하는 초콜릿의 개수를 0으로 만들어 가는 과정이라고 생각해야 한다. 열심히 구현했는데 시간 초과가 났다.

백준을 업로드하다 좀 뜸했는데, 그동안 공부 방법에 회의?를 느껴서 더 기초로 내려가고, 참고하는 자료도 기본 3개는 깔았다.

특정 배열의 인덱스별로 스냅샷을 생성하는 클래스를 구현하는 문제이다. TreeMap이라는 자료구조가 생소했는는데 이번에 floorEntry() 메서드로 새로 학습했다.

mid*mid가 num가 동일한지만 체크하면 된다.

two pointer 알고리즘을 easy, medium을 번갈아 가면서 풀고 있는데 기억해두고 싶은 것들을 간단히 적어보았다.