본문 바로가기

전체 글1064

백준 1138 자바 - 한 줄로 서기 (BOJ 1138 JAVA) [ 문제보기 ] [ 코드보기(깃헙) ] N이 최대 10이다. 따라서 모든 경우를 보려면 10! 번을 봐야한다. 이 경우 362880번으로, 사실 모든 경우를 봐도 가능하긴 하다! 다해봐야 O(N! * N) 정도이다. 사실 시간복잡도, 메모리복잡도 면에서 모두 이득인 방법이 더 있다. 어차피 입력이 키가 1인 사람부터 차례대로 들어오기 때문에, 키가 큰 사람부터 순서대로 입력을 만족하는 위치에 넣어버리면 된다. (따라서 그리디 알고리즘 분류다.) 4 2 1 1 0 의 입력을 확인해보자. 이 경우 키가 1인 사람은 좌측에 2명, 2인 사람은 좌측에 1명, 3인 사람은 좌측에 1명, 4인 사람은 좌측에 아무도 없다는 입력이다. 키가 작은 사람부터 보자면 어려운 문제가 확실하지만, 키가 큰 사람부터 보면 엄청 .. 2021. 11. 3.
백준 1485 자바 - 정사각형 (BOJ 1485 JAVA) [ 문제 보기 ] [ 코드 보기(깃헙) ] [ 틀린 경우 ] 처음엔 아래와 같이 축에 평핸한 정사각형을 찾는줄 알았다. 그래서 예를들어 입력이 1 1 1 1 2 2 1 2 2 와 같다면, 사실 좌측이 x축인지 우측이 x축인지는 안알려줬지만 상관없이 좌측이 2종류고, 우측이 2종류이며 각각 2번씩 나왔고, 좌측의 2종류의 차이와 우측의 2종류의 차이가 동일하다면 정사각형으로 판단하도록 했다. 이 코드는 틀렸다. [ 해설 ] 그렇다면 아래와 같이 정사각형이 기울어 있는 경우까지 찾을 수 있어야 한다. 1. 그래도 딱히 어려울건 없는데, 그냥 4개의 점을 입력받고 나올 수 있는 모든 경우의 길이를 구해본다. 4개에서 2개를 순서없이 골라야하니, 4C2 = 4P2 / 2! = 4*3/2 = 6가지만 구해보면 된.. 2021. 11. 3.
백준 1195 자바 - 킥다운 (BOJ 1195 JAVA) 문제 : https://www.acmicpc.net/problem/1195 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01100/BOJ_1195.java 순전히 구현력에 따라 풀 수 있고 없고가 갈리는 문제이다. 길이가 최대 100이므로 그냥 brute force로 모든 경우를 시뮬레이션 돌려도 전혀 문제가 없다. 1. 일단 최대로 나올 수 있는 경우는 예를들어 모든 부분이 '이'로 되어 있다면 서로 겹칠 수 없으니 두 문자열의 합이 일단 최대치이다. 그 후에, 이런 모양부터 시작해서 하나하나 직접 비교해보는 것이다. 이 때 '이'와 '이'가 만나는 경우는 맞물릴 수 없는 경우이므로 무시한다. ... --(A)-- ... 이런식.. 2021. 11. 2.
백준 1111 자바 - IQ Test (BOJ 1111 JAVA) 문제 : https://www.acmicpc.net/problem/1111 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01100/BOJ_1111.java 쉽게봤더니 생각보다 예외처리할게 많았다. 그래도 이정도면 무난한 편인듯. 'A'와 'B'가 언제 발생할지만 잘 생각해보면 된다. 1. 우선 n이 2 이상일 때 첫번째 수와 두번째 수가 동일한 경우를 생각해봐야 한다. 이게 찾기 제일 어려웠다. [1 1 1 1 ...] 이런 경우이다. 처음엔 2차방정식이 안풀리니 당연히 'A'일꺼라 생각했는데, 2x-1 과 같은 경우 가능하다. 그러니 동일한게 이어진다면 동일한 값을 출력만 해주면 된다. 다만 [1 1 2 ..] 이렇게 갑자기 숫.. 2021. 11. 2.
백준 23334 자바 - Olympic Ranking (BOJ 23334 JAVA) 문제 : https://www.acmicpc.net/problem/23334 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/23300/BOJ_23334.java 브론즈 티어지만 자바 한정으로 시간초과 날 위험이 큰 문제라 남겨봅니다. 자바에 시간 어드밴티지 없이 모든 언어 동일하게 1초 제한인 문제입니다. 이 문제의 경우 일반적으로 생각할 수 있는, 입력받은걸 배열에 넣고 정렬하는 방식으로 하게 되면 시간초과가 날 확률이 있습니다. g,s,b가 최대 999이고, g,s,b 순서대로 비교가 되면 되므로 g*1000000 + s*1000 + b 로 처리를 하게되면 최대 10억-1 이므로 int형으로 한방에 표현 가능합니다. 예를들어 g.. 2021. 11. 2.
백준 22728 자바 - Amida, the City of Miracle (BOJ 22728 JAVA) 문제 : https://www.acmicpc.net/problem/22728 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/22700/BOJ_22728.java 일본어로 된 문제라 번역기 돌려야 한다는 점을 빼면 그냥 문제에 제시된 대로 구현만 하면 된다. 내 경우엔 arr[a][b] = c를 a높이에서 b번 수직선에서 c번 수직선으로 넘어갈 수 있다로 정의했다. 따라서 h, p, q를 입력받을 시 arr[h][p] = q, arr[h][q] = p가 된다. 그리고 높이 1001(가로선이 높이 1000부터 있을 수 있으므로)부터 높이를 1씩 감소시키면서 해당 높이에서 이동할 가로선이 있으면 무조건 이동하는 방식으로 짰다. 최종적으로.. 2021. 10. 30.
스프링부트 Spring Security 기본 세팅 (스프링 시큐리티) [ 2023-02-10 추가 ] 스프링부트 3.0 이상에 적용하실 경우 '스프링부트 3.0이상 Spring Security 기본 세팅 (스프링 시큐리티)' 글을 참고해주세요. 버전 상관없이 시큐리티 기본 세팅을 익히실 경우에도 위 링크가 더 좋습니다. 목차 이하 내용은 스프링부트 2.6.2를 기준으로 작성되었으나, 스프링부트 2.7.8 까지는 이하 글에서 설명한대로 동작함을 확인했습니다. 다만, 2.7.X 대에서는 deprecated로 표시된게 있을 수 있습니다. [ 예시 프로젝트 ] 이하 글에서는 import를 빼놓고 코드를 넣어두었고, 부분부분 따로 있는 코드들이 있어서 완전 초보라면 이해하기 힘들 것 같습니다. 또는 당장 급하게 복붙할 스프링 시큐리티 코드를 찾는 경우도 있을 수 있습니다 ㅋㅋ. 이.. 2021. 10. 30.
백준 1004 자바 - 어린 왕자 (BOJ 1004 JAVA) 문제 : https://www.acmicpc.net/problem/1004 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1004.java 사실 문제에 있는 복잡한 그림을 보고 쫄지만 않으면 된다. 그냥 시작지점과 끝지점이 각 원에 포함되는지만 확인하면 된다. 1. 둘다 포함하거나, 둘다 포함안되면 지나갈 필요가 없다. 2. 둘 중 하나만 포함되면 지나가야 한다. 원의 x,y 좌표와 시작점, 끝점의 좌표에 대해 각각 거리를 구해 반지름보다 작다면 포함되니 그걸로 판단하면 된다. 2021. 10. 29.
백준 1003 자바, 파이썬, C# - 피보나치 함수 (BOJ 1003 JAVA, Python, C#) 문제 : https://www.acmicpc.net/problem/1003 코드(자바) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.java 코드(파이썬) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.py 코드 (C#) : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01000/BOJ_1003.cs Memoization 개념에 대해 익힐 수 있는 아주 좋은 문제이다. 피보나치의 경우 문제에 제시된 기본적인 방식으로 짜게 되면 재귀적으로 호출되는 함수.. 2021. 10. 29.
백준 2696 자바 - 중앙값 구하기 (BOJ 2696 JAVA) 문제 : https://www.acmicpc.net/problem/2696 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02600/BOJ_2696.java 1. 중앙값을 빨리 찾기 위한 방식을 찾아야 한다. 이렇게 중앙값을 취하는 경우 보통 절반씩 나눠서 어떠한 자료구조에 넣는 방식으로 풀면 괜찮은 경우가 많다. 2. 이 문제의 경우 힙 2개에 넣으면 괜찮게 풀 수 있다. PriorityQueue 2개를 둬보자. 하나는 맥스힙, 하나는 민힙으로 사용한다. 예를들어 1,2,3,4,5,6,7,8,9가 맥스힙에 1,2,3,4,5가 들어있고, 6,7,8,9가 민힙에 들어있다고 보자. 맥스힙에서 하나를 peek해보면 가장 큰 수인 '5'가.. 2021. 10. 29.