Changmo_log

4/28일부로 백준의 서비스가 종료됐다. ㅜㅜ추후 문제만 볼 수 있는 사이트로 돌아온다고는 하지만 기간이 많이 남은 상태이므로,Do it 알고리즘 코딩테스트 Python.의 책에 있는 문제들을 통해 정리해보겠다. 11660: 구간 합 구하기 2 (실버 1) N × N개의 수가 N × N 크기의 표에 채워져 있다. 표 안의 수 중 (X, Y)에서 (X, Y)까지의 합을 구하려 한다. X는 행, Y는 열을 의미한다. 예를 들어 N = 4이고, 표가 다음과 같이 채워져 있을 때를 살펴보자. (2, 2)에서 (3, 4) 까지의 합을 구하면 3 + 4 + 5 + 4 + 5 + 6 = 27이고, (4, 4)에서 (4, 4)까지의 합을 구하면 7이다. 표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때 이를 처리..

이번 문제는 백준 난이도 골드4인 '스도쿠' 문제이다. 우선 문제에 대해 먼저 설명을 하면 우리가 흔히 아는 스도쿠의 개념을 그대로 프로그래밍에 적용하는 건데직접 좌표를 입력해서 좌표 내에 숫자가 0인 좌표가 빈칸이라고 생각하면 된다. 문제를 풀기 전에 스도쿠의 조건을 한번 정리해보자면가로줄에 중복되는 숫자가 없어야 한다.세로줄에 중복되는 숫자가 없어야 한다.3x3 크기의 보드에 중복되는 숫자가 없어야 한다. → 위 조건을 만족하면서 1~9까지의 숫자를 채우면 된다. [Python] 일단 직관적으로 생각해서 접근해보게 되면.스도쿠의 전체 보드를 탐색하면서 0인 좌표를 찾고, 해당 좌표에 1~9까지 숫자를 대입해보며 넣을 수 있는 숫자를 찾으면 된다. 그럼 지금 내가 말한 방식으로라면for x for..

이번 문제는 백준 난이도 실버 2인 '골드바흐 파티션' 문제이다.https://www.acmicpc.net/problem/17103 이 문제는 골드바흐 추측에 따라 어떤 짝수가 입력됐을 때, 그 짝수의 골드바흐 파티션 갯수를 구하는 문제다. 골드바흐 파티션이란?: 골드바흐 추측에 따르면 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다는 것이다.즉, 어떤 짝수. 예로 4가 주어졌을 때,이 4는 4이하의 소수 (2, 3)중에서 두 개의 소수를 가지는 쌍의 합으로 4를 표현할 수 있다는 의미다.→ 여기서 포인트! 동일한 소수의 쌍으로도 가능하다는 점이다. 2+2 = 4 이런식으로 말이다. 6이라면 (2, 3, 5) 중 3 + 3 = 6을 만들 수 있고,10이라면 (2, 3, 5, 7) 중 3 + ..

이번 문제는 백준 난이도 실버 4인 '다음 소수'문제이다. 테스트 케이스가 주어지면 그 수만큼 정수 입력을 반복해, 해당 정수보다 큰 소수 중 가장 작은 소수를 출력하는 문제이다. 소수란?: 소수는 1과 자기 자신만을 약수로 가지는 수이다. 예로 7, 13과 같은 수가 소수이다. → 7은 (1, 7), 13은 (1, 13) 추가로 합성수의 개념도 짚고 가자합성수란?: 합성수는 1과 자기 자신 외에도 약수를 가지는 수이다. 편하게 4, 6, 12 등 여러 개의 약수를 가지는 수가 합성수라고 생각하면 된다. 그럼 소수를 구하는데 합성수의 개념은 왜 나온 걸까?합성수는 N이라는 정수가 존재할 때, √N 이하의 약수를 무조건 하나 가진다.예로 9라는 숫자가 있다면 √9 = 3이고. 9의 약수는 (1, 3, ..

이번 문제는 백준 난이도 실버5인 '영화감독 숌' 문제다. 이 문제는 종말의 수인 '666'이 들어가는 수를 작은 순으로 나열하고제목을 시리즈 별로 제작할 때 '종말의 세상 1', '종말의 세상 2' 이런 식이 아닌 '666'이 들어간 수를 작은 순으로 나열한 숫자로 사용하자는 의미이며N번째 시리즈 제목을 제작하려 할 때 N번째에 해당하는 숫자가 무엇인지 찾는 문제이다. 실제로 나열해보면 1 : 6662 : 16663 : 26664 : 36665 : 46666 : 56667 : 6660 → 5666다음이 6660인 이유는 666이 포함되면서 6660보다 작은 수는 없기 때문이다 ..

이번 문제는 백준 난이도 실버4인 '설탕 배달' 문제다. 이 문제는 최대 5000kg의 설탕을 5kg, 3kg의 두 봉지를 이용해 최대한 작은 봉지의 수를 사용해서 5000kg의 설탕을 딱맞아떨어지게 운반하는 봉지수를 구하는 문제다. 일단 이런 문제는 특별한 수학적 공식이 존재하지 않는다.그리고 입력값 또한 5000이하로 작기 때문에 직접 모든 경우의 수를 시도해서 구하는 브루트포스 방법으로 해결하는 게코드도 단순하고 효율적이다. . 그렇다면 모든 경우의 수를 시도하려면 어떻게 하면 될까?일단 문제의 특징을 보면 봉지의 수를 가장 작게 사용하는 것이 목표다.그렇다면 5키로의 봉지를 최대한 많이 사용하고 남은 설탕을 3키로로 딱 맞아떨어지게 사용하면 된다.가장 빠르게 구하기 위해선 5키로의 봉지를 최..

이번 문제는 백준 난이도 실버5 '분수찾기' 문제이다.https://www.acmicpc.net/problem/1193 문제의 조건은 나와있는 그림의 분수처럼 위치해 있는 2차원 배열맵에서 지그재그로 이동해야한다.→ 그림으로 표현하면 이런 식으로 이동한다는 뜻이다. 그런데 맵을 자세히 보면 분수형태로 표현되어있지만 이건 곧 원소의 위치를 나타내는 것이기도 하다.→ 행/열 형태. 즉, 2차원 맵을 지그재그로 이동하며 이동 시마다 값이 1씩 증가하게 되는 규칙을 따른다. 그렇게 한 숫자를 입력했을 때 해당 숫자가 위치한 행/열 주소를 출력하는 문제다. 규칙을 보면 대각선으로 이동하며 각 각 층으로 나눠 표시할 수 있을 것 같다.이런식으로그리고 층이 증가할 수록 해당 층의 원소 갯수가 1씩 증가한다.Ex)..

백준 난이도 실버5 정도 되는 '그룹 단어 체커' 문제를 해결해보았다. 이 문제는 그룹 단어라고 해서 한 알파벳이 연속돼서 나타나 한 단어를 이룬 것이다.즉 입력받은 문자열에서 각 문자를 하나씩 조건에 비교하며 그룹 단어인지 체크한 후 카운팅하는 방식으로 풀어나가면 된다. [조건]신경써야할 조건들은이전 단어와 비교하여 같은 단어인지해당 단어가 이미 사용된 적이 있는지최종적으로 그룹 단어인지이렇게 체크를 해서 카운트 할 수 있다. PYTHON import sysinput = sys.stdin.readlinenum = int(input())count = 0 기본 세팅을 해준다.결과 값을 위해 count 변수 생성for _ in range(num): str = input().strip() chec..

백준 10828번 문제는 스택을 이용하여 각 기능을 구현해보는 문제이다.시간 제한은 0.5초명령의 수는 10,000개 이하  첫번째로 내가 시도한 방법은Scanner를 통한 입력과 Stack클래스를 사용하여 기능을 구현하고 split()메소드를 사용해서 각 명령을 구분했다.import java.util.Scanner;import java.util.Stack;public class Baekjoon10828 { public static void main(String args[]) { Scanner sc = new Scanner(System.in); Stack stack = new Stack(); int N; int pushNum; String order; N = sc.nextInt(); sc.n..