알고리즘 Phase1

*오른쪽 pivot기준 정리 pivot기준 좌우로 정렬하고, 그 좌우 각각에 대해서 반복한다. 자세 pivot정하고 왼쪽부터 traverse하며 pivot보다 작은 수를 발견할때마다 왼쪽부터 저장한다. (traverse하는 포인터위치 수와, 왼쪽부터 ++되는 포인터변

정리주석 //bubble sort 아래 코드 참고

풀이과정 ( -> push() \-> push() ) -> stack.peek()가 (인지 아닌지 또는 else \_스택이 비어있는경우 \-> stack.peek()가 \[인지 아닌지 또

LinkedList를 구현한 Collection객체는 listIterator사용가능ListIterator<?> it = list.listIterator();함수 : hasNext(), next(), hasPrevious(), previous(),add(), rem

예를들어, 첫번째 입력값이 4 -> push,push,push,push,pop두번째 입력값이 3 -> pop세번째 입력값이 6 -> push, push, pop네번째 입력값이 8 -> push, push, pop다섯번째 입력값이 7 -> pop여섯번째 입력값이 5 ->

이 문제는 다음과 같이 stack을 이용하면 뒤 탑들의 신호를 수신하는 탑을 관리할 수 있다.1\. stack이 비어있다. -> 신호를 받는 탑이 없다.2\. stack의 top의 탑이 송신한 탑보다 크다 -> top의 탑이 수신한다.3\. stack의 top의 탑이

조건 1\. 모든 글자는 짝이 존재2\. 짝끼리 아치형 곡선을 이었을때 교차 존재 X풀이1\. 순서대로 넣으면서 stack.peek와 같으면 pop, else push2\. 다 넣었을때 stack.isEmpty()면 answer++

괄호문제, 좋은 단어, 탑 문제 등을 풀어보니 이제 알고리즘에서 Stack을 어떻게 활용하는지 알 것 같다.분명히 Stack은 과거의 기록을 기록하기 위한 것이라고 배웠는데도 지금까지 막연하게 거꾸로 data를 저장하는 객체라고 생각했었다.지금 느끼는 것은 당연한 얘기

해답들을 봐도 이해가 안간다내가 이상한건가

첫 BFS 문제이다BFS는 기본적인 코드 틀이 있다고 한다.준비물0\. 좌표 클래스ex) new Pair(x, y)1\. boundary exception 체크용 배열ex) int\[] bx = {1, 0, -1, 0};int\[] by = {0, 1, 0, -1};2

42%에서 시간초과 발생함

이 문제의 관건은 처음 시작할 때 익은 토마토가 여러개 일 수 있다는 것이므로, 츠마리 bfs탐색이 여러 곳에서 시작된다는 점이다.해답은 의외로 간단했다. 시작 지점을 모두 처음에 큐에 넣고 시작하면 되는 것이었다.\+그리고 미로탐색 문제와 마찬가지로 토마토가 익은 날

처음 시도에는 단순한 알고리즘으로 풀 수 있다고 생각해서 다음과 같은 풀이를 생각했다.처음 케이스 판별1\. 수빈이 동생보다 뒤에 있는 경우? -1만 반복2\. 앞에있는 경우? 아래 실행판별후1\. 거리차가 x보다 큰 경우 -> 순간이동2\. 거리차가 x보다 작은 경우

첫번째 풀이는 HashSet을 사용하는 것이다.HashSet은 HashMap을 이용하므로 Sorting하지 않고도 빠르게 Search가 가능하다.사용한 HashSet 메서드add()contains()

그 유명한 하노이 탑 문제하노이 탑의 풀이는 다음과 같다업로드중..start의 N-1개의 블록을 tmp로 옮긴다.start의 1개의 블록을 end로 옮긴다.tmp의 N-1개의 블록을 end로 옮긴다.이것을 재귀적으로 반복한다.이를 코드로 옮기면 다음과 같다.

백트래킹도 BFS와 마찬가지로 기본적인 틀이 있다고 한다. 명확하게 알려주는 곳은 없지만 내 나름대로 정리해보면 다음과 같다.static boolean\[] isUsed (사용 여부 표시 배열)static int\[] answer (정답 기록 배열)백트래킹 재귀함수 실

2차원 배열을 90도 회전 하는 공식for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ tmpi = arrn-j-1; }}

이전 문제 N과 M(1) 문제에 이어 N과 M(2) 문제이다.이 N과 M 문제 시리즈를 다 풀어 볼 작정인데 굳이 다 올려야하나 싶은 생각이 들었지만, 일단 이 문제 같은 경우는 쓰고 싶어서 한 번 써본다.문제 설명이전 N과 M(1) 문제와 문제 지문은 똑같다. 하지만

