본문 바로가기

알고리즘

백준 1920풀이 - cin / cout 으로는 안 풀려 오늘은 풀이한 문제 중 백준 1920문제를 들고 나왔습니다. 의외성이 있어 공유합니다 :) https://www.acmicpc.net/problem/1920 단순한 이진 탐색 문제인데요. 1) 최대 10만개의 숫자를 입력, 2) 다시 최대 10만개의 숫자를 입력받고 3) 각 숫자가 1)번의 10만개에 들어있는지 검색하는 문제입니다. 그냥 입력받은 수를 숫자 오름차순 정렬해서, 2진 탐색, 존재여부만 판단하는 되는 문제이나, 비교적 쉬움애도 불구하고 풀기 어려워 7번만에 제출, 통과했는데요. 바로 "시간초과"가 그 주범입니다. 이진 탐색 풀이의 원리 이진 탐색은 아래와 같습니다. 예를 들어 7개의 수가 있다고 할 때, 34 121 56 777 1024 10 142 이 숫자를 모두 작은 숫자에서 큰 숫자로 .. 더보기
백준 문제풀이 - 큰 수 A+B 오랜만에 백준 코딩 문제 풀이를 해보았습니다. 백준 문제 풀이는 코딩 실력을 테스트하는 일종의 연습용 사이트인데요. 참여자도 많고 문제도 어마어마하게 많습니다. 국내 '천하 제일 코딩대회'라고 해도 과언이 아닐텐데요. 개발자들끼리 서로 코딩 문제를 풀어 랭킹을 뽐내기 때문입니다. 다만 전혀 코드 분석 없어 대충 복붙해 넣기만 하는게 가능한 단점도 있는데요. 다른 분의 코드를 참조는 하되 풀이방법만 익히고 스스로 풀어보는게 중요합니다. 그렇지 않으면 실력이 늘지 않지요. 그나저나 오랜만에 로그인해보니 헉! 순위권이 10.000위권 밖으로 밀려나 있는게 아니지 않습니까? 두둥!! 개발자 블로거의 자존심(?)이 걸린 문제라 가만 있을수 없어 부랴부랴 문제를 풀어 10.000위권 안으로 진입시켜 놓았습니다. 다.. 더보기
구름LEVEL 어느개발자 이야기 스토리가 있는 알고리즘 문제입니다.데이터베이스 관리자였던 개발자가 해고를 당해, 회사 DB를 망가뜨려놓았다는 이야기인데요. 얼마나 억울하게 느꼈다면 그랬나 싶기도 하지만, 도의상 그러면 안되겠지요 :)level.goorm.io/exam/43171/%EC%96%B4%EB%8A%90-%EA%B0%9C%EB%B0%9C%EC%9E%90-%EC%9D%B4%EC%95%BC%EA%B8%B0/quiz/1구름LEVEL코딩테스트에서 가장 높은 비중을 차지하는 알고리즘 문제를 제작하고 풀이할 수 있는 온라인 저지 서비스입니다. 기업에서 선호하는 C, C++, 파이썬(Python), 자바(Java), 자바스크립트(Javascript) 이level.goorm.io자, 결국 망가뜨린 자료를 복구하는 것인데요. 문제를 보고 처음엔.. 더보기
구름LEVEL 소수판별 코딩알고리즘 문제풀이 전에 접했던 구름 LEVEL 알고리즘 문제를 한번 풀어봤습니다. 원본 문제 URL은 아래와 같은데요. 쉬운 문제로 가벼운 준비운동인 셈입니다. 소수판별하는 문제 풀이이고 시간복잡도가 나오긴 하나 필수 통과요소로는 판단하지는 않는 듯 합니다. level.goorm.io/exam/43238/%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84/quiz/1 구름LEVEL 코딩테스트에서 가장 높은 비중을 차지하는 알고리즘 문제를 제작하고 풀이할 수 있는 온라인 저지 서비스입니다. 기업에서 선호하는 C, C++, 파이썬(Python), 자바(Java), 자바스크립트(Javascript) 이 level.goorm.io 소수란 1과 자기 자신 외에는 약수가 없는 수인데요. 특정한 수 n이 소수인지 아닌.. 더보기
백준 1712 손익분기점 풀이 백준문제 1712번 손익분기점 문제 풀이입니다 https://www.acmicpc.net/problem/1712 1712번: 손익분기점 월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다. 예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다. 노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 www.acmicpc.net 손익분기점이란 제품제작에 필요한 비용중 1회성으로 지출이 끝나는 "고정비용"과 각 제품마다.. 더보기
백준 3052. 나머지 문제 풀이 오랜만에 백준 문제를 풀어봅니다 :) 그냥 10분안에 간단히 풀 수 있는 문제 하나 골라봤는데요. https://www.acmicpc.net/problem/3052 3052번: 나머지 문제 두 자연수 A와 B가 있을 때, A%B는 A를 B로 나눈 나머지 이다. 예를 들어, 7, 14, 27, 38을 3으로 나눈 나머지는 1, 2, 0, 2이다. 수 10개를 입력받은 뒤, 이를 42로 나눈 나머지를 구한다. 그 다음 서로 다른 값이 몇 개 있는지 출력하는 프로그램을 작성하시오. 입력 첫째 줄부터 열번째 줄 까지 숫자가 한 줄에 하나씩 주어진다. 이 숫자는 1,000보다 작거나 같고, 음이 아닌 정수이다. 출력 첫째 줄에, 42로 나누었 www.acmicpc.net 요약하면, 10개의 주어지는 숫자들을 42.. 더보기
백준 알고리즘 7576 토마토 문제풀이 해설과 소스 토마토를 영국에서는 "신이 주신 열매"라고 부릅니다. 그만큼 피로회복에도 좋고, 특히 토마토의 라이코펜 성분이 알코올 분해시 생성하는 독성물질을 배출한다고 하네요. 영국에서는 해장으로도 토마토를 섭취한다고하니, 가볍게 보였던 토마토가 웬지 오늘 따라 달라보이는군요. 크레이는 술을 먹지 않지만, 술 드시는 분은 다음날 해장국 대신 해장토마토를 권해드리는 바입니다. 그렇다고 술을 과음하시라는 이야기는 절대 아닙니다 :) ​ 오늘 도전해본 백준 알고리즘 문제는 "토마토 익는 날짜" 계산하기 문제입니다. ​ https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 .. 더보기
백준알고리즘 2037 문자 메시지 해설 및 소스 이번엔 좀 재미난 문제입니다 :) 영어로 된 문자자판에서 문자 메시지를 보내는 데 걸리는 시간을 측정하는 소스를 짜는 것인데요. https://www.acmicpc.net/problem/2037 2037번: 문자메시지 문제 오른쪽 그림과 같은 핸드폰 자판이 있다. 이 자판을 이용하여 어떤 영어 메시지를 치려고 할 때, 걸리는 최소 시간을 구하는 프로그램을 작성하시오. 단, 1번은 누를 경우에는 공백이 찍힌다고 하자. 그리고 만약에 AC라는 문자를 치려 한다면 A를 치고 난 후 일정 시간을 기다린 후 C를 치면 된다. 하나의 문자를 입력하려면, 버튼을 눌러야 한다. 버튼을 누르면 버튼에 쓰여 있는 문자가 입력되며, 버튼을 누를 때 마다 다음 문자로 바뀌게 된다. 예를 들 www.acmicpc.net 문제 .. 더보기