본문 바로가기

알고리즘33

[백준] 1062번: 가르침 | C++ https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 틀린 이유 1. K=5 일 때, antatica 처리를 하지 않았다. 2. 연산자 우선순위를 고려하지 못했다. - 코드 주석 (1)에서 learned_bit & w 는 AND 연산한 bit를 반환한다. 그런데 if의 조건문은 0이 아닌 것은 모두 참으로 판별하므로 하나 이상 일치하는 bit가 있을 경우 모두 cnt++ 연산 되었다. 조건문을 learned_bit & w==w 라고 코드를 고.. 2022. 12. 14.
[백준] 2637번: 장난감 조립 | Python 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 틀린 이유 1. 처음엔 dp[7]로 제출했다. (멍청...) 2. N개의 노드가 주어졌을 때, 기본 부품, 중간 부품을 거쳐 완제품이 되는 노드가 N번임을 가정하고 다이내믹 프로그래밍으로 풀었다. (dp[N]=1 에서 시작) 정답 코드 각 노드 간 선후관계를 생각해야 할 땐 위상 정렬을 사용한다. 위상 정렬된 topology[N-1]가 완제품 노드임을 이용해 다시 다이내믹 프로그래밍으로 풀었다. 완제품부터 기본부품까지 탑다운(?)으로 .. 2022. 12. 10.
알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드 독서기간_2022년 11월 24일 ~ 2022년 12월 01일 저자_안티 라크소넨 확실히 프로그래밍 대회 준비용이라 고급진 알고리즘이 나온다. 코드 예제 전혀 없이 이론만 쭉쭉 나오니 코딩테스트 준비용으로 공부하실 분들에게 비추천한다. 나도 건너 뛴 후반부 부분(고급 그래프, 기하 등등)은 앞쪽 알고리즘 마스터 한 후 다시 읽어 보겠다... 코테 공부용은 밑에 도서들 추천합니다. 2022.11.24 - [독서/개발] - 코딩테스트를 위한 자료구조와 알고리즘 with c++ 2022.12.03 - [독서/개발] - 이것이 취업을 위한 코딩 테스트다 with Python 2022. 12. 8.
[백준] 1744번: 수 묶기 | C++ https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 틀린 이유 1. 음수 벡터를 내림차순으로 정리하지 않았다. 음수와 양수 벡터에서 절댓값이 큰 값 2개를 곱하는 것으로 접근하였는데, 음수 벡터도 오름차순으로 정리하여 절댓값이 작은 값부터 pop_back() 되었다. ex) [-1, -23, -6, -72] => [-72, -23, -6, -1], v.back() == -1 2. 양수 벡터와 음수 벡터에 원소가 1개씩 남았을 때, zeroCnt가.. 2022. 12. 6.
이것이 취업을 위한 코딩 테스트다 with Python 독서기간_2022년 11월 25일 ~ 2022년 12월 1일 저자_나동빈 코딩 테스트 알고리즘 입문 도서로 추천한다. 언어 선택 기준부터 시작해 기본적인 알고리즘을 코드 예제와 함께 쉽게 설명한다. 나는 백준을 어느정도 풀었었고, 이 책을 읽기 앞서 빡빡한 이론서 두 권을 읽었더니 쉽게 느껴졌다. 입문자에게도 Python의 직관성 덕분에 코드 해석하는 데 어렵지 않을 것이다. 책에서 어려운 알고리즘이라고 해봤자 위상정렬 정도이다. 백준 문제를 풀면서 Union-Find, MST, 크루스칼 이론을 따로 따로 공부했었는데, 세 가지 모두 연관되어 있다는 것을 알았다. 수준이 높아질수록 각 알고리즘의 연관 관계를 생각하며 공부하자. 아직 그리디스러운 발상이 어려운데... 많은 문제를 접하다보면 연상할 수 있을.. 2022. 12. 3.
[C++] string 문자열 split 하는 함수 stringstream 헤더파일을 사용해 직접 구현해야 한다. python은 기본 제공하는데 c++은 그저 똥... #include #include #include using namespace std; vector split(string str, char delimiter); int main(){ string test = "min sung kang"; vector result = split(test, ' '); for (int i=0;i 2022. 12. 2.
[프로그래머스] Lv4 무지의 먹방 라이브 | Python 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 먹는 시간이 적은 순으로 정렬해서 (먹는 시간 - 전 음식 먹는 시간) * (음식 개수) 로 k에 천천히 빼주는 식으로 접근했다. 그러다보니 k==0 일 때 k=tmp: k-=tmp prev=hq.heappop(heap)[0] size-=1 else: idx=k%size heap.sort(key= lambda a:a[1]) answer=heap[idx][1] break return answer 2022. 12. 1.
[정수론] 에라토스테네스의 체 (C++) 완전탐색 하지 않고 빠르고 정확하게 소수를 구하는 알고리즘 bool visit[MAX] -> 2부터 시작하여 소수를 구하고, 소수의 배수를 모두 true 처리를 한다. -> visit[i]가 0인 인덱스들이 소수이다. 4,000,000까지 수 중 소수의 개수는 대략 28만 개가 넘는다. 범위에 조심하자! void sieveOfEratosthenes(){ for(int i=2;i 2022. 11. 28.

티스토리툴바