programmer life guidance 101

> 다익스트라 알고리즘 이제부터 그래프에 대한 글만 엄청 쓸 겁니다. 한 11~12개 정도 예정되어 있네요. 그래프... 정말 어렵고, 답없고, 온갖 문제가 많기로 유명합니다. 그 중에서도 처음을 장식할 최단 경로 알고리즘은 그 종류부터 3개나 됩니다. 그 중 첫 번째 알고리즘인 다익스트라 알고리즘(Dijkstra's algorithm)에 대해서 알아보겠습니다. 이 알고리즘이 하는 일은 그래프의 어떤 정점 하나를 시작점으로 선택하고, 나머지 정점들로의 최단거리를 모두 구합니다. 시작점 자신이야 뭐 그냥 0입니다. 정점 개수가 V, 간선 개수가 E일 때 기본적인 최적화를 거치면 O(ElogV)의 시간복잡도를 갖습니다. 그래프는 무향이거나 유향인데 대체로 유향인 경우가 많고, 간선마다 이동거리가 존재합니다...

프로그래머스 2020 KAKAO BLIND RECRUITMENT 블록 이동하기 :https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 대표적인 BFS 구현문제 인줄 알고 쉽게 덤벼들었지만, 고려해야 할 게 많아 꽤 까다로웠다. 처음 생각은 bfs로 회전과 직선이동을 나누고 동서남북대각선 체크해주면서 벽이 아닌 곳의 최대좌표를 리턴해주며 최소시간을 구하는 것이었다. 하지만 테스트케이스를 충족하지 못하였고, 다른 블로그를 참고해서 답을 고쳤다. (..

> 알고리즘의 분석 알고리즘의 자원(resource) 사용량을 분석 자원이란 실행시간, 메모리, 저장장치, 통신 등 여기서는 실행시간의 분석에 대해서 다룬다. 시간복잡도 실행시간은 실행환경에 따라 달라짐 하드웨어, 운영체제, 언어, 컴파일러 등 실행시간을 측정하는 대신 연산의 실행 횟수를 카운트 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 데이터의 크기가 같더라고 실제 데이터에 따라서 달라짐 최악의 경우 시간복잡도(worst-case analysis) 평균 시간복잡도(average-case analysis) 점근적(Asymptotic) 분석 점근적 표기법을 사용 데이터의 개수 n → ∞ 일때 수행시간이 증가하는 growth rate로 시간복잡도를 표현하는 기법 Θ-표기, Ο-표기 등을 사용..

알고리즘을 위한 자바 IO codeplus - 프로그래밍 대회에서 사용하는 Java 참고 System.out System.out.println(); System.out.printf("%d", n) 실수형, 문자형 자료 출력 가능 Scanner next[자료형]을 이용해서 입력을 받을 수 있고, hasNext[자료형]을 이용해서 입력받을 수 있는 자료형이 있는지 구할 수 있다. 두 수 입력 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int a, b; a = scanner.nextInt(); b = scanner.nextInt(); System.out.println(a..

> N-Queens (Back tracking) (n = 8) 아래의 예(n=8)에서는 8x8 체스보드에 8개의 말을 놓는데 그 중에 어떤 말들도 동일한 행, 동일한 열, 동일한 대각선 상에 오지 않도록 n개의 말을 놓을 수 있는가에 대한 문제이다. 위의 방법대로 n개의 말을 놓으려면, 결국 조건을 만족하면서 하나의 행에 하나의 말이 와야한다. Back Tracking 내가 지나온 길을 다시 되돌아 가면서 문제를 해결한다 어떠한 결정들을 내려가다가, 결정이 막다른 길이다. 즉, 그 결정을 내려서는 안된다라는 것이 분명해지면, 가장 최근에 내렸던 결정을 번복한다. 이런식으로 문제를 해결한다. 상태 공간트리 1번말이 (1,1)에 위치했을 때, 그리고 그 때 2번말이 (2,1), (2,2), (2,3), (2..

> 회문판별 회문은 유전자 염기서열 분석에서 많이 쓰인다 회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 말한다. #define _CRT_SECURE_NO_WARNINGS #include #include #include int main(){ char word[30]; // 단어 저장 배열 int length; // 문자열 길이 bool isPalindrome = true; // 회문 판별값을 저장할 변수, 초깃값 TRUE printf("단어 입력하세요: "); scanf("%s", word); length = strlen(word); // 0부터 문자열 길이의 절반만큼 반복 for(int i=0; i