백준

[백준/JAVA] 1620: 나는야 포켓몬 마스터 이다솜문자열과 번호를 연결지어 입력받아 검색하는 문제이다. 처음에 HashMap을 썼는데도 시간초과가 났다. key로 value는 금방 찾을 수 있지만 value로 key를 찾는 건 반복문이 필요한 문제가 있었다. 검

[백준/JAVA] 2751: 수 정렬하기2n개의 수를 오름차순으로 정렬하는 문제이다. n의 개수와 그 절댓값의 크기가 상당히 넓어서 처음에 아무 생각 없이 sort를 썼다가 시간 초과가 났다. 시간복잡도를 줄이기 위해서 다음 방법들을 사용했다.Scanner 대신 Bu

[백준/JAVA] 10989: 수 정렬하기3Counting sort를 사용하여 정렬하는 문제이다.Counting sort란 배열에서 해당 숫자가 나온 개수를 세서 새로운 배열의 각 인덱스에 저장하고 그 갯수만큼 해당 숫자를 출력하는 정렬이다.시간 복잡도는 O(n)이나

[백준/JAVA] 2869: 달팽이는 올라가고 싶다처음 문제를 봤을 때 무슨 소린지 잘 와닿지가 않았는데 이해만 하면 의외로 간단한 문제이다.v미터의 막대기가 있는데 달팽이는 하루에 a미터 올라가고 b미터 미끄러지는 것을 반복한다. 즉 v+a-b+a-b... 이다.주

[백준/JAVA] 1193: 분수찾기이해만 하면 코드 자체는 간단한데 이해하기가 상당히 어려운 문제였다. 처음에는 순서를 잘못 이해했었는데, 진행방향은 아래와 같다.대각선 왼쪽 위부터 홀수번째 라인은 ↗ 방향으로 나아가고 짝수번째 라인은 ↙ 방향으로 나아가는 지그재그

[백준/JAVA] 1018: 체스판 다시 칠하기문제가 쉬워 보이는데 코드 만들기가 살짝 복잡하다.브루트 포스로 푸는 게 제일 간단한데 더 나은 방법이 있는지는 모르겠다. 케이스가 많지 않아서 브루트 포스를 해도 극단적으로 많은 시간이 걸리지는 않는다.문제 설명에서 힌

[백준/JAVA] 1436: 영화감독 숌n번째 영화의 제목은 n번째로 작은 종말의 수라는 말에 유의한다.이 문제에서 종말의 수란 "666"이 들어가는 n번째로 가장 작은 수이다.즉 종말의 수는 1666, 2666, ... 6666, 6660, 6661, ... 666

[백준/JAVA] 1181: 단어 정렬n개의 알파벳 단어가 입력으로 주어지면 길이가 짧은 것 우선길이가 같다면 사전 순으로정렬하는 문제이다. 이때 중복된 단어는 하나만 남기고 제거해야 한다.단어 중복을 제거하기 위해 HashSet을 사용하였다 HashSet에서는 입력

[백준/JAVA] 18870: 좌표 압축수직선 위에 N개의 좌표 X1, X2, ..., XN이 있을 때 Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.대충 봤을 때 말이 직관적으로 이해가 되지 않는데, 쉽게

[백준/Python] 2485: 가로수여러 개의 가로수의 위치가 주어질 때, 가로수들의 간격을 일정하게 하기 위해 몇 개의 가로수를 더 심어야 하는지를 찾는 문제이다.예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를

[백준/Python] 1929: 소수 구하기m과 n이 입력으로 주어질 때, m 이상 n 이하의 소수를 모두 출력하는 문제이다. 문제 자체는 간단한데 isPrime 함수에 n == 1일 시 False를 리턴해야 한다는 점을 빼먹어서 틀렸다.소수는 1과 자기 자신만으로

