선택과 집중

목차 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 설계&풀이 아이디어는 옳게 접근했으나, 구현을 못했다. 요건은 간단하다. -를 기준으로 split 해주고, 나머지 애들을 다 묶어버리면 된다. 여러가지 케이스가 있는데.. 10+20-10 맨 앞이 +로 시작해서 묶이는 경우 10-20 맨 앞이 단순 숫자인 경우 10-20+30 맨 앞은 숫자, 뒤가 +로 묶이는 경우 10 하나만 들어오는 경우 10+20 +만 들어오는 경우 10-20..

목차 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 설계&풀이 백트래킹의 기본문제다. 매번 DFS/BFS를 도망만 다녔다가 각잡고 제대로 공부해보고자.. N과M 시리즈를 시작해봤다. 요건은 간단하다. 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. - 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 백트래킹이란걸 아는 상태에서 DFS를 적용해보려고 했는데, 도저히 감..

목차 문제 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 설계&풀이 좌표 압축이란, 주어진 좌표를 크기순으로 정렬하는 행위를 말한다. 예를들어 다음과 같은 리스트(좌표) 가 주어졌다고 가정하면.. tempList = [1, 3, 4, 2, 4] # 좌표압축 실행 후 print(tempList) # 결과 ''' [0, 2, 3, 1, 2] ''' 이런식으로, 오름차순 정렬 기준으로 1은 0번째 ..

목차 문제 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 설계&풀이 처음엔 별다른 알고리즘을 생각하지 않고 그냥 for문 돌려서 풀려고 했다. 그런데 결과는 시간초과. 뭘까 뭘까.. 생각을 하다가, 투포인터가 생각나서 투포인터로 풀어봤는데, 정답이었다. 처음 코드는 다음과 같다. ''' 1. 일반적인 회문 판단 함수, 정답을 출력하는 함수 두개로 나뉘어서 작업해주자 ''' import sys t = int(input()) # 0, 1, 2중 하나 출력해주는 함수 def p..

목차 문제 https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 설계&풀이과정 먼저 시간초과가 난 내 코드다. import sys # 시간초과 풀이 n, m = map(int, input().split()) hPeople = [ sys.stdin.readline().rstrip() for _ in range(n) ] sPeople = [ sys.stdin.readline().rstrip() for _ in range(m) ] answer = [] ..

목차 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 설계 및 풀이 DP 문제이다. 사실 문제 유형을 어떻게 알아내는지는 좀 더 문제를 풀어봐야 알 것 같다. 처음엔 재귀로 풀었는데, 재귀로 풀다보니 시간 초과가 되어서 뭘까 고민하다가 결국 답지를 봤는데.. DP더라... 먼저, 재귀로 푼 코드다. cntZero = 0 cntOne = 0 def fibonacci(n): global cntZero global cntOne if n == 0: cntZero += 1 return 0 elif n == 1: cntOne += 1 return..

문제 www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는다. 합이 M을 넘지 않는 카드 3장을 찾을 수 있 www.acmicpc.net 설계 브루트포스는 '모든 경우의 수'를 탐색하는 알고리즘이다. 말 그대로 '무식한 힘' 알고리즘이다. 장점으로는 정답을 100% 찾아낼 수 있다는 것이지만, 단점은 당연히 효율이 극단적으로 떨어진다는 것이다. 하지만 브루트포스가 오히려 코드가 간결한 문제들이 몇 개 있다. 이런 문제 같은 경우다. 먼저 변수들을 선언해주고 필요한 정보를 입력해줬다. n과 m은 문제에 있는 ..

문제 www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B > up >> down >> top; int answer = top / (up - down); cout = top ? answ..

문제 코드 Scanner대신 BufferedReader, Writer를 써봤다. 이걸로 쓰는 습관을 들이는게 좋을듯. 먼저 어떻게 풀지 생각해보면.. 개행문자나 공백을 구분해서 역순으로 출력해야한다. 이 경우 스택을 쓰는게 간편하고, 일반적인 배열로도 풀 수 있지만 효율이 안좋으니 그건 패스하도록 하겠다. (그냥 문자열 입력받고, 배열의 크기만큼 for문돌려서 뒷 인덱스부터 출력하면된다. 근데 스택이있잖아?) 암튼 전체 코드다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader..

문제 코드 Stack을 import하지 말고 풀기와 하고 풀기 둘 다 해봤다. 뭐 어차피 평소엔 Stack import해서 쓰는데 복습할 겸.. Stack import X import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] stack = new int[n]; int size = 0; while(n-- > 0){ String cmd = sc.next(); if(cmd.equals("push")){ int num = Integer.parseInt(sc.next()); stack[size++] ..