Minimal Hustle, Maximum Impact

먼저 시간복잡도와 Big-O를 설명하기앞서..알고리즘에 대한 이야기부터 시작. 알고리즘을 사람들이 어렵게 생각하는데 알고리즘은 단순히 특정한 목적을 이루기 위한 방법, 프로세스다. 예로 자전거를 타고 예술의전당에서 우리집까지 가는 일련의 과정, 일련의 절차를 알고리즘이다. 예시를 알고리즘으로 만들면 아래와 같다: function RideBicycle(from, to) { /* 1. 자전거를 탄다 2. from(출발지), to(목적지)를 설정. 3. 최단거리 루트를 결정 4. 출발하는동안 적색 신호등이면 정지, 녹색 신호등이면 출발. 5. 도착하면 자전거에서 내린다. */ } 위의 예시처럼 알고리즘은 1. 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정이며 2. 가는 루트는 다양하..

얼마전 **기업 코딩테스트를 보고 첫문제부터 멘붕에 빠졌었던 문제이다. 다시풀어보니 쉽네.. 왜 멘붕에 빠졋을까.. 시간제한이 있으면 그런것같다. 시간제한이 있어도 탈압박 할 수 있는 능력을 길러야겠다. 문제설명: 입력으로 숫자의 갯수와 총 더할 수 있는 갯수, 특정한 인덱스의 숫자가 중복 될 수 있는 한계의 수가 주어진다. (N은 숫자의 갯수, M은 총 더할 수 있는 갯수, K는 특정한 인덱스의 숫자가 중복 될 수 있는 한계의 수) 출력으로 총 더한 최대값을 출력한다. 말로는 제대로 설명이 안되니 예제를 보여주겠다. ex) 입력으로 -> 5 3 2 4 2 3 1 3 5는 주어질 숫자의 갯수를 나타내고, 3은 총 더할 수 있는 갯수, 즉 3번만 더해서 최대값을 만들어야함. 2는 특정한 인덱스의 숫자가 중..

문제 출처: https://www.acmicpc.net/problem/14890 나의 접근 방법! 1. 오르막, 내리막, 평지 일때만 생각했다! 그 외 나머지(ex. 1,3처럼 차이가 1 초과인 것들은 경사로를 못만드니)는 고려할 필요가 없다! 2. 오르막일떄(ex. 1,2) 밑변의 길이가 주어진 기울기의 밑변의 길이보다 같거나 크면(count >= L) count를 1로 초기화. 3. 내리막일때(ex. 2,1) 밑변의 길이가 0보다 같거나 크면count를 0으로 초기화. 4. 평지를 만나면 count+1. 5. 좌표의 맨 끝에 도달했을때 count가 0보다 같거나 크면 그 길을 지나갈수 있는 길로 판단 ret++ 해주면 완성. 코드를 보면 직관적이라 이해할 수 있을것이다! static void solv..

문제 출처: https://www.acmicpc.net/problem/1759 나의 접근 방법! Backtracking 자체를 이해하기가 어려워서 하나하나 손코딩으로 입력해줘서 이해를 하였다. 풀이를 참고하여 이 문제를 이해하며 풀었는데 굉장히 어려웠다. static void backTracking(int index, int cnt, int mo, int ja, String s) { if(cnt == selectNum) { if(mo>=1 && ja>=2) System.out.println(s); return; } if(index == maxNum) return; if(strArr[index] == 'a' || strArr[index] == 'e' || strArr[index] == 'i' || strA..

문제 출처: https://www.acmicpc.net/problem/2178 나의 접근 방법! 간단한 BFS 문제지만 나는 초급자 이므로 이해하는데 꽤나 헷갈렸다 ㅎㅎ 1. Queue에 들어온 순서대로 첫번째 front를 꺼낸후 그 좌표의 상하좌우에 1이 있는지 확인한 후에 있다면 큐에 넣어준다. 2. 그 좌표의 상하좌우에 1이 있다면, 그 좌표의 값에 1을 더한 값을 상하좌우에서 발견한 좌표에 넣어준다. (간척사업 처럼) 3. 큐가 빌때까지 이 과정을 반복하고 출력을 map[N-1][M-1]의 값을 해주면 이동한 횟수가 나올 것이다. 나의 소스코드 : https://github.com/wopuv48/Algorithm_Practice_for_Tests/tree/master/FindRoad

문제 출처: https://www.acmicpc.net/problem/15683 나의 접근 방법! 핵심 키 포인트! static int[] Dr = {0, -1, 0, 1}; //0-right, 1=up, 2=left, 3=down static int[] Dc = {1, 0, -1, 0}; static int[][] Dcam = { {1, 0, 0, 0, 4}, {1, 0, 1, 0, 2}, {1, 1, 0, 0, 4}, {1, 1, 1, 0, 4}, {1, 1, 1, 1, 1} }; 요것을 가지고.. Dcam의 각행에 따라 카메라 타입을 나누어서 인덱스번호 0 = 오른쪽, 1 = 위쪽, 2 = 왼쪽, 3 = 아래쪽 으로 각각 설정해서 감시할 수 있는 경로를 미리 설정하고 90도 회전할 수 있는 경우의 ..

문제 출처: https://www.acmicpc.net/problem/9663 나의 접근 방법. (N-QUEEN의 이해를 돕기 위한 사진) * 하나의 줄에는 하나의 퀸만, 따라서 이차원 배열이 필요 없다! * 직선과 대각선은 필터링! queen(i) isPromising? col[i] = 1~n; queen(i+1); 이렇게 하면 전수조사가 되지만 queen(i) isPromising? i가 n까지 왔는가? 그럼 출력 col[i] = 1~n; queen(i+1); 이렇게 하면 답이 나온 경우 그만 체크하고 결과를 보여줄수 있다. 나의 소스코드: https://github.com/wopuv48/Git-Tutorial/tree/master/N-queen

문제 출처: https://www.acmicpc.net/problem/2667 나의 접근 방법. 1. 이차원 배열을 하나 만들어 그안에 입력 받은 값들을 넣어준다. 2. boolean 타입의 이차원 배열을 하나 또 만든다.(방문 체크용) 3. BFS를 만든다. 4. 우선순위 큐를 만든다.(우선순위 큐는 작은 수부터 우선적으로 나오기 때문에 필요) 5. 이차원 배열을 하나하나씩 돈다. 0이면 패스 1이면 방문 체크용 이차원 배열에 체크하고 그 좌표를 기준으로 BFS를 실행한다. 6. BFS를 실행한 결과(조회된 주택의 수)를 우선순위 큐에 넣어준다. 7. 다시 그 기준점의 좌표로 돌아와서 다음 좌표로 이동. 8. 0이면 패스 1이면 4번 과정으로 한다. 나의 소스 코드: https://github.com/..

입력받은 값을 단수로 정해서 정삼각형 만들기. 오랜만에 해보는 거라 머리가 아팠지만 차근차근 해보니 규칙을 찾을 수 있었다. 나같은 경우는 변수를 포인트로 해결했다. 아래는 코드 package first; import java.util.Scanner; public class firstTest { public static void main(String[] args) { Scanner st = new Scanner(System.in); int n; int a; do { System.out.print("n:"); n = st.nextInt(); a = n; } while(n 0; k--) { System.out.print("*"); } a--; System.out.println(); } } }