분류 전체보기
-
[BOJ] 1202 :: 보석 도둑알고리즘/BOJ(C++) 2018. 7. 24. 12:09
https://www.acmicpc.net/problem/1202 으엉 ㅠㅠ어려웠고 엄청 많이 틀렸던 문제라서 문제풀면서 느낀거 정리하려고 씀 1. 그리디한 문제. 가장 큰 가격 부터 가방에 담으려고 시도 -> 가방에 담을 때 자신보다 크거나 같은 가방 중 가장 작은 가방을 찾아야함2. 정말 naive하게 풀면 nk가 나오는데 물론! 시간초과3. 지금 담으려는 무게보다 크거나 같은 것 중 가장 작은 가방을 찾는 과정에서 시간을 줄이기 위해 lower_bound를 생각함(logN)4. lower_bound로 담을 수 있는 가방을 찾고 그 가방을 사용했다는 표시?를 하기위해 erase연산을 사용헀으나, vector에서 erase연산은 n의 시간복잡도를 가지므로 약 n^2logn이 나와 시간초과5. 우선, p..
-
18.07.18일상/일기 2018. 7. 18. 16:35
방학 진짜 바쁘다 ㅂ방학맞음?ㅌㅋㅋㅋㅋㅋㅋ하 일단 약간 느슨해지고있던 알고리즘 공부를 스터디 덕분에 다시 의지생겨서 빡빡 하고있당 프로젝트가 엎어질 위기에 놓였다..ㅠㅠ 프로젝트 시작보다 끝내는게 더 어렵다는 말은 팩트여따 어카냐 우리플젝 흑흑 ㅠ 네이버 데이터사이언스 컴페티션때매 딥러닝 공부중인데 이것도 어렵다 왜 안어려운건없지..?ㅋㅋㅋㅋㅋ 안ㅇ어려운거 롤? (본인 현재 브3...) 뭐암튼 포스팅하고싶은ㄱ거 1.파라매트릭서치 ->공부한김에 안까먹게 개념정리랑 문제푸는 스킬 조심할꺼?정리해놓기 2. 홍콩 마카오 여행 포스트.. ㅇ으어
-
[BOJ] 14226 :: 이모티콘알고리즘/BOJ(C++) 2018. 7. 3. 15:22
https://www.acmicpc.net/problem/14226 pair를 한 정접으로 하는 그래프를 생각하고, bfs탐색을 진행합니다. pair의 first원소는 현재 화면에 있는 이모티콘의 개수이고 second원소는 클립보드에 있는 이모티콘의 개수입니다. index관련 예외처리만 잘해주면 됩니다! 요즘 런탐에러 너무많이나네요ㅠ 실수안해야지.. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include using namespace std; int s; bool check[1003][2003];int dist[1003][2003]; int main(){ cin..
-
[BOJ] 9019 :: DSLR알고리즘/BOJ(C++) 2018. 7. 2. 22:58
https://www.acmicpc.net/problem/9019 얘도 BFS문제입니다! 앞으로 한동안은 미뤄놨던? 어려운 BFS문제들을 다 풀어서 끝내려고합니당... 이번주 scpc 2차라서 좀 다양한 못접해본 문제들 풀어야 하긴 하는데 ㅠ 몬가 이제와서 새로운 개념 공부해서 풀기 좀 늦은것 같기도하고... 암튼 잡소리 치우고 이문제도 너무 전형적인 bfs문제인데 여기서는 이제 다른 bfs문제랑 다른게 현재 탐색중인 지점이 어디서왔는지를 나타내는것(from배열 이용) 뿐만 아니라 그 지점으로 올때 사용된 방법(how)도 기록을 해주어야 한다는 점 입니다! L과 R구하는데 실수만 안하면 하핳...금방 풀수있는 문제입니다123456789101112131415161718192021222324252627282..
-
18.07.01 방학계획 및 요즘 생활..?일상/일기 2018. 7. 1. 17:44
드디어!종강하고 좀 방학다운 방학보내구 있다아 좀 늦게자고 늦게 일어나기도하고 하루는 날잡고 롤도 원없이 하구 ㅎㅎ 그래도 여전히 맘이 바쁜건 벌려놓은일이 너무 많아서? 일단 다음주 scpc 2차 준비 하느라 좀 맘이급하구...8월말까지 진행중인 프로젝트 완성시켜야하구 7월동안 네이버 데이터 사이언스 강의도 들어야하구 다할수있을거라 믿고 열심히해보쟈!!! 그래도 원없이 하고싶은 코딩 하니까 행볻하긴 하다 헤헤 학기중엔 지겨운 이론공부하느라 진이ㅣㄴ짜 노잼이였는데 ㅠ 방학 목표 1. 백준 500문제 찍기(영양가있는걸로 풀자...) 2. 진핸중인 교내대회 프로젝트 잘 마무리하기 3. 네이버 데이터 사이언스 컴페티션 상받기! 딥러닝 빡공부 들어간다.
-
[BOJ] 1377 :: 버블 소트알고리즘/BOJ(C++) 2018. 7. 1. 15:49
https://www.acmicpc.net/problem/1377 백준 풀고 점점 풀이올리기가 귀찮아지는데...풀이올리면 나도 한번 다시 푸는 방법 복습하는 거니까 다시 열심히 올리려고한다! 우선 이 문제는 우리가 아는 평번한? 버블 소트 문제인데, 전체 크기인 N의 크기가 너무 커서 실제 버블 소트를 돌리면 TL이 뜬다. 그래서! 우리는 처음 들어왔을 때 수의 위치와 정렬 후 수의 위치를 비교해 가장 앞으로 많이 옮겨간 수가 몇칸 옮겨갔는지를 찾아주면 되는 문제이다!이때 정렬할때 algorith 헤더파일에 들어있는 sort함수를 쓰면 nlogn에 정렬이 가능하다. vector pair로 입력을 받아 first에는 수의 값 second에는 위치를 입력받으면 된다.후에 first를 기준으로 sort하고 s..
-
18.06.24 2018 SCPC(삼성프로그래밍대회) 1차 에선 후기일상/일기 2018. 6. 24. 14:29
정신차리고 이제야 쓴다아... 어제 아침 9시부터 오후 9시까지 1차 예선이 진행되었는데 나 자신이 24시간 코딩을 할것이라는것은 역시 큰 착각이였다 ...ㅎ.ㅎㅎㅎㅎㅎ 결과부터 말하자면 1 2 3번 세개 풀었고 4번 5번은 부분점수도 못받았다 ㅠ 시도 횟수가 진짜 처참... 문제풀면서 느낀점 및 앞으로 공부할 방향 정리하면 우선 시도횟수 관련해서는 좀 더 신중하게 제출을 해야겠다. 워낙 백준에서 문제풀때 생각없이 제출 제출 제출 이러던 습관이 대회에서까지....그냥 안풀린다고 화난다고 한번 더 넣어보고 ㅋㅋㅋㅋㅋ endl을 '\n'으로 바꿔서 넣어보고...뻘짓이란 뻘짓은 다했다. 그리고 시간복잡도 생각하는 습관을 조금 더 들여야겠다. 시간리밋이 나서 코드를 고쳤을 때 고친 코드가 전의 코드에비해 시간복..
-
[BOJ] 4963 :: 섬의 개수알고리즘/BOJ(C++) 2018. 6. 20. 12:26
https://www.acmicpc.net/problem/4963 0은 바다 1은 섬일때 총 섬의 개수를 구하는 문제입니다. 1로 연결된 모든 지점을 구해 그것을 한개의 섬으로 간주하고 총 섬의 개수를 구하면 됩니다. 대각선도 연결된 것으로 간주합니다. 즉 한 지점에 대해 자기자신을 주위로 8개 모두 탐색을 해야하는 것 입니다. 1인 지점이 존재하면 그 지점부터 탐색을 시작하고, 섬의 개수를 증가시켜줍니다.자신 주위의 8개를 모두 탐색하며 1이 있다면 연결된 섬이라는 의미 이므로 0으로 변경시켜주고, 그와 연결된 섬도 탐색하기 위해 queue에 넣어 그 지점도 후에 다시 탐색될 수 있도록 합니다. bfs방식을 이용해서 풀이 했습니다.#include #include using namespace std;in..