로직과의 사투/Algorithm
코딜리티 Lesson 1, Binary Gap - Java
코딜리티 테스트를 볼 일이 생겨 Java로 첫 문제 연습을 해보았다. Binary Gap은 코딜리티의 Lesson 1번의 문제이다. 문제의 요는 10진수를 2진수로 변경해 가장 큰 1과 1사이의 갭을 구하는 문제이다. Java Integer 클래스 안에 toBinaryString 메소드를 이용해 한 번의 순회로 해결할 수 있게 코드를 짜보았다. // you can also use imports, for example: // import java.util.*; // you can write to stdout for debugging purposes, e.g. // System.out.println("this is a debug message"); class Solution { public int solut..
백준 알고리즘 1946번 신입 사원 - 파이썬
www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 그리디 알고리즘. 먼저, 서류 순위를 기준으로 정렬을 해준다. 서류 1등은 무조건 뽑히기 때문에 서류 1등의 면접 순위를 기준으로 나머지 지원자들의 면접 순위 비교를 진행한다. 참고로 문제에서 주어지는 값은 성적이 아닌 순위이다. 계속 성적으로 생각하며 문제 풀이하다가 깨닫고 고쳐서 정답판정을 받았다. 아 시간 초과도 발생하였는데 input 을 sys.stdin.readline 으로 치환해..
백준 알고리즘 1495번 기타리스트 - 파이썬
www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 100, 1 ≤ M ≤ 1000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net DP를 공부하던 중 기타가 취미인 나에게 딱 꽂히는 문제 제목이 보여서 바로 들어갔다. 하지만... 시간 엄청 쓰고 결국 다른 사람 풀이를 참고해 풀었다.... DP를 접할 때마다 나의 멍청함을 매번 느끼게 된다. DP 테이블을 1차원 배열로 선언해서 단순하게 max 값만 취하고 조건만 잘걸어주면 풀릴 줄 알았으나 완전 잘못된 접근이었다. 결국 다른 사람의 코드를 참고해 D..
백준 알고리즘 1654번 랜선 자르기 - 파이썬
www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 이진탐색을 통해 해결하는 방법을 바로 떠올리고 곧장 입력한 뒤 제출 하였으나 계속 검사 80%선에서 Zero Division Error 가 발생하였다. 반례를 혼자 찾기 힘들고 원인이 떠오르지 않아 구글링을 통해 k = 1, n = 1 data = [1] 인 경우 start를 0부터 설정할 시 mid 가 0이 되는 오류를 발견하고 start를 1로 수정하였다. k, n = map(i..
백준 알고리즘 4485번 녹색 옷 입은 애가 젤다지? - 파이썬
www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net BFS로 해결할 수 있는 문제였다. 다만 아직 BFS에 대한 이해도가 떨어지다 보니 쉬운 문제임에도 불구하고 생각보다 많은 시간이 걸렸다. BFS 복습을 계속 해야할 것 같다. from collections import deque dx = [-1, 1, 0, 0] dy = [0, 0, 1, -1] def bfs(i, j, graph, costs): queue = deque() queue.app..
백준 알고리즘 4963번 섬의 개수 - 파이썬
www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 기본적인 DFS 문제였다. 여타 다른 문제에서 일반적으로 4방향을 검사하는 것과 다르게 총 8방향을 검사하도록 풀었다. 다만, RecursionError: maximum recursion depth exceeded while calling a Python object 가 발생해서 인터넷 검색을 통해 recursion limit을 늘려주었다. import sys sys.setrecursionlimit(10*..