왜 알고리즘을 공부하는가? 가장 큰 이유는 취업. 특히 해외 기업은 전화인터뷰나 1차 인터뷰로 알고리즘과 관련된 문제풀이를 시키는 경우가 많다. 실무에서는 쓸 일이 없지만, 그래도 이런 부분은 항상 갈고 닦아놔야 나중에 큰 도움이 된다. 그리고 두번째 이유로는, 구글 코드잼에 참가해보고 싶은 욕심. 맨날 해야지 해야지 하면서 당일만 되면 귀찮아서 넘겨버리곤 했었다. 어떻게 공부할 것인가? 유명한 알고리즘 사이트로는 국내에선 백준과 프로그래머스, 해외에서는 리트코드가 있다. 개인적으로 프로그래머스는 문제의 퀄리티가 굉장히 좋아서, 잘 정돈된 문제를 풀고 싶을때 좋다고 생각한다. 리트코드는 문제가 굉장히 다양하고 많은데, 잘 큐레이션된 문제들을 한눈에 모아서 풀고 싶다면 돈을 내야하더라. 아마 알고리즘 첫 ..
백준 1463번 문제. 1로 만들기 [Point] 다이나믹 프로그래밍으로 차근차근 부분해부터 구해나간다 자칫 막막해보일 수 있지만 다이나믹 프로그래밍의 관점에서 곰곰이 공략법만 제대로 짚어내면 쉬운 문제다. *변수 설명*N : 입력 변수DP[x] : x라는 숫자를 1로 만들기 위해 필요한 "최소 연산의 횟수". 1의 경우엔 0번의 연산, 2와 3의 경우엔 1번의 연산이면 충분하고 최종해를 구하기 위한 최소한의 기본해이므로 미리 초기화해준다. temp : 각각의 연산으로 나온 DP[x]의 값을 미리 저장하는 변수. 이 변수를 DP[x]값과 비교하여 더 작은 값을 DP[x]에 넣어준다 *알고리즘 설명* D[N] 은 다음 후보 중 가장 작은 값이 될 것이다.1번 후보. D[N-1] + 1 2번 후보. D[N/..
백준 1003번 문제. 피보나치 [Point] 문제 예제에 주어진 코드를 잘 활용하여 fib(1)과 fib(0)이 나올 때 카운트만 잘 해주면 된다. 쉬운 문제.예제로 주어진 코드를 조금 수정하면 된다. *변수 설명*cnt_0 : fib(0)이 몇 번 나오는지cnt_1 : fib(1)이 몇 번 나오는지T : 테스트 케이스 N : 입력 *알고리즘 설명*재귀함수 int fib(int n) 을 이용하여 n이 1과 0일 때는 카운트 횟수를 증가시켜주고 그 외의 경우에는 fib(n-1)과 fib(n-2)를 호출해주면 된다. 그림을 그려보면 이진트리처럼 내려가게 됨. 별 다른 설명은 더 필요 없을듯하다. 123456789101112131415161718192021222324252627282930313233#incl..
※ 개인적으로 공부하면서 끄적끄적 받아적은 거라 다소 엉망일 수 있습니다. [코딩야학 2일차 필기 노트] 웹서버 설치부터 HTML 이론까지 1. 윈도우에 웹 서버 설치 https://opentutorials.org/course/1688/93372. 서버 제어 https://opentutorials.org/course/1688/94103. 프로그래밍 언어 https://opentutorials.org/course/1688/93394. HTML 이론 https://opentutorials.org/course/1688/9340 ================================================ 1. 윈도우에 웹 서버 설치 영상 순서에 따라 bitnami를 설치 localhost/index...
※ 개인적으로 공부하면서 끄적끄적 받아적는 거라 다소 엉망일 수 있습니다 [1일차 필기노트] 1. 수업 소개 https://opentutorials.org/course/1688/102452. 웹 어플리케이션을 만드는 순서 https://opentutorials.org/course/1688/93313. 구상 https://opentutorials.org/course/1688/93324. 기획 https://opentutorials.org/course/1688/93335. 인터넷과 웹의 역사 https://opentutorials.org/course/1688/93346. 서버와 클라이언트 https://opentutorials.org/course/1688/9408 ========================..
백준 2110번 문제. 공유기 설치 [Point] 파라메트릭 서치를 이용 (최적해 -> 이진탐색 + 결정) 공유기를 최대한 널찍널찍하게 설치할 수 있는 최대 거리를 찾는 문제다. 이진탐색의 응용 버전인 파라메트릭 서치를 이용하면 된다.간단한 개념은 이 게시글에 정리해두었으니 참조 알고리즘 자체는 어렵지 않다."음..좋아 너로 정했다!""문제 조건 만족!""헐..니가 만족된다구..? 좋아 일단 널 임시 정답으로 생각해둔 다음... 가라 다음 후보!""피카피카! 문제조건 만족!""헐 너도 만족되는구나! 가라 다음 후보!" 이렇게 이진탐색으로 범위를 좁혀가면서 최적해를 구하면 된다.(무슨 소리인지는 나만 이해할 수 있을 것 같다......) 기본 뼈대는 다음과 같다. 1. 필요한 값을 입력받고, 집의 위치를 ..
Parametric Search (파라메트릭 서치) [개요]이진탐색의 응용 버전.최소값이나 최대값 등의 최적해 문제를 구할 때 유용하게 쓸 수 있다.혹자는 이것을 최적화문제 = 이진탐색 + 결정문제 (Yes or No) 로 쪼개는 것이라고 표현하기도 한다. [기본 뼈대]1. 이진탐색을 이용해 임의의 값 계산(보통 mid값이다)2. 이 값은 문제의 조건을 만족합니까 안합니까? 3. 문제 조건을 만족할시 일단 저장해두고 범위를 좁혀가면서 최적화된 해에 도달 [전제 조건]이 서치를 적용하려면 해의 구간이 연속적이어야한다.만일 mid가 문제의 조건을 만족한다면, [Left,mid] 혹은 [mid,Right] 범위에 있는 해는 모두 문제의 조건을 만족할 만한 '가능성'을 가지고 있어야한다.당연한 얘기긴 한데, 5..
백준 2346번 문제. 풍선 터뜨리기 [Point] 원형으로 작동할 수 있게끔 하되, 는 것에 유의하여 "몇 걸음"을 움직였는지 카운팅해줄 것 처음에 이 문제를 보자마자 떠오른 생각은 환형 더블 링크드 리스트였다 (Circular Double Linked List) 터뜨린 풍선은 앞으론 고려 안한다는 점에서 원형 큐도 좀 생각하긴 했다..하지만 C언어에서 구현하려면 코드가 생각보다 길어질 것 같아서 어떻게 할까 고민하다가, 그냥 야매로 배열을 사용하기로 결정. 전체적인 알고리즘의 뼈대는 다음과 같다. Remain : 남아있는 풍선의 갯수 total : 전체 풍선의 갯수 (이 값은 변하지 않는다)dir : 방향move : 몇 걸음 이동해야 하는가 (속도 = 속력+방향인것처럼 arr[i]의 값을 몇걸음(mo..
백준 1005번 문제. ACM Craft [Point] DP와 DFS를 짬뽕시켜 풀어보자. 개인적으로 좀 고난에 빠졌던 문제.분명 알고리즘 분류에 "위상정렬"이라고 들어가있는데, 나는 위상정렬로 어떻게 풀어야할지 떠오르지 않아서 다이나믹 프로그래밍과 DFS를 짬뽕시켰다.찾아보니 이 분의 글이 "위상정렬" 관점에서 제일 설명이 잘 된 글 같다. (링크) 일단 목표건물 w부터 차례대로 역추적 DFS를 하려고 했다DP배열은 0으로 초기화되어있으니 visit 배열의 역할을 대체하여 사용하였다. 부분해의 후보들 중 가장 큰 값을 가진 후보가 부분해로 채택이 되고, 이런 부분해들이 모여 최종 해를 구할 수 있다 (건물을 시공하려면 선행건물이 전부 다 건설되어야하기때문에 가장 건설시간이 긴 선행건물을 생각해야한다) ..
백준 4963번 문제. 섬의 개수 [Point] DFS를 이용해 그래프의 연결요소(Connected Component)의 갯수를 찾아내라 그래프의 연결요소란 이동가능한 "뭉치"라고 생각하면 된다. 이 문제에서 요구하는 섬의 정의와 그 갯수는 그래프의 연결요소 개수와 일맥상통한다.우선 w=0,h=0이 들어오지 않는 이상 무한루프로 케이스를 입력받고 결과값을 출력하면 된다.매 과정이 반복될때마다 방문여부를 알려주는 visit[][]과 섬의 갯수를 알려주는 cnt 변수를 도로 초기화하는 것을 잊으면 안된다. 코드는 간단하다.방향배열 dx,dy를 이용해 탐색가능한 8개의 주변 정사각형을 검사한다.①이동가능하면서(map[][]=1) ②맵을 벗어나지 않는 유효한 범위(nx와 ny의 범위 체크), ③마지막으로 한번도..
- Total
- Today
- Yesterday
- 아난티앳강남
- 드럼세탁기 고장
- 스텐팬 갈변
- 자취요리
- 구글애드센스 혐오광고
- 자취 집들이
- 타르코프 스파 관광
- 사마귀광고 제거
- 스파 파트 4
- 겨울철 동파
- 스텐팬 세척
- 친구들호캉스
- 타르코프 스파 투어
- 스시이마
- 스텐팬 갈색
- 구글애드센스 광고차단
- 겨드랑이 혹
- 4E표시
- 혐오광고 제거
- 스텐팬 탄 자국
- 초간단 샤브샤브
- 물이 안나와요
- 겨드랑이 초음파
- 싱크대 단수
- 건강검진 겨드랑이
- 급수에러
- 겨드랑이 지방종
- 스파투어 파트4
- 스파관광 파트4
- 마민재쉐프
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |