본문 바로가기

알고리즘41

[SWEA] 9940. 순열1 (Python3) 문제 링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXHx23oq0REDFAXR&categoryId=AXHx23oq0REDFAXR&categoryType=CODE 나의 논리 N이 입력되었을 때, 순열이 맞다면 1부터 N까지의 숫자가 한 번씩 다 있어야 한다는 점에 착안해서 테스트 케이스로 입력 받은 숫자들을 sorting 해주고 1부터 N까지의 숫자가 차례대로 있다면 "YES" 아니라면 "NO"를 출력하도록 했다. # date: 2020/10/21 # author: psS2mj # brief: SWEA_9940_순열1 (D3) T = int(input()) for tc in range(1,T+1): an.. 2020. 10. 21.
[BOJ] 3052. 나머지 (Python3) 문제 링크 / level: Bronze II www.acmicpc.net/problem/3052 3052번: 나머지 39, 40, 41, 42, 43, 44, 82, 83, 84, 85를 42로 나눈 나머지는 39, 40, 41, 0, 1, 2, 40, 41, 0, 1이다. 서로 다른 값은 모두 6개가 있다. www.acmicpc.net 배열에 관한 문제인데, 여러 가지를 연습해볼 수 있을 것 같아서 도전해봤다. 문제를 풀어본 결과 몇 가지 공부포인트가 있었다. 1. 배열을 선언하고, 길이를 지정하고, 10개의 데이터를 받는 과정 2. 나머지 연산 (이건 Java에서의 연산과 같다.) nums = [0] * 10 for i in range(10): nums[i] = int(input()) % 42 내가 .. 2020. 9. 4.
[BOJ] 2588. 곱셈 (Python3) 문제 링크 / level: Bronze IV https://www.acmicpc.net/problem/2588 2588번: 곱셈 첫째 줄부터 넷째 줄까지 차례대로 (3), (4), (5), (6)에 들어갈 값을 출력한다. www.acmicpc.net 👍이 문제에서 새로 익힌 기술: Extended Slices 15 Extended Slices 15 Extended Slices Ever since Python 1.4, the slicing syntax has supported an optional third ``step'' or ``stride'' argument. For example, these are all legal Python syntax: L[1:10:2], L[:-1:1], L[::-1]. T.. 2020. 9. 1.
[BOJ] 1000. A+B (Python3) 문제 링크 / level: Bronze V https://www.acmicpc.net/problem/1000 1000번: A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net Python은 학부 때 논문 쓰면서 데이터 분석용으로만 썼었는데, 코테용으로 준비를 시작해보기로 했다. 아주 간단한 입출력 문제이지만 나에게는 Python으로 푼 첫 알고리즘 문제니까 기념으로 글을 적어본다. 얼른 Python 문법에 익숙해져서 빠르게 알고리즘 구현 단계까지 넘어가야겠다. Python에서 입력받는 두 가지 방법: 1. 공백으로 구분될 때 -> input().split()의 형태로 받는다. 2. 줄바꿈으로 구분될 때 -> input()의 형태로 받는다. 진짜 .. 2020. 9. 1.
[BOJ] 2740. 행렬 곱셈 (Java) 문제 링크 / level: Bronze I https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 내가 생각한 풀이 고등학교, 대학교 때 많이 계산했던 행렬의 곱셈 연산에 관한 문제였다. 그런데 간단한 규칙에 비해 코드로 구현하는데 생각보다 어려움이 좀 있었다.🤔💦 일단 행렬의 곱셈을 위한 조건을 알아보자. 첫 번째 행렬(first)의 크기: N * M 두 번째 행렬(second)의 크기: M * K 1. 이 중 M의 값이 반드시 같.. 2020. 5. 28.
[알고리즘 이론] 순열과 조합, 그리고 중복순열과 중복조합 순열과 조합, 그리고 중복순열과 중복조합은 알고리즘 문제풀이에서 매우 자주 이용되고, 또 백트래킹이니 DFS니 어쩌구 저쩌구로 이어지는 것들이다. 그래서 코드로 구현하는 것까지는 다음에 하고, 오늘은 이론적인 내용을 예시와 함께 살짝 정리해두려고 한다. 우선 순열과 조합부터 이야기해보자. 이 둘은 중복을 허용하지 않으므로 모두 다른 숫자가 나온다는 공통점이 있다. 순열: 중복을 허용하지 않음. 순서가 의미 있음. 조합: 중복을 허용하지 않음. 순서가 의미 없음. 그리고 순서가 유의미한지의 여부가 둘의 가장 큰 차이다. 가령 주사위를 3번 던진다고 할 때 순열은 1 2 3 1 3 2 이 두 가지가 모두 나올 수 있다. 중복을 허용하지 않으므로 모두 다른 숫자가 나왔고, 순열은 순서가 유의미하므로 [1, 2.. 2020. 5. 25.
[BOJ] 10093. 숫자 (Java) 문제 링크 / level: Bronze II https://www.acmicpc.net/problem/10093 10093번: 숫자 문제 두 양의 정수가 주어졌을 때, 두 수 사이에 있는 정수를 모두 출력하는 프로그램을 작성하시오. 입력 두 정수 A와 B가 주어진다. (1 ≤ A, B ≤ 1015, A와 B의 차이는 최대 100,000) 출력 첫째 줄에 � www.acmicpc.net 내가 생각한 풀이 간밤에 짝꿍이랑 연습 겸 대결을 하면서 풀어본 문제. 난이도도 브론즈인데다가 문제가 너무 심플해서 5분컷 할 줄 알고 건드렸다가 런타임 에러에... 틀렸습니다에.. 아주 난리를 친 문제였다. 자세히 보면 정답 비율이 약 24%밖에 되지 않는 오묘한 문제다. 문제의 핵심은 1. 입력값의 범위를 잘 살펴야한다.. 2020. 5. 24.
[BOJ] 1110. 더하기 사이클 (Java) 문제 링크 / level: Bronze I https://www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net 내가 생각한 풀이 간단한 문제인데 자릿수 이야기가 있어서 문자열로 할까 숫자로 할까 고민하다가 브론즈 문제라서 그냥 간단하게 숫자로 풀었다. 자릿수는 나눗셈과 모듈러 연산으로 처리해줌. 몇 가지 포인트는, 1. 연산하려는 숫자가 한 자릿수일 때와 두 자릿수일 때로 나눠서 처리하는 것 2. 덧셈 연산 한 번 할 때마다 카운트(cnt)도 하나씩.. 2020. 5. 23.
[BOJ] 14681. 사분면 고르기 (Java) 문제 링크 / level: Bronze IV https://www.acmicpc.net/problem/14681 14681번: 사분면 고르기 문제 흔한 수학 문제 중 하나는 주어진 점이 어느 사분면에 속하는지 알아내는 것이다. 사분면은 아래 그림처럼 1부터 4까지 번호를 갖는다. "Quadrant n"은 "제n사분면"이라는 뜻이다. 예를 들어, 좌 www.acmicpc.net 내가 생각한 풀이 x좌표와 y좌표를 입력받은 뒤 두 좌표의 값을 곱한다. 곱해서 양수가 나온다면 (+,+) 또는 (-,-) 조합이니까 x좌표의 값만 검사해서 양수면 1사분면, 음수면 3사분면으로 처리. 곱해서 음수가 나온다면 (-,+) 또는 (+,-) 조합이니까 이번에도 x좌표의 값만 검사해서 음수면 2사분면, 양수면 4사분면으로 .. 2020. 5. 23.

티스토리툴바