[백준/Python] 4948: 베르트랑 공준 임의의 자연수 n이 주어질 때 n보다 크고 2n보다 작거나 같은 소수의 개수를 찾는 문제이다. 처음엔 간단한 문제라고 생각해서 1929: 소수 구하기의 코드를 약간 변형해서 그대로 제출했는데 시간 초과가 났다. (시간

[백준/Python] 13909: 창문 닫기n개의 창문과 n개의 사람이 있다. 처음에 모든 창문이 닫혀 있다.1번째 사람은 처음에 모든 창문을 연다.2번째 사람은 2, 4, 6, 8... 번째 창문을 닫는다.3번째 사람은 3, 6, 9... 번째 창문을 열거나 닫는다

[백준/Python] 1010: 다리 놓기서쪽에 n개의 다리가 있고 동쪽에 m개의 다리가 있을 때 서쪽의 다리와 동쪽의 다리를 잇는 경우의 수를 구하는 문제이다. 이때 $n<m$이다.경우의 수는 $nCk$이고 결국은 이항계수를 구하는 문제이다. 유의할 점은 시간

[백준/Python] 2108: 통계학산술평균, 중앙값, 최빈값, 범위(최댓값과 최솟값의 차이)를 출력해야 한다.크게 어려운 문제는 아니라고 생각했는데 제출해 보니 시간 초과가 났다.문제는 입력을 input()으로 받은 점이었다. 파이썬의 입력에서 input()과 s

[백준/JAVA] 20920: 영단어 암기는 괴로워n개 문자열을 입력받은 후자주 나오는 단어일수록 앞에 배치한다.해당 단어의 길이가 길수록 앞에 배치한다.알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다.위 정렬 조건에 따라 정렬하는 문제이다. 이때 길이가 m보

[백준/Python] 9012: 괄호설명이 복잡하게 적혀 있긴 하지만 단순히 괄호가 올바른지를 검사하는 balacned parentheses 문제이다.열린 괄호가 있으면 그에 맞는 닫힌 괄호 쌍이 존재해야 한다. 이는 스택 구조를 이용해 풀 수 있다.우선 여는 괄호가

[백준/Python] 1874: 스택 수열n개의 수가 주어질 때 수들을 스택에 오름차순으로 push한 뒤, pop하면서 주어진 수열을 만들수 있는지를 묻는 문제이다. 예를 들어 입력으로 4 3 6 8 7 5 2 1 이 주어지면오름차순으로 정렬했을 때는 1 2 3

[백준/Python] 11866: 요세푸스 문제 0 요세푸스 문제에서 사람들이 선택되는 순서를 구하는 문제이다. 알고리즘 분류는 큐에 속하지만 순환식으로 푸는 방법또한 존재한다. 큐로 푸는 경우에 2164: 카드2 문제의 코드를 조금만 수정하면 쉽게 풀 수 있다.

[백준/Python] 5430: AC정답률이 19%인것부터 예상하긴 했지만 열심히 코드를 써서 내보니 시간초과가 났다...처음 제출했던 코드찾아보니 reverse()함수의 시간복잡도가 $O(n)$이라 실행시간에 큰 영향을 주고 있었다.조금만 생각해 보니 R이 등장할

\[백준/Python] 2447: 별 찍기 - 10n이 입력으로 주어질때 해당하는 프랙탈 패턴을 출력하는 문제이다. 이때 n은 3의 거듭제곱이다.주어진 패턴을 보면 n = 3일 때의 패턴이 크기가 커지며 반복되고 있다는 것을 알 수 있다.

\[백준/C++] 2580: 스도쿠코드를 짜기가 굉장히 막막했는데 어떻게든 코드를 짜보려고 했다. 개인적으로 재귀가 너무 어려워서 아직도 원리에 대해 제대로 이해하지 못하고 있는 것 같다.처음에 check 함수와 sudoku 함수 두개를 만들어서 각각의 셀에 대해 ch

\[백준/JAVA] 14888: 연산자 끼워넣기1부터 N까지의 수열이 있을 때 N-1개의 연산자가 주어지면 수와 수 사이에 연산자를 넣는다. 이 결과값의 경우의 수의 최솟값과 최댓값을 구하는 문제이다. 이때 연산자 우선순위를 신경쓰지 않고 왼쪽부터 차례대로 연산하며 수

\[백준/JAVA] 14889: 스타트와 링크스타트 팀과 링크 팀이 있을 때, 각 팀에 존재하는 선수들끼리의 짝에 따라 팀의 능력치가 증가한다. 이때 두 팀의 능력치 차이를 최소로 만들고자 한다.백트래킹이 사용되는 부분은 팀을 나누는 케이스를 구하는 부분이다. 1 2

\[백준/JAVA] 1904: 01타일크기가 n인 2진 수열을 만드는데, 0은 무조건 짝수개씩만 붙어있을 수 있다. n일때의 2진 수열의 경우의 수를 구하고 이를 15746으로 나눈 나머지를 출력해야 한다.뜬금없이 15746으로 나누는 이유는 무엇인가 했는데, n이 너

[백준/JAVA] 1912: 연속합 n개의 임의의 수열이 주어질 때 1개 이상의 수를 연속적으로 선택하여 최대 합이 되는 경우를 구한다. 문제에서 최대합을 찾을 때 최대합의 일부분은 그 부분에 대한 최대합이라는 점에 유의한다. 소스코드

\[백준/JAVA] 1149: RGB거리연속된 주어진 집들을 R, G, B 색상으로 칠해야 하는데, 이때 이웃하는 집끼리는 같은 색이 될 수 없다. 집을 칠하는 비용은 각각의 색상에 따라 달라지며, 조건에 따라 색을 칠할 때 비용이 최소가 되도록 한다.처음 1번째 집을

\[백준/JAVA] 12865: 평범한 배낭N개의 물건이 있고 각 물건은 W의 무게와 V의 가치를 가진다. 이때 물건들의 가치를 최대화하면서 무게제한인 K를 넘지 않도록 물건을 고르는 경우의 수를 찾는다.이 문제는 다이나믹 프로그래밍에서 유명한 알고리즘 문제인 knap

\[백준/JAVA] 9251: LCSLCS란 Longest Common Susequence(최장 공통 부분 문자열)의 약자로, common sequence들 중 가장 긴 것을 뜻한다.예를 들어 <span style="background-color:어떤 문제를 DP

\[백준/JAVA] 2559: 수열연속적인 k일의 온도의 합이 최대가 되는 값을 누적합으로 찾아야 한다.브루트 포스로 풀면 중복 계산이 아주 많이 일어날 수밖에 없는 문제이다. k일의 연속된 합을 구할 때 가운데 값은 중복되고, 달라지는 것은 가장 맨 앞과 가장 맨 뒤

\[백준/JAVA] 11053: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구해야 한다.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 30,

\[백준/JAVA] 24511: queuestackqueuestack이라는 특정한 자료구조가 있고, 수열의 값을 입력받아 이를 자료구조에 넣는다. queuestack은 다음과 같이 동작한다.입력받은 수 x0을 1번 자료구조에 삽입한다.1번 자료구조에서 원소를 pop한다

\[백준/JAVA] 9935: 문자열 폭발주어진 문자열에 폭발 문자열이 존재하면 그 문자열 부분을 없애버린다. 유의할 점은 폭발 문자열을 제거하여 새로 생긴 문자열에 또 폭발 문자열이 존재하면, 또 폭발이 일어나야 한다. 모든 폭발이 끝난 후에 남은 문자열을 출력하고,