분류 전체보기

[백준 2602] 돌다리 건너기 C++

2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 돌대가리 건너기 다이나믹 프로그래밍 처음에 너무 어렵게 생각했다.. dp배열을 2차원으로 두고 별의별 조건들을 걸면서 했더니 머리만 아프고 문제는 예제입력조차 풀리지 않았다.. 결국 어쩔 수 없이 구글을 참고했는데.. 단순히 3차원 dp배열을 설정해주면 아주 쉽게 풀리는 문제였다 dp[현재 돌다리 상의 위치][다리 종류(천사or악마)][지금까지 밟은 문자열 개수] 처음 dp배열을 -1로 초기화 시켜주고 현재 dp값은 현재 돌다리 상의 위치로 부터 갈 수 있는 모든 돌다리의..

[백준 9466] 텀프로젝트 C++

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS 를 이용해서 사이클을 이루는지 확인하는 문제 사이클을 찾는 문제다 보니 처음에 union-find를 사용해서 풀었다.. 결과는 시간초과! 틀린 코드 더보기 #include using namespace std; int student[100001]; bool visited[100001]; int makeUnion(int st, int p){ if(student[p] == st) return student[p] = 0; return student[p] = makeU..

[백준 1937] 욕심쟁이 판다 C++

1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net DFS + DP dp[r][c]값 : 판다가 r, c에서 출발했을 때 최대로 살 수 있는 날을 저장 상하좌우로 움직이며 얻는 dp값들 중 최댓값을 현재 dp값으로 갱신한다 방문여부, 좌표별 최대 생존일의 메모이제이션을 통해 문제를 해결 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 32 33 34 35 36 37 38 39 40 41 42 43 44 ..

SystemSoftware - Machine data(Assembly) #2

구조체가 메모리에 기록되는 방식을 알아보고 어셈블리어가 어떻게 작동하는지 알아보자 struct rec{ int a[4]; size_t i; struct rec *next; }; Linked List의 메모리 구성과 어셈블리 struct rec{ int a[4]; int i; struct rec *next; }; void set_val(struct rec *r, int val){ while(r){ int i = r->i; r->a[i] = val; r = r->next; } } set_val 함수의 while문에 대한 어셈블리어를 알아보자 // %rdi = r // %rsi = val .L11: moveslq 16(%rdi), %rax// %rax에 i값(시작주소 r에서 16만큼 떨어진) 을 넣어준다 mo..

[백준 17136] 색종이 붙이기 C++

17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 백트래킹 연습하기 #3 삼성 A형 기출 문제 백트래킹을 효과적으로 적용하기 위해서 가장 큰 색종이 먼저 덮어줘야하는 그리디 기법이 사용되었다 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 ..

[백준 2661] 좋은 수열 C++

2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 백트래킹 연습하기 #2 res : 지금까지 만들어진 수열 is_bad() 함수의 나쁜 수열 찾는 방법 ex1) res = 32121 start lo hi 0 32 121 1 21 21 -> start=1 일 때 lo == hi 이므로 나쁜 수열이 되어 return false ex2) res = 3212323 start lo hi 0 321 2323 1 212 323 2 12 323 3 23 23 -> start=3 일 때 lo==hi 이므로 나쁜 수열이 되어 return f..

백트래킹 너무 어려워

아 백트래킹 너무 어렵다... 실버 1문젠데 1시간 반이나 고민하고 진짜 절망스럽다 백트래킹 왜이렇게 어렵냐 나만그래? 전에 조고리즘 Music도 백트래킹에서 막혀서 80점으로 그냥 던져놨는데 요즘따라 백트래킹 알고리즘때문에 신경쓰여서 다른거 할 때도 자꾸 생각나서 집중이 안된다 그만큼 열심히 해야지... baaaarkingdog 님 유튜브에도 보니까 백트래킹은 구현력이 매우 많이 필요한 파트이고, 재귀를 기본적으로 사용하기 때문에 문제를 많이 풀고 익숙해지는게 진짜 중요하다고 한다... 쉬운 알고리즘이 아니란거에 그나마 위안을 좀 얻어야 겠다ㅠ 그런데 백준 티어는 플레티넘을 바라보고 있는데 실버 1 백트래킹 문제에 쩔쩔매면 진짜 티어가 무슨 의미인가 싶다 아직 기초공사가 많이 부족한 상태임을 다시한번 ..

SystemSoftware - Machine data(Assembly) #1

C언어에서 다루었던 포인터연산을 통한 변수 값 참조와 다차원 배열의 특정 위치의 값을 참조하는 방식을 어셈블리어를 통해 깊게 알아보자 int val[5]; 라는 정수형 배열이 있다고 생각해보자 주소값 x x + 4 x + 8 x + 12 x + 16 값 1 5 2 1 3 배열의 메모리 값까지 생각 한다면 위와 같이 구성 되어있을 것이다 x = 배열의 시작주소 예제 1) Reference Type Value val[4] int 3 val int * x val + 1 int * x + 4 &val[2] int* x + 8 val[5] int - *(val+1) int 5 C to Assembly 1. int pnu[5] = {1, 5, 2, 1, 3}; int get_digit(int z[], int id)..

[Django project #2] conda + Django + mysql 개발 환경 구축하기 (2) for Mac

[Django project #1] conda + Django + mysql 개발 환경 구축하기 (1) for Mac 1. Mac 에서 conda 가상환경 설치하기 1) conda 설치하기 Anaconda | Individual Edition Anaconda's open-source Individual Edition is the easiest way to perform Python/R data science and machine learning.. hyeo-noo.tistory.com MySQL세팅을 완료 했으니 Django에 MySQL 데이터베이스를 적용해보자! 사실 데이터 베이스 적용은 개발이 완료되고, 배포 전에 데이터의 사이즈를 고려해서 정한다고 하는데.. 어차피 나중에 할 거 지금 미리 연습해 ..

[백준 1759] 암호만들기 C++

1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹 연습하기 #1 Stack Permutation C++ 순열을 구하기위해 dfs를 사용했는데 visit 배열 대신 stack을 사용해서 구현해보았음 n이 8이 넘어가면 하루종일 걸려요.. 모든 경우의 수를 출력해주기 때문에 어쩔 수 없다 if(node == N) 부분의 for hyeo-noo.tistory.com 이전에 스택을 이용해 permutation을 구현한 코드처럼 C개의 문자중에서 L개를 뽑는 경우를 모두 출력하는 문제이다 추가된 조건들 암호를 이루는..