처음 인접리스트와 인접행렬을 공부하면서 참고한 사이트가 있습니다. 제 블로그에서는 해당 블로그글을 요약하는 형태로 작성해보았습니다!https://sskl660.tistory.com/60 그래프를 표현하는 경우는 크게 두 가지 방법이 있습니다.(인접행렬과 인접리
합병 정렬은분할정복 알고리즘 중 하나 라고 볼 수 있습니다. 그럼 분할정복 알고리즘이란 무엇인가?문제를 두 개의 작은 문제로 쪼개고, 나눈 두 문제를 해결시도한다. 만약 해결이 안된다면 다시 두개의 작은 문제로 쪼개고, 나눈 문제에 대하여 해결시도한다. ...이렇게 반
2차원 배열의 합을 알아보기 이전에, 1차원 배열의합으로 감각을 익히고 가봅시다. 백준 사이트에서 1차원 배열 합을 익히기 좋은 문제가 있죠 백준 11659번 구간 합 구하기 4위의 사이트는 1차원 배열의 합과 관련된 문제, 아래 링크는 2차원 배열의 합과 관련된 기본
일반적으로 1억 번(10^8)의 연산은 1초입니다.빅- 오 O(n) 표기법을 기준으로 코딩테스트에서 수행시간을 계산합니다. 모든 테케를 통과해야만 합격으로 판단하므로 최악일 때를 염두해야 합니다.시간 복잡도 표기법빅-오메가 : 최선일 때 연산 횟수빅-세타 : 보통일 때
플로이드 와샬 알고리즘을 사용하는 경우는, '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하고 싶을 때 사용합니다. 이와 반대로 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘입니다. 핵심 아이디어는 '거쳐가는
하노이탑 문제 - 프로그래머스처음에 계속 종이에 기둥 3개를 그려놓고 n=3, n=4, n=5, ... 이렇게 계속해서 작성해보았다. 내가 찾은 규칙은 이러하다.1\. n이 짝수인 경우 처음시작(n=1)은 두번째 기둥이고 이후에는 세번째 기둥, 두번째 기둥을 번갈아간다
SWEA - 최대상금 문제업로드중..List list 선언으로 입력받은 숫자를 한 자리씩 list.add(0, 숫자)로 입력길이가 2인 1차원 int배열 plus(swap 할 num의 모음)와 1차원인 boolean배열 전역 선언/최대 교환횟수 count 전역 선언fi
SWEA 단순 2진 코드 문제이번 문제는 정확한 문제 설명도 없고 약간의 유추도 필요했던 문제다. 특히 문자열에 대한 정확한 이해와 판단이 있고 배열 활용을 잘하면 잘 풀 수 있는 문제라고 생각한다. 나는 3시간 정도 시간을 들여서 문제를 풀었지만 더 쉽게 풀 수 있는
이번 문제에서 약간의 난항(?)을 겪었다. ArrayList와 LinkedList를 섞어서 쓰던 탓이었는지 이번 문제에서는 LinkedList를 선택해서 문제를 풀었다. 이 때문에 시간초과 라는 문제에 계속 놓였다.알고보니 LinkedList와 ArrayList에는 속
백준 - 행복 유치원 문제 링크이 문제는 그리디 문제로, 키 순서대로 나열된 학생들의 키를 입력받고 그 중 그룹마다 키 차이의 합 중 가장 작은 값을 구하는 문제다. 위의 예시대로 5명(N=원생의 수)을 3개의 조(k)로 나누어야 하지만, 각 조마다 최소 한명씩은 있어
백준 1912번 링크이번 문제는 전형적인 다이나믹 프로그래밍의 기본문제를 가져와봤다. 내가 문제를 푼 방식과 이 문제의 정답이 약간 다른 부분이 있어서 기억하고 짚어가고자 작성하였다.for문 (1) dpi-1+arri<0 이라면 dpi = 0으로 초기화하고(+ b
이 문제를 풀면서 조합으로 푸는 방법밖에 생각나지 않았다. 시간초과가 날까 싶었지만 일수(15일)이 작아서 DFS로 풀었다.현재 날짜(idx)라고 할때, 일이 마치는 날짜(idx + (arridx -1))가 n일 안에 마치는 경우dfs(idx+arridx, sum+ar
백준 가장 긴 증가하는 부분수열4 - 문제 링크이번 문제는 백준 11053번 가장 긴 증가하는 부분 수열의 확장문제로, 링크는 여기다. 위 문제와 차이점이 있다면 가장 긴 증가하는 부분 수열의 원소를 오름차순으로 출력해줘야한다는 점이 추가되었다.인덱스 i = 1번부터
백준 포도주 시식 문제 링크3잔은 연속해서 마시시 않아야한다는 조건이 있다. 이 경우 현재 인덱스를 기준으로 oox, oxo, xoo와 같이 마셨는지 안마셨는지 3가지 상황에서 dpi값을 갱신하여 마신 최댓값을 구할 수 있다. 예로, 현재 인덱스가 2일 때를 생각해보자
백준 문제 링크이 문제는 left = 0, right = 'arr 배열 중 가장 큰 값' 이렇게 설정해놓고 이분탐색을 통해 문제를 해결할 수 있다.중간값인 mid = (left+right)/2 가 될 것이고, mid값이 타당한지 계속 체크해준다. 어떻게 타당한지 체크하
파일명 정렬 링크지문에서 요구하는 정렬 기준에 대해 이해하고 Arrays.sort의 new Comparator<>() 내부의 정렬을 잘 다룰 줄 알아야 풀 수 있는 문제다. HEAD는 숫자가 아닌 문자로 이뤄진다. 최소 한 글자 이상이며 문자열 비교시 대소문자 구
문제는 이해가 갔지만 어떻게 풀어야 할지 머리를 계속 굴렸지만 단번에 떠오르지 않았다. 쉽게 풀리진 않아서 스택/큐 카테고리에서 가장 마지막 섹션에 있는 것 같다. 가장 처음에는 스택을 이용해서 (값, 인덱스)를 담아서 스택에 있는 값보다 같거나 작도록, 혹은 같거나