코딩테스트 - 백준

문제 백준 2563번/실버5 문제 해석 100 * 100 큰 도화지 안에 10*10 색종이를 여러 개 붙였을 때, 색종이가 붙은 영역의 넓이를 구하는 문제이다. 단 고려해야하는 것은, 색종이를 겹치게 붙였을 경우에는 영역의 넓이는 "10*10 + 10* 10 - 겹치는 범위" 라는 것을 인지하여야한다. 문제 조건으로는 색종이의 왼쪽아래 꼭짓점의 위치가 주어지므로, 이를 이용하여 계산하여야한다. 풀이 전략 문제조건에서는 색종이의 왼쪽아래 꼭짓점의 위치를 주어진다. "10*10 + 10* 10 - 겹치는 범위"를 일일이 계산하기는 귀찮으니까, 그냥 100*100 배열을 생성하고, 색종이의 시작점에 따라 색종이의 영역에 10*10 크기만큼 영역을 표시해주는 방식으로 해보자. 문제 조건에서 색종이는 100개가 ..

문제 백준 1193번/실버5 https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 문제해설 글로 봐도 이해가 바로 가기는 할텐데, 그림같은 순서대로 갈 때, n번째에는 어떤 분수인지 출력하는 문제이다. 풀이 전략 대각선의 순서를 i라고 하자. 1번째 대각선에서는 1개, 2번째 대각선에서는 2개, 세 번째 대각선에서는 3개, i번째 대각선에서는 i개의 분수가 존재한다. 즉 i번째의 순서는 1+2+3+...(i-1) +1 부터 시작하여 1+2+3+...+i 에 끝난다. n이 몇 번째 대각선에 있는지 1부터 i까지의 합 공식 i*(i+1)/2 를 이용하여 i를 구하고, i의 시작지점, ..

문제 백준 9613번/실버4 문제 해설 GCD(Greatest Common Divisor)이란 최대공약수를 의미한다. 테스트 케이스를 입력받고 테스트 케이스만큼의 각 경우의 답을 구하는 문제인데, 각 경우는 각 수들의 모든 쌍들의 최대 공약수를 더해서 테스트 케이스마다 출력을 해줘야하는 문제이다. 풀이전략 보통 우리가 초중학교때 최대공약수를 구하는 방법에는 소인수 분해를 하여 구하는 것이었으나, 코딩테스트 쪽에서는 유클리드 호제법을 많이 사용한다고 한다. 원리같은 것은 잘 모르겠고, 두 줄 요약하자면 a에서 b를 나눴을 때 나머지가 0이면 종료 -> 몫이 최대 공약수 , 그렇지 않다면 2번으로 이동 1번에서 나온 나머지를 c라고 하였을 때, b에서 c를 나누어줌. 나머지가 0이면 종료->이때의 몫이 최대..

문제 백준 11656/실버4 https://www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 문제 해석 접미사 : 어근이나 단어의 뒤에 붙어서 새로운 단어를 만드는 역할 즉, 녹음기 에서 기 자와 같이 단어 뒤에 붙는 단어를 의미한다. 문제에서 baekjoon 에서 baekjoon 자체가 접미사가 될 수 있고, b 뒤에 붙는 aekjoon, ba뒤에 붙는 ekjoon 이 접미사가 될 수 있으니, 접미사가 될 수 있는 모든 경우를 사전순으로 나열하라는 문제이다. 풀이전략 결국 접미사라는 것은 어느 범위부터 끝까지라는 것이 공통으로 구해야한다..

문제 백준 1074번/실버1 https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 문제 해석 2의 몇 제곱인지 알려주는 n, 몇 번째 행인지 알려주는 r, 몇 번째 열인지 알려주는 c, 이렇게 3개를 입력받은 후, 행렬에서 해당 위치에 위치하는 수는 무엇인지 출력해야한다. 단 행렬에서 각 요소의 번호는 Z자를 그리면서 새겨지는 방식이다. 풀이 전략 N의 값이 최대 15이면 행의 길이는 2^15 = 32768, 열의 길이도 32768이다. 만..

문제 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 문제 분석 n과 m 을 입력받고 n개의 문자열이 들어있는 s집합에 m개의 다른 문자열들이 몇 개가 포함되어있는가(일치하는가)를 찾는 문제이다. 주의 해야할 점은 N의 범위는 최대 10000개, M의 범위도 최대 10000개 이므로, 둘 다 반복성이 있는 리스트 또는 튜플을 이용하게 된다면 M의 마지막 단어가 N에 포함되어 있지 않은 경우 이미 10000번째 까..

문제 문제분석 에라토스테네스의 체는 한참 알고리즘 공부할 때 소수 구하는 문제 부분에서 나왔었다. 2부터 시작하여, 2는 실수이므로 2를 제외한 2의 배수들은 모두 제거한다. 2보다 큰 숫자인 3도 실수이므로, 3을 제외한 3의 배수인 모든 뒤쪽의 수들을 전부 지운다. 다음 4는 이미 지워져있으므로 넘어가고, 5는 소수이므로 5를 제외한 모든 배수들을 지운다. 이를 반복하여 소수들을 구하는 것이 에라토스테네스의 체이다. 이도 마찬가지인데, 범위는 n, k를 입력받았을 때 n까지로 정해져있고, k번째로 지워진 수를 구하는 것이고 n의 수가 1000 보다 작으므로 이중포문으로 돌려도 충분한 자원으로 프로그램을 실행시킬 수 있을 것이다. 풀이 전략 이 중 for문 두 번 돌리면서 미리 선언된 배열에서 조건을 ..

문제 문제 링크는 맨 밑에 첨부하였다. 문제분석 a의 원소의 개수, b의 원소의 개수를 입력받고 a의 원소들, b의 원소들을 입력받은 후 a의 원소들에서 b의 원소들을 빼고 남은 길이 + b의 원소들을 빼고 a의 원소들을 빼고 남은 길이를 더해줘야하는 문제이다 풀이 전략 기본적으로 파이썬에서는 set 집합 함수가 주어진다. 핵심적으로 - a.difference(b) : a-b - b.difference(a) : b-a 를 이용하여 구할 수 있으나, 그냥 a-b , b-a 하면 구하고자 하는 값이 바로 나와서 굳이 해당 메소드를 이용하지는 않는다. 코드 결과 고찰 딱히 어려울 건 없었다. 파이썬의 집합을 사용하지 않고 풀어도 살짝 복잡해지는 정도이지 크게 어렵지는 않을 것 같다. set 를 조금 더 정리한..

문제 문제 링크는 글 맨 아래에 첨부하였다. 문제분석 0~9까지의 숫자중 입력받은 수에서 가장 많이 쓰여진 숫자의 개수를 출력하는 문제이다. 단, 숫자 6과 숫자9의 경우에는 둘이 가지고 있는 개수를 각각 균등하게 나눠진다고 이해하면 편하다. 예제 입력 1번같은 경우 6이 0개, 9개 4개 이므로 9의 2개를 6에 2개를 주면 둘 다 2개가 존재하게 되므로 답은 2개 출력된다. 풀이 전략 딕셔너리를 이용하여 키 값을 0~9를 두고, 수를 입력받았을 시 각 자리 별로 키 값의 값을 수정한다. 6과 9의 개수는 더해준 후 2로 나누어서 6과 9에 각각 나누어준다 이후 가장 value 가 큰 값을 가져온다. 코드 고찰 26번째 코드에서 count.tiems()보단 max(count)를 하였으면 원하는 답이 바..