N과 M을 다 풀어보기에는 같은 문제를 여러번 푸는 느낌이라, 프로그래머스의 백트래킹 문제를 풀어보려고 했다. 그런데 프로그래머스를 들어가니 레벨측정을 위해 문제 하나를 풀어보라는 메세지가 떴다. 그래서 한 번 풀어보았는데 우연찮게도 이 문제를 백트래킹을 사용하여 풀게

하루종일 풀어봐도 답이 안나와서 해답을 본 후 차이를 중심으로 오답노트를 작성해 보겠다.나의 시도1\. 재귀로 탐색하는 범위 : 2차원배열을 돌면서 퀸 N개를 다 놓았을 때 return2\. 대각선을 검사하는 방법 : 현재 row, col을 기준으로 좌측상단을 구하고,

정렬문제는 정렬을 직접 구현할 일은 없다고 한다.라이브러리에 정렬해주는 함수가 있기 때문이다.풀이 시도디버깅 결과 답은 맞게 나오지만, 제출시 메모리 초과가 뜬다..대체 어떻게 해결해야 할까..해답아래 코드를 보면 어렵지 않게 이해할 수 있다.값의 갯수를 저장하는 co

DP하나의 문제는 단 한번만 풀도록 하는 알고리즘계산한 결과는 테이블(배열)에 저장 \_메모이제이션 기법점화식 세우기ex) 피보나치 : n = n-1 + n-2테이블(배열)만들기ex) static int d;초기값 정하기d0 = 0;d1 = 1;배열 채워넣기(Bott

첫 번째 풀이점화식 구하기1\. 한 번에 1계단 or 2계단n(테이블) = n(점수) + max(n-1, n-2)(테이블)2\. 연속 세 개는 Xn+3(테이블) = n(테이블) + n+1(점수) or n(테이블) + n+2(점수) or n+1(테이블) + n+2(점수)

풀이각 index숫자들의 연산횟수 테이블\* 각 숫자에 해당하는 index에, 그 숫자의 연산 최소 횟수 저장점화식n = Min(n-1, n/3, n/2)) + 1\* n = n-1의 연산횟수와, n/3의 연산횟수와, n/2의 연산횟수중 가장 적은 횟수\* 연산 횟수를

