알고리즘10 알고리즘 공부 방법 1. 시작할 때 (언어를 선택하라) 언어를 선택한 후, codeup에서 기초 100문제를 풀어야 한다. codeup 2. 백준 문제를 푼다. 1) 그리디 알고리즘 문제를 푼다. 쉬운 난이도와 문제들 중에서 그리디 알고리즘 유형이 많이 출제 된다. 2) 탐색 문제를 푼다. 완전 탐색, BFS, DFS를 공부하면 된다. 3) 기초 동적 프로그래밍 푼다. 1), 2), 3)를 50문제씩 백준에서 푼다. 3. 프로그래머스 기출문제를 푼다. 1) kakao 2) 삼성역량테스트 코드포스 블루레벨 정도면 코딩테스트 합격 가능하다. 또는, 삼성 역량 테스트 B형으로 정도면 합격 가능하다. 참고자료 https://youtu.be/ukkLCl9yBvE 2021. 10. 11. 1. 그리디 알고리즘 (Greedy Algorithm) 단순하지만 강력한 문제 해결 방법이다. 국내 알고리즘 교재에서 단어 그대로 번역하여 탐욕법으로 소개된다. 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 탐욕적 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 매 순간 가장 좋아 보이는 것을 선택한다. 그리디 알고리즘은 문제 출제의 폭이 매우 넓기 때문에 단순 암기를 통해 모든 문제를 대처하기 어렵다. 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다. 무작위로 주어진 경우에는 그리디 알고리즘으로는 해결할 수 없다. (무작위인 경우는 다이나믹 프로그래밍으로 해결할 수 있다.) 대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있.. 2021. 9. 21. Part 01 코딩 테스트, 무엇을 어떻게 준비할까? 코딩 테스트 준비를 돕는 다양한 서비스 알고리즘 공부할 때 Part 02를 이해한다. Part 03 관련 문제를 푼다. 백준 온라인 저지에서 관련 문제 50개를 푼다. 백준 온라인 저지 : 삼성 SW 역량테스트 대비 문제집 제공 프로그래머스 : 카카오 공채 문제집 제공 삼성전자 : DFS/BFS를 활용해야 하는 탐색과 시뮬레이션 문제 유형을 자주 출제한다. (상시 SW 역량테스트 A형 문제와 유사하게 출제 된다.) 복잡도 알고리즘의 성능을 나타내는 척도 시간 복잡도 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미 알고리즘을 위해 필요한 연산의 횟수 빅오 표기법을 사용한다. (가장 빠르게 증가하는 항만을 고려하는 표기법) int arr[5] = [3,5,1,2,4]; int summar.. 2021. 9. 14. 알고리즘 풀 때, 주의할 점 Algorithm 풀 때 주의할 점 1. 문제에서 제시 된 행렬을 잘 판단 해야한다. 좌표가 m = 4, n = 3인 격자모양이 있을 때 행 : n, 열 : m이다. 이때, 잠긴 지역의 좌표를 담은 2차원 배열 puddles가 있을 때 puddles[i][j] i 는 열이다. j 는 행이다. 행렬 판단을 잘 해야 한다. 참고 자료 코딩테스트 연습 - 등굣길 | 프로그래머스 (programmers.co.kr) 2021. 8. 19. 완전 탐색이란 무엇인가? 완전 탐색 (Exhaustive Search) 모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘이다. 알고리즘을 풀 때 가장 강력하고 확실한 방법이지만 시간이 가장 오래 걸리는 탐색 기법이다. brute fore algorithm이라고도 불린다. 자원만 충족해준다면 항상 100%의 정확도가 보장된다. 0000 ~ 9999로 이루어진 임의의 비밀번호를 찾고 싶을 때, 가능한 모든 조합은 1만 개(10^4)이다. 완전탐색 기법의 종류 Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법 비트 마스크 : 이진수 표현을 자료구조 쓰는 기법 (AND, OR, XOR, SHIFT, NOT) 재귀함수 순열 : 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 늘어 놓은 수.. 2021. 8. 18. Dijkstra 알고리즘이란 무엇인가? 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘 : 하나의 정점에서 다른 모든 정점들의 최단 경로를 구한다. 다익스트라 알고리즘의 기본 로직 : 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며, 최단 거리를 갱신하는 것이다. 정점을 잇기 전까지는 시작점을 제외한 정점들은 모두 무한 대 값을 가진다. 1. 다익스트라 알고리즘 기본 로직 시작점 : 5번 정점 5번 노드를 제외한 나머지 정점들이 가지는 최단 경로는 아직 연결되지 않았으므로 무한대이다. 1) 경로가 가장 짧은 정점을 고른다. 시작 점, 5번 노드와 연결되어 있는 노드는 2, 4번 노드이다. 2번 노드 dist[2] = min(dist[2], dist[5] + adj[5][2]) min(INF, 4) = 4 4번 .. 2021. 8. 15. 이전 1 2 다음
