백준 알고리즘 강의 후기(코드플러스): 기초1
알고리즘 기초 1/2
프로그래밍 언어 (C++, Java)를 할 줄 알고, 기초 알고리즘을 배우는 강의입니다.
전체 강의 구성은 https://code.plus/notice/16 를 참고해주세요.
알고리즘 기초1 강의 링크: https://code.plus/course/41
● 100 - 알고리즘 시작
먼저, 알고리즘이 무엇인지, 어떻게 공부하는 것이 좋은지 알아봅니다. 그 다음으로 알고리즘의 효율성을 측정하는 방법 중 하나인 시간 복잡도에 대해서 배워봅니다.
내용을쓰세요
이 강의('알고리즘 시작')는 정말 좋은 강의이기 때문에 꼭 들으셔야 합니다.
구) 알고리즘 기초 : 맛보기 강의 - 정리
알고리즘: 알고리즘이란 어떤 문제를 해결하기 위한 여러 동작들의 모임
알고리즘 공부에 가장 효과적인 방법 -> 문제 풀이
- 알고리즘 문제풀이 사이트 추천
- 백준온라인: https://www.acmicpc.net
- 그 외 사이트
- 알고스팟: https://algospot.com
- 코드포스: http://codeforces.com
- 탑코더: http://topcoder.com
알고리즘문제해결전략의 서문을 읽어보길 추천.
 |
