Problem Solving
백준 14500번 - 테트로미노(C++)
문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 설명 엄청난 노가다 문제다. 위 4개의 테트로미노 모양으로 숫자를 묶었을 때 가장 큰 수를 출력해야 하는데, 문제는 테트로미노를 회전하고 대칭시켜도 된다는 것이다. 그래서 총 2(하늘) + 1(노랑) + 4(분홍) + 4(초록) + 8(주황) = 19개의 경우의 수가 있는데 이걸 하나하나 계산하고 싶지는 않았다. 그래서 짱돌같은 내 머리를 열심히 굴려 좀 더 예쁜 코드를 짰다. 하늘색 경우의..
백준 2812번 - 크게 만들기(Swift)
문제 www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 설명 n과 k를 입력받은 다음 들어오는 N자리 숫자는 Int로 저장하지 않고 인덱스를 통해 숫자 하나하나에 접근하기 위해 Character 배열로 저장한다. 숫자의 왼편부터 제일 오른편 숫자까지 하나씩 검사하며 지금 스택의 top에 있는 숫자와 비교한다. top보다 지금 검사하고 있는 수가 더 크다면 스택에서 top을 pop한 후에 지금 검사하고 있는 수를 집어넣고 k를 1만큼 감소시킨다. 모든 루프를 마친 후 stack의 0번째부터 stack.count - k - 1번째 인덱스에 ..
백준 9519번 - 졸려(Python)
문제 https://www.acmicpc.net/problem/9519 9519번: 졸려 문제 선영이는 다가오는 COCI에 사용할 데이터를 만드느라 삼일동안 깨어있었다. 더 이상 데이터를 만들 수 없는 상황에 이르렀고, 심지어 선영이는 신경쇠약에 걸려 아무것도 제대로 보지 못하� www.acmicpc.net 풀이 처음으로 생각해 낸 방법은 문제에 나와있는 셔플을 그대로 역으로 실행하는 것을 n만큼 반복하는 반복하는 것이었는데, 문제를 잘 보니 n 크기가 최대 10억이었다(...). 보통 이렇게 무언가를 반복해야 하는 문제인데 n값이 터무니없이 크다면 주기가 있는 경우가 많아서, 일단 문제에 나와있는 대로 코드를 짠 다음 주기를 찾아보려고 했다. 4~10글자로 셔플을 돌려보니 주기가 있는 것은 확실한데, ..
백준 11582번 - 치킨 TOP N(C++)
문제 https://www.acmicpc.net/problem/11582 11582번: 치킨 TOP N 인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많�� www.acmicpc.net 풀이 간단하다. 머지 소트를 돌리다가 조건을 만족하면 중간에 정렬을 멈추는 것이다. 하지만 난 이 간단한 문제에 갈피를 못잡고 뻘짓을 하다가 강사님의 힌트를 보고 광명을 찾았다. 내가 한 뻘짓은 my_merge() 함수에서 지금 정렬중인 인원이 입력으로 주어진 인원보다 적으면 바로 리스트를 출력하도록 코드를 짰는데, 생각해보니 이게 왼쪽 서브리스트의 정렬이 ..
백준 10825번 - 국영수(C++, Python - lambda)
문제 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 풀이 C++에서는 학생 구조체 배열을 만들어 이름과 국어, 영어, 수학 점수를 저장한 다음 compare 함수를 통해 조건에 맞게 정렬한다. Python에서는 lambda 함수를 이용해서 정렬할 수 있다. wow 나의 코드 - C++ #include #include #include using namespace std; struct person { char name[11]..
백준 1248번 - 맞춰봐(Python)
초급 스터디 - 02 Backtracking 예제 * 강의를 들으며 배운 것을 정리하는 포스팅입니다. 제가 생각해낸 아이디어가 아닙니다. * 문제 https://www.acmicpc.net/problem/1248 1248번: 맞춰봐 문제 규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 www.acmicpc.net 풀이 입력으로 주어진 조건을 n x n 배열에 저장한 다음 각 조건을 검사하는 방법은 1)행 단위, 2)열 단위의 두 가지 방법이 있다. 1) 행 단위로 검사를 하는 경우는 n = 4일 때 0부터 0까지의 합, 0부터 1까지의 합, 0부터 3까지의 합..
백준 15811번 - 복면산!?(Python)
초급 스터디 - 01.5 Permutation and Combination 연습문제 F https://www.acmicpc.net/problem/15811 15811번: 복면산?! 복면산이란 수학 퍼즐의 일종으로, 어떤 계산식의 각 숫자들을 특정 문자로 바꾸면 각 문자가 어떤 숫자인지 맞추는 퍼즐이다. 대표적으로 SEND+MORE=MONEY가 있다. SEND + MORE ------ MONEY S=9, E=5, N=6, D=7, www.acmicpc.net 문제 복면산 문제인데, 파이썬의 itertools 라이브러리를 잘 사용하면 쉽게 풀 수 있을 것 같았다. 코드 설명 우선 첫 번째 단어와 두 번째 단어, 그리고 정답 단어를 각각 op1, op2, ans로 입력받은 다음, 집합으로 변형시켜 중복을 없애..
백준 2675번 - 문자열 반복(Python)
num = int(input()) for i in range(num): number, string = input().split() txt = '' for j in string: txt += j * int(number) print(txt) string의 각 문자를 number만큼 반복하여 txt에 붙여넣고 출력. 초간단 하지만 이 문제의 의문점은 num = int(input()) for i in range(num): number, string = input().split() for x in string: print(x * int(number), end='\n' if x == string[-1] else '') 왜 저 코드는 맞고 이 코드는 틀리냐는 것. 아직도 반례를 못 찾았다.
백준 1431번 - 시리얼 번호(Python)
https://www.acmicpc.net/problem/1431 문제 다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다. 모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다. 시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다. A와 B의 길이가 다르면, 짧은 것이 먼저 온다. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다) 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로..