본문 바로가기

Studying

 (94)
[백준]_1316번 : 그룹 단어 체커(파이썬 and C언어) 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 전략 조금 까다로워 보이는 문제이다. 어느 알파벳이 연속으로 배치되어 있는지 알아내야 하고 또한 한 번만 쓰인 알파벳이면 연속이라고 가정해야 한다. 파이썬은 다행히도 문자열을 원하는 인덱스 범위 안에서 자를 수 있다. 따라서 인덱스 i와 i+1의 요소가 같다면 i를 1 증가시키고 만약 같지 않다면 문자를 [i+2:]로 묶는다. 예를 들어 apple을 [2:]로 묶으면 ple가 된다. 시도 1(Python) import sys in..
[알고리즘] 이진 탐색(Binary Search) INDEX 1. 정의 2. 방법 3. 소스 구현 4. 장점 5. 단점 1. 정의 ▶ 오름차순으로 정렬된 1차원 배열에서 특정한 값을 찾아내는 알고리즘 반드시 오름차순으로 정렬된 배열에서만 사용 가능하다. 왜냐하면 찾으려는 숫자가 n일 때 현재의 위치가 n보다 작을 때 n은 반드시 현재의 위치보다 뒤에 있음을 기본으로 깔고 있기 때문이다. 또한 이진 탐색을 사용하는 목적은 크게 두 가지가 있다. 찾고자 하는 원소가 배열에 있는지에 대한 존재 여부. 찾고자 하는 원소가 배열에 있다는 것을 확실히 알고 있지만 위치 정보를 알고 싶을 때. 2. 방법 오름차순 배열과 찾고자 하는 값(6)이 있다고 가정하자. { 1, 2, 3, 4, 5, 6, 7 } 우선 배열의 중간에 있는 값(4)을 입력한다. 현재 위치(4)와..
[백준]_1312 번 : 소수(파이썬 and C언어) 1312번: 소수 피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. www.acmicpc.net 관찰 솔직히 처음 보았을 때는 너무 쉬워 보였다. 하지만 우리의 컴퓨터는 소수점을 잘 다루지 못한다.. 또한 계산할 숫자들의 크기를 조심해야 한다. 일단 a/b의 값을 c에 저장하고 c를 소수점 아래로 쪼개는 방법이 있을 것이다. 하지만 이렇게 할 시 어떤 문제점이 생기는지 확인해 보자. 시도 1(Python) import sys input=sys.stdin.readline a,b,n=map(int, input().split()) ls=list(str(a/b..
[백준]_1181번 : 단어 정렬(파이썬 and C언어) 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 그냥 말 그대로 조건들만 만족시키면 된다. 다행히도 파이썬은 리스크에 문자형 자료형이 있어도 sort을 사용하면 알파벳 순서로 정리해 주는 쩌는 기능이 있다. 또한 중복을 제거하는 조건은 집합(set)을 통해 간단히 해결할 수 있는데, 대신 순서가 중구난방으로 바뀌기 때문에 다시 list로 만들어주는 작업은 수도 없이 해보아서 이번 문제는 그다지 험난한 길이 아닐 것 같다 전략 단어를 하나 씩 리스트(ls)로 받는다. 그냥 input과 sys를 이용했..
[백준]_1193 : 분수 찾기(파이썬 and C언어) 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 분수 표에서 지그재그로 내려오면서 몇 번째 순서에 어떤 분수를 출력할지 고민해야 되는 패턴에 미쳐버린 문제이다. 규칙 사냥 규칙은 단순 계산의 연속이기 때문에 인간보다 제대로 된 수식만 알려준다면 컴퓨터가 잘 해결해 줄 것이다. 먼저 위의 표를 보면서 규칙을 생각해 보자. 뭔가 시점(빨간 화살표)이 대각선으로 움직이는 것에서 규칙을 찾아내기에는 살짝 불편한 것 같다. 따라서 아래와 같이 표를 변형시켜 주겠다. 1 / 1 (1) 1 / 2 (2) 2 / 1 (3) 3 / 1 (4) 2 / 2 (5) 1 / 3 (6) 1 / 4 (7) 2 / 3 (8) 3 / 2 (9) 4 / 1 (10) 분수 ..
[백준]_1010번 : 다리 놓기(파이썬 and C언어) 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 강 동쪽(치역)과 같이 현재 상황을 일대일대응 함수로 치환할 수 있다는 것이다. 고등학교 수학(하)교육과정은 바뀌기 때문에 만약 이 글 작성 시점 이후로 순열과 조합이 수학(하)에 들어있지 않다면 필자를 틀이라 생각하고 넘어가주길 바란다..에 배정되어 있는 순열 또는 조합을 활용하는 문제이..

티스토리툴바