https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수를 구하는 알고리즘은 '에라토스테네스의 체'라는 이름으로 널리 알려져 있다. 밑의 코드에서도 구현하겠지만, 간단한 원리는 소개하는 게 좋을 것 같다. 1. 소수면 True, 아니면 False로 구성된 리스트를 만든다. 2. n ** 0.5 까지 반복문을 돌면서 소수면 그 배수들을 전부 False로 바꾼다. 3. 리스트에서 n까지 반복하며 값이 True인 인덱스를 구한다. 복잡한 듯 싶지만 꽤 간단하며 원리도 직관적이다. 이 문항은 에라토스테네스의 체와 두 포인터가 합쳐진 문젠데, 각각의 개념 자체는 어렵지 않지만..
0. 일주일 동안 블로그를 신경 쓰지 못했다. 핑계 아닌 핑계를 대자면, 내가 작성한 코드를 ColorScript를 통해서 업로드 중이었는데, 깨짐 현상과 줄 간격이 라인 넘버와 맞지 않는 현상이 너무 많이 발생해서 다른 해결책을 강구해야 했다. 그러던 중 티스토리에서 제공하는 코드 블럭을 알게 되었는데, 라인 넘버, 하이라이트, 폰트 등 html/css를 이용해 수정해주면 깔끔하고 더 효율적인 코드 작성이 가능하더라. 문제는 각종 블로그에서 지시하는 대로 따라갔는데도 원하는 스타일이 안 나와서 한참을 헤매다가 오늘에서야 그럴듯한 모양새가 잡혔다. 지난주는 주간 주라 바쁘기도 했고, 코드 첨부 문제도 있었고... 여러모로 험난했다. 그래도 문제는 꾸준히 풀었기 때문에 오늘 그동안 푼 문제들 정리도 할 겸..
https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net output이해를 잘못해서 조금 돌아갔지만, 결과값 s가 아닌 새로이 벼열한 리스트를 return하는 방식의 문제 또한 충분히 좋았을 것 같다. color scripter를 이용해서 코드를 업로드하고 있었는데, 불규칙적으로 사이즈가 커지거나, 정렬 오류가 발생하는 경우가 종종 생겨서 다른 방식의 필요성을 느꼈다. html을 미약하게 공부한 상태라 자신감이 붙어서, 구글링으로 검색한 블로그들..
https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이는 역시나 단순하다. 백준 저지에서 solved.ac 설정을 수정하면 문제별로 난이도가 표시되는데, 실버 수준의 문제들은 사실 그렇게 어렵게 느껴지지는 않는 것 같다. 문제는 시간 복잡도다. 문제에서 제한한 조건에 따라서 어떻게 풀지를 설계해야 하는데, 그 해석이 잘 안돼서 구현은 가능하지만 이 풀이가 문제가 요구하는 바에 부합하는지 판단을 내리는 게 조금 까다롭다. 해야지, 해야지 생각은 하는데 ..
https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 정렬 알고리즘이긴 하지만, sort 함수의 쓰임새에 조금 더 치중된 문항이다. 이 문제를 푸는데 필요한 역량은, 1) sort함수의 문자열 정렬 기능을 알고 있는가 2) sort함수의 key기능을 알고 있는가 3) sort함수를 여러 번 사용한 경험이 있는가 정도가 될 수 있을 것 같다. 1, 2는 파이썬 기초 문법을 공부할 때 접한 기억이 있어서 자세히는 아니어도 무의식 속에 알고 있..
https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번에 사용한 정렬 알고리즘은 퀵정렬이다. 사실 어떤 정렬 알고리즘의 효율이 더 좋은지는 아직 시간 복잡도에 대한 이해가 부족하여 잘 모르겠지만, 우선은 다양한 알고리즘들을 실제로 사용해보는 것도 좋지 않을까라는 것에 의의를 두기로 한다. 보통의 정렬 알고리즘과 달리 이 문제는 내림차순을 요구하기 때문에 일반적인 풀이와는 미묘하게 다르다. 어느 부분을 수정해야하는지 사고하는 것도 의외로 단순하지만 재밌는 경험이었다. # PYTHON CODE 1 2 3 4 5 6 7 8 9 10 11 ..
https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 버블, 단순 선택, 단순 삽입, 셸, 퀵, 병합, 힙 중에 병합 정렬이나 힙 정렬로만 풀리는 시간 복잡도를 갖는 문제다. 퀵 정렬의 경우 꽤 빠른 정렬이기는 하지만, 배열의 종류에 따라서 그 기능이 천차만별이기 때문에 사용에 주의를 해야 한다고 한다. 병합 정렬은 재귀적인 부분에서 이해가 잘 가지 않아서 잠깐 막혔지만, 몇 가지 케이스를 따라가다 보면 이해가 될 수밖에 없는 재귀 알고리..
https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 재귀 알고리즘은 내가 배운 알고리즘들 중에서 가장 추상적인 알고리즘이다. 틀이 명확한 다른 알고리즘에 비해서 재귀는 깊이 들어갈수록 늪에 빠지는 느낌이 강하게 든다. 일일이 케이스를 분류하고 100프로 이해하려는 것보다 어느 정도 선에서 특수한 규칙까지만 확인하고 느낌대로 수정해나가는 게 더 효율적인 접근방식인 듯하다. 프로그래머스의 기초 강의와 알고리즘 도서로 간단히 복습은 했는데,..