처음 봤을 때, 백트래킹 문제와 상당히 유사해보였고 이걸 어떻게 DP로 푸나 도저히 감이 안 왔다.그래서 바킹독 선생님의 힌트를 조금 얻어 풀게 되었다.힌트 : N = 4일 때,1(+3)1+1(+2), 2(+2)1+1+1(+1), 3(+1), 2+1(+1), 1+2(+

첫번째 시도생각끝에 일단 막무가내로, dpn = dpn-1 + (N-1과 다른 색 중 최솟값) 으로 풀어보았다.우선 답은 틀렸지만, IDE로 돌려본 결과 5개의 테스트 케이스 중 앞에 4개는 정답이었다.오답인 이유에 대해서 생각해본 바로는, 문제를 풀면서도 생각했었지만

첫번째 시도아무리 생각해봐도 감도 안와서 (바킹독 선생님 조언대로) 직접 테이블을 한 번 채워봤다.이렇게 그려놓고 다시 가만 생각해보니, 일단 홀수번째의 갯수는 이전 짝수번째의 갯수 +1 이라는 것을 알았다. 그래서 일단 dp홀수 = dpn-1 +1 까지는 생각했다.그

그리디 문제 푸는 방법: 같은 건 따로 없음, 그냥 iq테스트풀이가 틀렸을경우 오래 붙잡혀있을 가능성 높은 유형코딩테스트에서의 추천 전략 거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 100% 확신한다 -> 짜서 제출해보고 틀리면 빠르게 손절100%

Collections.sort와 Arrays.sort가 있는데 일단 Collections.sort를 예로 설명하겠다.int start, int end라는 데이터멤버를 가진 Meeting이라는 객체가 있다.이 "회의"객체를 시작시간을 기준으로 정렬하려고 한다.1\. 일단

첫번째 시도그냥 일단 바선생 풀이 참고하여 구현해봄답은 맞으나 시간초과

이전 시도https://velog.io/@seluo65/BFS-%EB%B0%B1%EC%A4%801926-%EA%B7%B8%EB%A6%BC이전 시도에서 뭔가 괴랄하게 엄청 열심히 짠 듯한데, 이번 시도에서는 짬밥?이 조금 쌓여서 그런가 3달만에 시도해 보는데도

Queue문제라고 해서 풀고 있는데, 프로그래머스 문제들은 그냥 그 문제유형을 가장한 구현문제 같다.아무튼 이 문제는 이전에 풀었던 기록이 있는데, 그때 기억에 따라 로직을 구현해봤다. 그럼에도 불구하고 그 때의 코드와 비교하니 훨씬 길이가 짧게 나왔다. 그래서 신기하

첫시도(오답)처음에는 이렇게 풀었다.가격 배열에서 다음 가격이 들어가면 그 앞의 모든 가격들에 대해, 시간계산이 끝난 가격은 skip시키고, 안끝난 가격은 시간을 ++해주고, 그 다음 새로온 가격보다 작으면 시간계산을 끝내주었다.arr = 가격arr = 시간arr =

이 문제도 유형은 정렬이기는 한데, 구현이 상당히 어지러웠다.일단 문제 이해하는 것 부터도 힘들었고, 설계도 아래 주석처럼 단계별로 딱딱 끊어보아야 겨우 구현할 수 있었다.게다가 처음 제출 할 때도 거의 자포자기한 상태로 냈는데, 한 번에 성공해서 깜짝 놀랐다ㅋㅋ

\* 개인 기록용 글이므로 풀이는 내용에 없음 sort함수의 Comparator에다가, compareTo함수를 이용해 String을 비교하는 정렬 문제의 좋은 유형인 것 같다. 처음엔 두 수의 같은 자릿수를 비교하며 더 큰 수가 나올 때까지 비교하는 로직을 직접 람다함

처음에 모든 수를 한 번씩 다 써봐야 한다는 것 외에, 예시 때문에 사용하는 순서도 상관이 있는 줄 착각했다. 그래서 도저히 모르겠어서 다른 풀이를 한참 보고 나서 이해했다. (알고보니 순서는 상관이 없었다.)우선 모든 수를 한 번씩 다 써봐야 한다.그래서 나는 자연스

레벨3의 BFS 문제이다.풀이백준 그림 문제와 비슷하다. 2차원 배열에서 이어진 그림들을 세는 것처럼, 존재하는 컴퓨터들 중 이어진 컴퓨터들을 세면 된다.그림은 2차원 배열에서 탐색한 칸에 1로 제거했다는 표시를 해주었는데, 여기서는 1차원배열에 탐색한 컴퓨터 번호에

1레벨 문제지만 내가 풀어본 완전탐색문제가 n과m이랑 NQueen문제밖에 없어서 풀이를 떠올리기 상당히 어려웠다.별 짓을 다해봤는데 결국 다른 블로그의 풀이를 참고했다.풀이1\. 어렵게 생각할 필요없이, 가로길이의 최댓값과 세로길이의 최댓값을 구하면 된다.2\. 가로길

이것도 전 문제인 최소직사각형과 마찬가지로 bfs알고리즘을 사용하지 않는 1레벨 완전탐색 문제였다.모듈러 연산자를 사용하는 핵심 알고리즘은 바로 떠올릴 수 있었지만, 출력조건인 "가장 높은 점수를 받은 사람이 여럿일 경우 오름차순하여 return' 부분을 떠올리기 어려

소수 찾기 문제가 여러개인 것 같던데 이 문제이다.(레벨2)수를 조합 가능한 모든 경우의 수를 찾아봐야 하므로 백트래킹 알고리즘을 사용하였다. 그런데 다 풀고 보니 수를 모두 사용했을 때의 경우의 수가 아니라 수를 모두 사용하지 않아도 그냥 만들 수 있는 모든 경우의

운이 좋았는지 풀이를 금방 떠올렸다.바로 (brown+yellow)는 사각형의 넓이와 같으므로 즉, (가로x세로)와 같다는 것이다.따라서 가로의 최댓값부터 가로의 최솟값까지 내려가면서, 그 사각형의 넓이에서 테두리를 제외한 값이 yellow의 크기와 같은지 검사하면 된

이 문제에서 중요한 부분은, 언뜻보면 그리디 문제로 생각하기 쉽다는 것이다. 그런데 아래 주석에도 있듯이 잘 (생각해)보면 결국 완전탐색이 필요하다. 그 이후로는 BFS를 이용해 그냥 잘 구현하면 된다.이하 코드 참고

나중에 다시 풀어보기풀이핵심 내용:bfs를 이용해 각 송전탑에 이어진 송전탑을 탐색하기 위해서, 인접행렬 2차원배열을 만들고 bfs에서 이 인접행렬을 참고하여 이어진 노드들을 확인함.

이 문제(소수 찾기)와 유사하다.특정 길이가 됐을 때가 아닌 모든 단계의 경우의 수에서, 현재 단계까지 만든 단어를 사용하는 부분이 똑같은데 이것만 알면 간단히 풀 수 있다.

그냥 피보나치 수를 구하는 것이 아니라, 주어진 수를 구할 때 피보나치 재귀함수에서 boundary contion에서 n이 0인 경우와 1인 경우 각각 몇 번씩인지 구하는 문제이다.일단 직접 재귀함수를 돌려보면서 카운트해보니 시간초과가 나왔다.그래서 각 수에서 0과 1

풀이삼각형을 내려가면서, 정수삼각형 배열에서 해당 칸까지 더한 최댓값을 DP테이블의 해당 칸에 저장한다. 구간 합을 더하는 것과 똑같은 전형적인 DP문제이다.단, 주어진 대상이 삼각형이라는 것이 문제다. 하지만 크게 어렵지 않은게, 주어진 예제 입력을 보면 아이디어가

풀이 -> 아래 코드 주석나름 고민을 해서 풀었는데 아이디어가 떠올랐다. 다른 사람들의 풀이도 똑같았다.알고리즘을 풀다보니 머리가 좋아지는 것 같다..ㅋㅋ

문제 풀이를 설명하기가 까다로워서 주석을 참고

풀이투 포인터를 이용하여 풀었다. 몸무게배열을 정렬한다.현재 가장 가벼운 사람 + 가장 무거운 사람 <= limit 이면 보트를 하나 추가한다. (그리고 가장 가벼운사람을 가리키는 포인터++, 무거운 사람을 가리키는 포인터--)만약 limit을 초과하면, 무거운

해쉬 : 정렬하지 않고도 빠르게 탐색이 가능한 자료구조HashMap<key, value> map = new HashMap<>();put(key, value)get(key)containsKey(key)for(Object o : map.keySet())HashS

String배열에서, 한 String을 접두어로 포함하는 다른 String이 있는지 찾는 문제이다.풀이를 한참 고민했는데(사실 못 풀었는데)알고보니 substring()을 사용하면 되는 문제였다.\* 그리고 subString이 아니라 substring(소문자)임을 주의

일단 해쉬 자료구조가 필요한 문제고, 풀이를 위한 아이디어가 또 있어야 한다.첫 번째 풀이 (오답)의상 종류를 선택하는 경우의 수를 구해서, 뽑은 의상 종류들로 만들 수 있는 옷의 조합을 구한다.ex) 상의, 신발을 뽑았으면, 상의 갯수 x 신발 갯수이 때, 의상 종류

