2019 winter PS Basic.ver

백준 10799 -- "첫째 주 배울 내용은 기본 자료구조로 배열, 연결리스트, 스택, 큐, 덱, 문자열(기본)과 정렬입니다. STL들도 이번주와 다음주에 공부하는게 좋겠습니다." -방장님 말씀... 메모... 문제 : (https://www.acmicpc.net/problem/10799) >문제는 파이프를 절단했을 때 몇 조각들이 나오는 가의 문제 ...

백준 1406 -- 문제: https://www.acmicpc.net/problem/1406 에디터 문제. 해당 키 입력에 따라서 커서를 이동시키고 문자를 삭제 및 삽입하는 기능 구현하기. 스택/ 리스트/ 벡터 를 사용하여 풀어봄. 시간제한 때문에 벡터는 안풀림 ㅎㄷ 1) 스택 l , r 이라는 스택을 두고 각각 커서의 왼쪽, 오른쪽을 나타내는 스...

백준 1158: 조세퍼스 문제 / 10820: 문자열 분석 -- 1) 조세퍼스 문제. 큐 활용해서 문제 풀기. (https://www.acmicpc.net/problem/1158) 첨에 링크드리스트 만들면서 개고생했는데 큐쓰면 됨.....ㅠㅠ 앞에꺼를 팝해서 뒤에다가 붙이면 사이클 완성. 암튼 그리고 주의할 점이 "\b" backspace 개행문자를 사용...

백준 11655 -- 1) 백준 11655(ROT 13) : https://www.acmicpc.net/problem/1165 암호화 하는 문제. 알파벳은 26개라 13개 더하고 다시 13개 더하면 제자리로 돌아오도록. 숫자는 해당 안되니 알파벳만 더하기. 아스키 코드상에서 'a' : 97, 'z' : 122 'A' : 65, 'Z' : 90 이다. ...

백준 11656 -- 1) 백준 11656 (접미사 배열) : https://www.acmicpc.net/problem/11656 stl공부를 해야하는 이유인가 싶다. string에서 사용할 수 있는 함수들로 substr() 이라는 좋은 친구를 발견했더니 아주 편하게 풀렸다. string으로 입력값을 받아들이고, substr(a, b) 를 이용해 벡터...

