목록Algorithm/백준 BOJ (44)
다희의 코딩 성장일기
[백준] 23288. 주사위 굴리기 2 (자바 JAVA)
[ 문제 ] [백준] 23288. 주사위 굴리기 2 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net # 접근 방법 및 풀이 한번에 풀고 너무 속상했던 문제다. 왜 현장에서는 못 풀었을까.. 사실 아이디어를 떠올리지 못했다. 주사위 굴리기를 한번 풀어봤음에도 떠올리기가 어려운 아이디어였나보다. 아무튼 주사위 굴리기를 풀어본 사람이라면 비교적 쉽게 풀 수 있는 문제다. 이 문제의 핵심은 주사위 도면..
[백준] 10597. 순열장난 (자바 JAVA)
[ 문제 ] [백준] 10597. 순열장난 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net # 접근 방법 및 풀이 dfs + 백트래킹으로 풀었다. 처음에 아이디어 떠올리기가 힘들었는데 범위를 보고 아이디어를 떠올렸다. 순열은 최소 1~50개의 수로 이루어져있고, 1부터 N까지의 수로 이루어졌으므로 최대로 나올 수 있는 숫자가 50이다. 즉 숫자의 범위는 1~50이므로 자리수는 1자리 아님 2자..
[백준] 20922. 겹치는 건 싫어 (자바 JAVA)
[ 문제 ] [백준] 20922. 겹치는 건 싫어 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net # 접근 방법 및 풀이 투포인터 연습문제로 너무 좋은 문제다. 처음에 풀고 4퍼에서 틀려서 반례 찾았는데 다행히 질문검색에 어떤분이 반례 잔뜩 올려주셔서 풀었다. 투포인터는 start포인터와 end포인터를 어디서 시작하고, 각각의 포인터를 어떤 조건일때 움직일지 잘 생각해보아야한다. 코드 자체는 짧게 나오지만,..
[백준] 1541. 잃어버린 괄호 (자바 JAVA)
[ 문제 ] [백준] 1541. 잃어버린 괄호 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net # 접근 방법 및 풀이 그리디 + 문자열 문제다. 처음에 이거보고 바로 아이디어가 안 떠올라서 화가났다. 그리디 문제를 더 풀어봐야할 것 같다. 문제는 적절히 괄호를 쳐서 식의 값을 최소로 만들어야 한다. 최소값이 나오기 위해선 - 기준으로 식을 나누고, +가 있는 식들을 다 계산해서 최종적으로 빼주면 된다. 예제..
[백준] 12851_숨바꼭질2 (자바 JAVA)
[ 문제 ] [백준] 12851_숨바꼭질2 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net # 접근 방법 및 풀이 수빈이의 위치에서 동생의 위치로 -1, +1, *2 일 경우로 이동해보면서 가장 빠른 시간으로 동생의 위치에 도착해야하므로 BFS로 풀었다. 숨바꼭질1을 오래전에 풀고, 비슷한 방식으로 최단시간 안에 동생의 위치에 도착하면 카운팅 해서 경우의 수를 세주면 될 줄 ..
[백준] 9177. 단어 섞기 (자바 JAVA)
[ 문제 ] [백준] 9177. 단어 섞기 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/9177 9177번: 단어 섞기 세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 www.acmicpc.net # 접근 방법 및 풀이 어디 기업 코테 풀면서 봤던 문제 같아서 풀어봤다. 정답률 26으로 극악이다.. 처음에 풀고 50프로만 맞아서 풀이방법 찾아봤다. bfs로 접근해서 다시 풀었다. 입력받은 3개의 단어들은 char[] 배열로 받고, 인덱스로 비교한다. Queue에는 첫번째 단어 인덱스와, 두번째 단어인덱스를 담기위해 Po..