프로그래머스 SQL고득점Kit의 1~2레벨 문제오답 개념 정리DATE_FORMAT(컬럼명, 날짜형식)

이전에 썼던 백트래킹문제 풀이 글의 하단에, 추가로 순조부(순열, 조합, 부분집합)에 대하여 이야기했다.순열, 조합같은 경우는 위 글의 백트래킹 방식으로 풀 수 있다고 보는데, 부분집합은 살짝 다르다. 위 글의 코드 패턴에서는 재귀함수 안에서 for문을 사용한다.부분집

이 문제는 순조부에서 조합에 해당한다.주어진 n개의 숫자 중 m개를 선택하는 모든 경우의 수를 찾아보아야 한다.조합 문제는 부분집합 문제와 상당히 유사한 것 같다.부분집합과 마찬가지로 재귀함수 내에서 for을 사용하지 않는다.설명은 다음 코드 주석을 참고

처음 공부했을 때 백트래킹 풀이로 알게 된(사실은 브루트포스 풀이가 더 정확한), 코드 틀에 대한 글을 썼다. 그런데 순조부(순열,조합,부분집합)라는 유형이 있다는 것을 알게 됐고, 백트래킹 문제와 풀이가 거의 유사했다. 그 이유는 사실 모두 브루트포스 유형 즉, 모든

조합의 살짝 응용문제이다.현재까지 데브코스를 진행하며 배운 순조부 알고리즘 지식 + stream API 를 이용하여 혼자서 풀게 된 문제인데 기념으로 작성ㅎ

BFS로 풀 수 있는 문제를 DFS로 풀수 도 있다.따라서 다음 문제를 BFS로도 풀어보고, DFS로도 풀어보았다.백준4963 섬의 개수 : https://www.acmicpc.net/problem/4963아래 풀이를 보면, DFS가 좀 더 직관적이다. 왜냐하