|
알고리즘을 공부하는 방법
프로그래밍을 많이 하는것 보다 생각을 많이 해보는것이 더 중요하다.
시간 복잡도
n!은 순서가 중요할때, 즉, 132와 123이 다를때,
코드 작성전에 시간복잡도를 생각해보고, 이게 구현 가능할지 생각해보는것이 더 중요하다.
알고리즘 문제에서 주로 나오는 입출력 패턴
문제를 풀면서 만나는 입출력 패턴은 총 8가지 이다.
이 중에서 첫번째 입출력 패턴을 살펴보자.
- 문제: https://www.acmicpc.net/problem/1000
- 풀이코드: https://gist.github.com/Baekjoon/0c7632bd9b01909c7e6f
세번째 입출력 패턴을 살펴보자.
4번유형
테스트케이스의 갯수가 주어지지 않는다.
몸풀기용 연습문제
규칙성을 찾는 연습문제
200 - 자료구조 1
스택 (Stack)에 대해서 집중적으로 배워봅니다. 스택을 사용하는 문제를 이용해 스택의 어떤 성질을 이용해서 문제를 해결할 수 있는지 알아봅니다. 큐(Queue)와 덱(Deque)은 이 챕터에서 소개만 합니다. 두 자료구조는 그래프와 BFS 챕터에서 집중적으로 다루게 됩니다.
300 - 수학 1
문제를 푸는데 필요한 기본적인 수학 내용을 알아봅니다. 나머지 연산, 최대 공약수, 소수에 대해서 알아봅니다.
♠ 백준 알고리즘 강의 후기(코드플러스): 수학1 & 수학2
백준 알고리즘 강의 후기(코드플러스): 수학1 & 수학2
300 - 수학 1 나머지 최대공약수와 최소공배수 최소공배수 소수 찾기 소수 구하기 골드바흐의 추측 팩토리얼 팩토리얼 0의 개수 조합 0의 개수 나머지 //첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C,
inner-game.tistory.com
400 - 다이나믹 프로그래밍 1
다이나믹 프로그래밍이 무엇인지, 난이도가 가장 낮은 문제들을 이용해 다이나믹 프로그래밍을 이해해 봅니다.
♠ DP는 따로 정리.. inner-game.tistory.com/426
백준 알고리즘 강의 후기(코드플러스): 기초1 - 다이나믹 프로그래밍1 (DP1)
● 400 - 다이나믹 프로그래밍 1 다이나믹 프로그래밍이 무엇인지, 난이도가 가장 낮은 문제들을 이용해 다이나믹 프로그래밍을 이해해 봅니다. 아래의 다이나믹 프로그래밍 프로그래밍1) 맛보기
inner-game.tistory.com
추가 자료
최백준님의 알고리즘 어떻게 공부할 것인가? 강의 정리 자료. 꼭 읽어 보세요.
[백준 BOJ 코드플러스/백준 BOJ 온라인저지 사용법] - [알고리즘 공부 방법] 나는 어떻게 알고리즘 공부를 했을까? - 최백준 님
[알고리즘 공부 방법] 나는 어떻게 알고리즘 공부를 했을까? - 최백준 님
나는 어떻게 알고리즘 공부를 했을까? - 최백준 님 가끔씩 다시 봐도 참 좋은 자료라고 생각됩니다. 제가 중요하다고 생각하는 부분만 캡쳐해보았습니다. 글 하단의 링크를 클릭하면, 최백준님
inner-game.tistory.com
이미 알고리즘에 조금 익숙하시다면, 리트코드에 도전해보시는것도 강력 추천 드립니다.
[왕초보] 리트코드 시작하는 방법 (릿코드/leetcode 활용법, 공부 방법)
[왕초보] 리트코드 시작하는 방법 (릿코드/leetcode 활용법, 공부 방법)
리트코드/릿코드/leetcode를 시작하는 방법은 다음과 같습니다. 1. 회원가입 leetcode.com/ 위의 리트코드(leetcode) 사이트에서 회원가입을 합니다. 기본적으로 사이트 이용은 무료입니다. 추가적으로,
inner-game.tistory.com
여기 까지가 이 글의 마지막 입니다.
아래 접은글 삭제하면 새로 옮긴글에서 사진이 지워질까봐 접어두기만함.
아래의 다이나믹 프로그래밍 프로그래밍1) 맛보기 강의를 가져왔다.
피보나치수를 예를 들어서 설명해 준다.
메모이제이션을 설명해준다.
탑다운과 바텀업도 알려준다.
- 탑다운 -> 재귀함수
- 바텀업 -> 작은문제부터 차례대로 푼다.
- f[0] = 0;
- f[1] = 1;
- for(int i ~
- 이런 스타일
문제풀이전략
- 점화식을 만들자.
- 문제를 많이 풀면서 감을 잡는것이 중요하다.
200 - 자료구조 1
조세퍼스 문제
문제 이해: 초반 1분, 원형으로 둘러 앉아서 k만큼 건너뛰며 제거하는 형태
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
Deque<Integer> deque = new ArrayDeque<Integer>();
StringBuilder sb = new StringBuilder("<");
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
for(int i = 1;i <= n; i++) {
deque.add(i);
}
while(!deque.isEmpty()) {
for(int i = 0; i < m-1;i++) {
deque.addLast(deque.removeFirst());
}
sb.append(deque.removeFirst() + ", ");
}
System.out.println(sb.toString().substring(0, sb.length()-2) + ">");
}
}
나머지연산으로도 처리 가능
while(!list.isEmpty()) {
index += m; if (index >= list.size()) {
index %= list.size();
}
sb.append(list.remove(index) + ", ");
}
201 - 자료구조 1 (연습)
203 - 자료구조 1 (참고)
300 - 수학 1
♣ 수학1 & 수학2 정리: inner-game.tistory.com/504
백준 알고리즘 강의 후기(코드플러스): 수학1 & 수학2
300 - 수학 1 나머지 최대공약수와 최소공배수 최소공배수 소수 찾기 소수 구하기 골드바흐의 추측 팩토리얼 팩토리얼 0의 개수 조합 0의 개수 나머지 //첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C,
inner-game.tistory.com
301 - 수학 1 (연습)
303 - 수학 1 (참고)
400 - 다이나믹 프로그래밍 1
- 1로 만들기
- 2×n 타일링
- 2×n 타일링 2
- 1, 2, 3 더하기
- 카드 구매하기
- 카드 구매하기 2
- 1, 2, 3 더하기 5
- 쉬운 계단 수
- 이친수
- 가장 긴 증가하는 부분 수열
- 가장 긴 증가하는 부분 수열 4
- 연속합
- 제곱수의 합
- 합분해
♣ DP1 정리 : inner-game.tistory.com/426
백준 알고리즘 강의 후기(코드플러스): 기초1 - 다이나믹 프로그래밍1 (DP1)
● 400 - 다이나믹 프로그래밍 1 다이나믹 프로그래밍이 무엇인지, 난이도가 가장 낮은 문제들을 이용해 다이나믹 프로그래밍을 이해해 봅니다. 아래의 다이나믹 프로그래밍 프로그래밍1) 맛보기
inner-game.tistory.com
401 - 다이나믹 프로그래밍 1 (연습)
- 1, 2, 3 더하기 3
- RGB거리 구)
- 동물원 구)
- 오르막 수
- 스티커
- 포도주 시식
- 정수 삼각형구)
- 가장 큰 증가 부분 수열
- 가장 긴 감소하는 부분 수열
- 가장 긴 바이토닉 부분 수열
- 연속합 2
- 타일 채우기
♠ DP는 새로운 포스트로 옮기고 그림삭제 될까봐 그림있는 부분만 남겨둠 inner-game.tistory.com/426
백준 알고리즘 강의 후기(코드플러스): 기초1 - 다이나믹 프로그래밍1 (DP1)
● 400 - 다이나믹 프로그래밍 1 다이나믹 프로그래밍이 무엇인지, 난이도가 가장 낮은 문제들을 이용해 다이나믹 프로그래밍을 이해해 봅니다. 아래의 다이나믹 프로그래밍 프로그래밍1) 맛보기
inner-game.tistory.com
백준 1149 RGB거리 - 실버1
[][][] (R,G,B)
[][][] (minGB+R, minRB+G, minRG+B)
[][][] (minGB+R, minRB+G, minRG+B)
...
[][][]
마지막줄의 3개중 가장작은값
백준 13398 연속합 2 - 골드5
배열이 두줄 필요하다.
윗줄은 제거않는버전, max(아무것도 안더한거, 지금까지더한거)+현재값
아랫줄은 하나제거한버전, max(하나뺀거+현재값더한거, 윗줄의이전최대값(즉,현재값을제거한것))
ans = max(max(윗줄, 아랫줄), 이전답)
근데 얼핏생각하며 아랫줄버전에서 계속 하나지운거에 또지우고 또지우고 그런 dp를 할수도 있지 않을까 싶은데..
잘 생각해보면,
1, -1, -1, 2 인 경우
1라운드
윗줄에서 1
아랫줄에서 1
2라운드 1, -1
윗줄에서 0
아랫줄에서 1(-1을 제거하였음)
3라운드 1, -1, -1
윗줄에서 -1
아랫줄에서 1(이미하나제거되어있음)+-1, -1(이미하나제거되있음) 중에 두번째꺼를 선택하게 되면 두개를 제거하는건데 동시에 맨처음꺼만 선택한 수열이됨
ans 는 현재 1
4라운드 1, -1, -1, 2
윗줄에서 2(현재값)
아랫줄에서 0+2, -1
ans는 2가됨
이런식으로 초기화 되므로, 연속해서 숫자를 빼줄 가능성은 없어짐
