알고리즘

백준 2580 스도쿠 자바

https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net nQueen문제를 이해했다면 충분히 풀 수 있는 문제다. 쉽게 풀진 못했고 2가지 케이스 때문에 많은 고생을 했다. 접근 아이디어 배열을 입력받을 때 0인 배열의 위치 값을 list에 넣는다. 그 후 백트래킹을 하면서 하나하나 값을 확인한다. 해당 자리에 가능한 숫자 배열을 만들고 그 숫자를 하나하나 넣어가며 백트래킹을 한다. 다른 분 코드를 보니 배열을 만들지 않고 숫자를 넣어서 체크하던데 그 ..

백준 9663 N-Queen 자바

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 못 풀어서 답을 봤다. 코드는 간단하지만 생각하기 쉽지 않은 문제다. 접근 방식 단순하게 2차원 배열을 생성하고 모든 경우의 수를 계산하려고 했다. 퀸을 놓은 후 재귀 탐색을 설정하는데 어려움을 겪었었다. 정답을 보고 이해한 뒤에 며칠 뒤 다시 풀어보니 잘 풀렸다. 퀸을 놓을 수 있는지 확인할 때는 1차원 배열이면 충분하다. 가로와 세로 같은 열에 퀸을 놓을 수 없으니 1차원 배열에 row값을 삽입하고 다음 번 ..

프로그래머스 주차요금계산 자바

https://programmers.co.kr/learn/courses/30/lessons/92341 코딩테스트 연습 - 주차 요금 계산 [180, 5000, 10, 600] ["05:34 5961 IN", "06:00 0000 IN", "06:34 0000 OUT", "07:59 5961 OUT", "07:59 0148 IN", "18:59 0000 IN", "19:09 0148 OUT", "22:59 5961 IN", "23:00 5961 OUT"] [14600, 34400, 5000] programmers.co.kr 생각한 방식 차 번호를 기반으로 조회하므로 자료구조는 맵으로 선택했다. 가장 작은 번호순으로 answer배열에 값을 넣고 출력해야 한다. records를 한 번 순회해야 차번호를 정렬할..

백준 2470 자바 드래곤 커브

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 접근 방식 풀지 못했다. 기존에 그린 선을 그대로 90도 회전해서 다시 그려야 한다. 처음에는 재귀 문제인 줄 알고 한참을 생각했다. 답이 나오지 않아서 선을 총 몇 번 그려야 하는지 계산 해보니 2의 k승만큼 선을 그어야 하는 사실을 확인했다. for문으로 Math.pow(2,k)로 접근해봤으나 진척이 나지 않았다. 기존에 그린 선을 90도 회전해서 다시 그려야 하는 ..

백준 18870 자바

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 접근 방식 못풀었다. 나보다 값이 작다면 +1을 하고 중복값을 제거하는 아이디어는 떠올렸다. 중복값 제거하니 Set이 떠올랐고 순위를 저장해서 조회하려면 Map이 필요해서 Set안에 Map을 사용해야하나?? 이런 생각만 든 채로 답을 봤다. 잘한 부분 순위를 매기고 중복을 제거하고 map을 찾은 부분은 잘 접근했다. 부족한 부분 확신이 부족했다. ..

백준 2108 자바

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 자바라는 언어에 대해서 화가나는 문제가 아닐까 싶다. 파이썬이었다면 큰 어려움 없이 순식간에 풀었을텐데 자바로 하니 오래 걸렸다. 특히 최빈값을 추출하는데 이렇게 복잡한 코드가 필요한지 상상도 하지 못했다. 하지만 이 문제를 풀지 않고 코딩테스트에서 최빈값 추출을 해야했다면 상당히 당황했을 것 같다. 잘 한 부분 stream을 적절히 활용했다. 부족한 부분 최빈값 부분에서 파이썬처럼 맵으로 카운트하고 정렬하려고..

백준 1436 자바

https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 브루트포스가 어렵다. 잘 풀리는 것도 있지만 이번에 푼 두개의 브루트포스는 낮은 난이도임에도 모두 풀지 못해서 답을 참고했다. 접근한 부분 사실 접근자체를 하지 못했다. 666에 1~9까지 앞에 붙이고 뒤에는 0~9까지 붙이면서 규칙이 있는지 찾아보려 했는데 보이지 않았다. 규칙이 보이지 않았던 이유는 5666다음에 6666이아니라 6660이기 때문이다. 이 점을 알지 못해서 규칙을 찾지 못했고..

백준 2470 자바

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 당장 어제만 해도 실버 5문제를 풀지 못해서 심란했는데 정답률 낮은 골드 5문제가 손쉽게 풀리는 것을 보니 코딩 테스트를 준비할 땐 회사의 유형에 맞게 준비해야 함을 느꼈다. 접근 방식 정렬한 후 투포인터를 사용했다. 맨 왼쪽에는 음수 or 가장 작은 값이고 오른쪽은 양수 or 가장 큰 값이니 두 값을 합쳐보고 0보다 작다면 왼쪽 값을 늘려서 0에 가깝게, 0보다..

백준 1018 체스판 다시 칠하기

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 실버5문제인데 풀지 못했다. 크게 어렵지 않다고 생각했는데 테케조차 통과하지 못했고 어떤 방법이 문제였는지 피드백을 해보겠다. 접근 아이디어 첫 접근은 간단했다. 4중for문으로 맨왼쪽위에 값을 기본값으로 넣고 다음 값이 맨 윗값과 같으면 count+1을 하고 다르면 맨 윗값에 넣은 값을 바꿔주는 방식으로 설계했다. BWBWBW WBWBWB 처럼 2번째 라인의 경우 전 라인의 값과 달라야 ..

백준 2231 자바

https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 아이디어 1부터 N까지 모든 자리수를 더하면서 값을 탐색하면 쉽게 풀리는 문제다. 잘한 부분 문제 자체가 단순하기 때문에 크게 잘한 부분은 없다. 부족한 부분 3번이나 틀렸다. 코드를 좀 더 꼼꼼히 살펴보지 않은 것이 이유다. 첫 번째는 테케 통과 후 틀렸다. import java.io.BufferedReader; import java.io.IOException; im..