알고리즘

[코드트리 조별과제] lower, upper bound

이진탐색 중 Lower Bound와 Upper Bound가 있다. 정렬된 배열에서 같은 값이 여러개인 경우 해당 알고리즘을 사용한다. - Lower: 같은 값들 중 가장 왼쪽에 있는 인덱스 리턴- Upper: 같은 값들 중 가장 오른쪽에 있는 값 한칸 옆에 있는 값 리턴 -> 1,2,3,3,3,4배열에서  target = 3인경우 4가 있는 위치 리턴 function lower_bound(arr, target) set left = 0 // 첫 번째 원소의 위치로 설정합니다. set right = arr.size - 1 // 마지막 원소의 위치로 설정합니다. set min_idx = arr.size // 최소이므..

[코드트리 조별과제] 시간복잡도

시간 복잡도에 대해서 배웠다. 대부분 아는 이야기지만 감각으로 깨우친 내용이다. 보통 1초 내 풀려야하는데 1억번 이하로 풀어야한다는 내용을 콕 집어서 가르쳐 주지 않는다. 또한 많이 쓰는 N2 시간복자도도 입력이 100000일 경우 시간초과 나는 사실도 문제를 틀려보면서 배워서 이렇게 집어줘서 알고리즘을 막 시작하는 사람들에게 좋다.

[JAVA 자바] 프로그래머스 PCCP 모의고사 3번 유전법칙

https://school.programmers.co.kr/learn/courses/15008/lessons/121685 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 재귀로 풀수있는 문제다. 다른풀이보면 스택과 큐로도 풀었던데 스택과 큐로는 잘 모르겠다. 재귀로 풀때 핵심 재귀로 풀때 핵심은 주어진 세대와 인덱스[3,25]를 받아서 값이 있는 부모까지 재귀를 타고 부모의 값을 찾았다면 그에 해당하는 자식값을 리턴하는식으로 풀 수 있다. 무슨말이냐면 2세대의 인덱스가 1일때는 3을 리턴하고 2세대의 인덱스가 2일때는 4를 리턴한다고 치자. 5세대부터 재귀..

[JAVA 자바] 프로그래머스 과제 진행하기

https://school.programmers.co.kr/learn/courses/30/lessons/176962# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 굉장히 까다로운 구현문제다. 여러 조건들이 있고 그 조건을 하나도 빼먹으면 안 되며 문제에 정확히 명시돼있지 않더라도 예외 케이스들을 다 추가해서 구현해야 한다. 배열 VS 우선순위큐 배열을 정렬한 뒤 index를 사용해서 값을 구해도 되고 우선순위큐를 사용해도 되는데 배열을 사용할 경우 까다로운 조건문안에서 매번 index++로 인덱스를 추가관리해야 하기 때문에 우선순위큐를 사용했다. 현재 ..

[JAVA 자바] 백준 2179

https://www.acmicpc.net/problem/2179 2179번: 비슷한 단어 첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다. www.acmicpc.net 가장 먼저 떠오른 방법은 모든 문자의 모든 경우를 구하는 방법이다. 하지만 입력길이가 20000이기 때문에 N * N * 100으로 시간초과가 난다고 판단했다. 떠오른 방법은 문자를 1자리 2자리 3자리 ...N자리로 다 나누고 set에 넣어 비교하는 방식을 생각했다. S와 T를 저장해서 출력해야 하는데 이 방식은 접두사가 같은 문자를 찾아도 S를 찾을 수가 없었다. 결국은 Map에서 키로 자른문자 value로 원본문자를 넣어서 S와 T..

[프로그래머스] 혼자 놀기의 달인 자바

https://school.programmers.co.kr/learn/courses/30/lessons/131130?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 처음에 cards안에 card를 기준으로 방문체크를 하면서 dfs를 순회했는데 테케5번에서 에러가 낫다. 코드를 자세히 보니 dfs로 들어갈 때 현재 내 배열이 아니라 다음 배열에 true표시를 하는 것 같았고 card로 순회하지 않고 배열 인덱스를 기준으로 순회하니 해결됐다. 틀렸던 코드 package programmers.level2; import java..

여행경로 자바

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 여행경로 L3 첫 접근 for문을 수행해서 ICN인경우 dfs를 수행하고 방문처리를 한다. dfs를 수행하면서 리스트에 값을 담고 다 순회했는지 확인한다. 다 순회했는지 확인하는건 visited를 for문 돌려서 참인 경우 2차원 리스트에 해당 리스트를 반환한다. 위 방법으로 하려고 했지만 구현에 실패했다. -> 실패코드 public class 여행경로 { static List list = new..

백준 1003 피보나치 함수 자바

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 틀린 줄 알았는데 맞았다. 접근 아이디어 0의 개수와 1의 개수를 출력해야한다. 피보나치에 dp를 접목시키는 방식은 배열안에 피보나치의 값을 넣어서 값이 있다면 배열을 리턴하는 방식으로 문제를 푼다. 하지만 이 문제는 도통 감이 잡히지 않았다. 막연하게 n만큼 배열을 만들고 n이 가지고 있는 0의 개수와 1의 개수를 리턴하는 식으로 구하면 되지 않을까?? 라고 생각했다. 구현 방식이 깔끔하지 못하고 매번 배열을 리턴하는 방식이 맞는가 싶은 의구심이 들었는데 맞았다. 0과 1은 함수내에서 구현하..

백준 14889 자바 스타트와 링크

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 접근 아이디어 조합으로 풀었다. tgt배열에 true false값을 넣어서 조합의 절반만 순회하도록 하고 절반을 순회했다면 연산을 했다. 2중for문에 j = i+1을 하면서 대각선기준 아랫방향은 접근하지 않도록 하고 ij와 ji를 더해서 최솟값을 갱신하는 방식으로 풀었다. 잘 한 부분 조합을 생각한 것과 절반만 순회하는 아이디어를 잘 떠올렸다. 합칠 때도 양쪽을 한번에 구하는 방식을 어렵지 않게 구현했다. 부족한 부..

백준 14888 자바 연산자 끼워넣기

접근 아이디어 연산자 배열이 2, 3, 0, 1 이렇게 주어졌다면 하나씩 줄이고 재귀로 탐색한다. 숫자 배열을 매번 연산해서 재귀 탐색을 진행할 것이므로 depth는 1부터 시작하고 0번째 값을 sum이라는 인자로 보낸다. for문으로 연산자를 하나 선택했다면 calculrator함수를 이용해서 바로 연산을 진행한 뒤 재귀를 수행한다. 잘 한 부분 크게 어렵지 않았고 연산을 따로 함수로 구분해서 보기 편하게 코드를 짯다. 부족한 부분 연산자를 감소시키고 재귀를 돌렸으면 다시 증가시켜야 하는 부분을 깜박했다. package backjon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; i..