백준 10989, 11651 -- 1) 백준 10989 : 수 정렬하기 (https://www.acmicpc.net/problem/10989) 메모리초과... printf가 cout보다 빠른가...? 들어갈 수 있는 수의 제한이 1~10000 인 것을 활용 (1000만에 비해 훨씬 작다) 하기전에 memset해서 배열 초기화 꼭해주기. https://g...

백준 11652 -- 1) 백준 11652 : 카드 (https://www.acmicpc.net/problem/11652) 좀 황당했다. long long사이즈에다가 100만개까지 받아들일 수 있는 array를 만들 수 있을지 몰랐다. 메모리 문제인지 뭔진 몰라도 일단 내 컴퓨터에서는 100만개까지 배열이 안만들어진다. 그래서 당연히 아니라고 생각하고 있...

백준 1717 -- 1) 백준 1717 : 집합의 표현 (https://www.acmicpc.net/problem/1717) Union Find. 1 0 1 3 index = 0 1 2 3 4 5 6 7 8 9 arr[] = 0 3 2 3 4 5 6

백준 1764 -- 1) 백준 1764 : 듣보잡 (https://www.acmicpc.net/problem/1764) 미래의 나야... 잘 보렴;;; STL을 잘 공부했니? 난 이거 봤을 때 좀 충격이었어. binary_search(begin, end, str) 하니까 서치가 되. 대박이야;;; vector를 사이즈 알고있으면 resize해서 처음부...

백준 15552 -- 1) 백준 15552 : 빠른 A+B (https://www.acmicpc.net/problem/15552) 뭐지 뭐지 하다가 엄청 고민하다가 일단 한번 내봤는데 통과... 고민하지 말고 더해서 출력하자.. https://github.com/JangJuMan/2019-winter-PS/blob/master/10_15552.cpp ...

백준 2606, 7785 -- 1) 백준 2606 : 바이러스 (https://www.acmicpc.net/problem/2606) 전형적인 DFS문제 (BFS가 더 빠르다고는 하던거 같은데 아무튼 이게 손에 익어서) 1과 연결된 노드가 몇개인지 거르면 끗. https://github.com/JangJuMan/2019-winter-PS/11_2606.c...

백준 2252 -- 1) 백준 2252 : 줄 세우기 (https://www.acmicpc.net/problem/2252) 우선 열심히 그래프 그려가면 topological sort 생각하며 DFS와 함께 풀었고, 결론적으로 틀렸다. 왜 틀린지는 어떤 케이스에서 틀렸는지 찾다가 포기했다. 아까우니까 아래쪽에 기록은 하겠다. 맞는 방법은 큐와 BFS를 활용...

백준 10815 -- 1) 백준 10815 : 숫자카드 (https://www.acmicpc.net/problem/10815) 처음에는 상근이의 카드를 a 입려값을 b로 한 후 두 어레이를 모두 sort하고 curser를 두개 둬서 점점 이동시키는 방법을 생각했었는데 입력 순서에 따라 답을 줘야 해서 이 방법은 채택하지 않았다. 나머지 할 수 있는 것은...

백준 11286 -- 1) 백준 11286 : 절대값 힙(https://www.acmicpc.net/problem/11286) c++ 공부합시다. priority q도 쓸줄 모르는 빵떠꾸... stl에 편히 쓸 수 있게 되어있는 칭구 하나랑... 힙을 구현을 못해서 아주... 열심히 공부해야지.. https://github.com/JangJuMan/2...

백준 4849 -- 1) 백준 4849 : 베르트랑 공준 (https://www.acmicpc.net/problem/4948) n과 2n 사이의 소수 몇개인지 구하는 문제. 소수 구하는 거야 뭐 2에서 sqrt(n)까지 구하는 방법을 사용했고, 필요없는 계산의 반복을 막기위해 DP로 접근. 해당 수가 소수인지 아닌지를 알려주는 어레이 isPrime을 만...

백준 9020 -- 1) 백준 9020 : 골드바흐의 추측 (https://www.acmicpc.net/problem/9020) 4부터 10000까지의 수는 2가지 소수의 덧셈으로 표현할 수 있다(골드바흐의 추측) 무조건 2개의 덧셈으로 정리되고, 소수 사이의 차이가 적은 것을 우선적으로 출력하는 문제. n이 들어오면 반절 잘라서 n/2 (혹은 n/2 +...

백준 11653, 2312 -- 1) 백준 11653 : 소인수분해 (https://www.acmicpc.net/problem/11653) 소수이면서 n을 나눌 수 있는 수를 찾고 있었는데 시간초과가 나왔다. 생각해보면 소수 체크를 할 필요가 없다. 왜냐하면 2부터 시작해서 나눠지지 않을 때까지 반복할 것이기 때문. 따라서 2에서 넘어가면 자연스럽게 4도...

백준 11005 -- 1) 백준 11005 : 진법 변환 2 (https://www.acmicpc.net/problem/11005) modulo 활용해서, 우리가 숫자 2진법으로 만드는 것처럼 벡터에 쌓아놓고 거꾸로 출력. https://github.com/JangJuMan/2019-winter-PS/18_11005.cpp 끗

백준 1676 -- 1) 백준 1676 : 펙토리얼 0의 개수 (https://www.acmicpc.net/problem/1676) 맨 뒤에 0이 나오려면 2x5가 있어야 한다. 2는 5에 비해 많이 나오므로 5가 몇번 곱해지는지만 알면 된다. 1~4! : 0번 5~9! : 1번 10~14! : 2번 15~19! : 3번 20~24! : 4번 25! : ...

백준 2485 -- 1) 백준 2485 : 가로수 (https://www.acmicpc.net/problem/2485) 보아하니 sort되서 위치값이 가로수의 위치로 들어온다. 각 가로수 사이의 거리를 구하고 저장한다. 이들의 최대공약수를 구한다.(가로수 사이의 거리들) 거리의 최솟값에서 1까지 가면서 해당 수를 공약수로 갖는지 확인하고, 공약수면 bre...

백준 2004 -- 1) 백준 2004 : 조합 0의 개수 combination을 했을 때 마지막에 오늘 0의 개수가 어떻게 되는가 알아보기. nCr = n! / (r! * (n-r)!) 이다. 0은 10의 곱으로 만들어지기 때문에 이것에 집중한다. 25나 125처럼 5의 곱이 더 더해지는 경우도 생각한다. 25 > 5 > 1 > 0 이므로 25!은 ...

백준 1167 -- 1) 백준 1167 : 트리의 지름 (https://www.acmicpc.net/problem/1167) 후;;; 컴과사 시간때 풀었었는데... dfs를 모든 leaf노드에서 돌리려고 했다가 TL.. dfs를 아무 leaf에서 돌리고 또 2번 돌리면 그 길이가 최대가 된다는 것을 배웠거늘.. dfs를 처음 돌렸을 때 최대거리가 되는...

백준 1761 -- fail... LCA... pii : pair https://www.acmicpc.net/problem/1761 https://github.com/JangJuMan/2019-winter-PS/23_1761.cpp ㅠ

백준 1991 -- 1) 백준 1991 : 트리순회 아직 안품.

백준 3176 -- 1) 백준 3176 : 도로 네트워크 아직 안품

백준 11437 -- 1) 백준 11437 : LCA 아직 안품.