분류 전체보기
-
[백준]1042: 거짓말 - JAVA문제풀이/백준 2021. 7. 5. 15:23
[백준]1042: 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 🪑 문제를 따라 조건들을 차례차례 정리해 보았다. 지민 -> 진실 OR 과장(되도록 과장 BUT 거짓말 들키기 싫어함) 진실 아는 사람 존재 -> 과장 할 수 없음. 진실을 한 번 이라도 들은 사람은 진실을 아는 사람이다. 🔧 위의 조건들을 토대로 어떻게 풀지 풀이 순서를 적어보았다. 진실을 아는 사람들의 정보를 모은다. 진실을 아는 사람이 속해있는 파티를 조사하여 해당 파티원..
-
[프로그래머스]로또의 최고 순위와 최저 순위 - JAVA문제풀이/프로그래머스 2021. 7. 4. 14:55
[프로그래머스]로또의 최고 순위와 최저 순위 코딩테스트 연습 - 로또의 최고 순위와 최저 순위 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호 programmers.co.kr 풀이 🪑 구현, 시뮬레이션 유형의 문제이다. 🔧 로또 번호가 맞는지 확인해 주기 위해 반복문을 2중으로 사용하여 확인해 주었다. 확인하면서 '0'으로 표시된 부분의 개수도 함께 count해 주었다. 🔧 최고 순위는 최대로 로또 번호를 맞췄을때 이므로 현재 맞는 로또 번호의 개수 + '0'의 개수로 계산해 주었다. 🔧 순위를 지정하는 부분은 배열을 사용하였다. 인덱스를 로또..
-
[백준]14890: 경사로 - JAVA문제풀이/백준 2021. 7. 3. 15:00
[백준]14890: 경사로 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 🪑 조건에 따라 문제를 잘 읽고 풀어야 하는 구현 문제였다. 확인해 주어야 할 방향은 총 2가지 방향이므로 (열, 행) 열을 확인하는 함수, 행을 확인하는 함수 두개로 나누어 풀어주었다. 🔎 확인할때는 한 방향으로 확인하며 현재 계단의 높이와 다음 계단의 높이차를 확인해 주었다. 계단의 높이차가 1을 초과하면 문제의 조건에 나와있는 "계단의 높이차는 1이어야 한다"를 만족하지 못하므로 바로 false를 반환하도록 하였다. 계단의 높이차가 1이더라도 다음 ..
-
[백준]10711: 모래성 - JAVA문제풀이/백준 2021. 7. 2. 15:56
[백준]10711: 모래성 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 풀이 이 문제는! 직관적인 방법으로 생각해서 풀면 시간초과가 발생하는 문제이다. 우선, 대부분 첫번째로 떠오른 풀이 방법은 다음과 같을 것이다. 모든 노드의 탐색을 반복하며 모래성이 있는 노드 주변의 8방향 노드값을 확인하여 무너지는지, 무너지지 않는지 확인한다. 위의 방법으로 푼다면 테스트 코드는 통과되겠지만 시간 복잡도 측면에서 효율적이지 못하다. 매번 모든 노드를 탐색하는 방법 보다 더 효율적인 탐색 방..
-
[백준]16947: 서울 지하철 2호선 - JAVA문제풀이/백준 2021. 6. 23. 11:40
[백준]16947: 서울 지하철 2호선 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 풀이 그래프의 탐색과 관련된 문제였다. 탐색 관련한 알고리즘을 활용하여 문제를 풀었다. 🤗 우선 풀이 과정을 다음과 같은 순서로 나눠 구현해 주었다. 싸이클이 발생하는 구간을 체크해준다. 탐색을 통해 모든 노드에서 싸이클이 발생하는 노드까지의 거리를 계산해 준다. 하나씩 차근차근 살펴보장. 🔹 싸이클이 발생하는 구간을 체크해준다. 싸이클은 언제 발생할까? 🤔 👉 그래프의 특성을 알고 있다면 쉽게 생..
-
[백준]3980: 선발 명단 - JAVA문제풀이/백준 2021. 6. 18. 11:20
[백준]3980: 선발 명단 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 풀이 모든 포지션으로 선수를 채웠을때, 능력치의 최댓값을 출력하는 문제로 백트랙킹 유형을 활용하여 문제를 풀었다. 헤당 선수를 뽑았는지 아직 뽑지 않았는지 확인해기 위해 visited 배열을 구현해 주었고, 선수를 뽑을 때마다 능력치의 합을 누적시켜 주었다. 선수를 뽑을때 문제의 조건에 따라 능력치가 0인 선수는 뽑지 않도록 한다. 모든 선수에게 포지션을 지정하는데 성공했다면 pos값이 11이 되었을 것이고, 이때 max값을 현재 total값과 비교하여 지정한 다음 되돌아가 다..
-
[백준]17836: 공주님을 구해라! - JAVA문제풀이/백준 2021. 6. 15. 13:22
[백준]17836: 공주님을 구해라! 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 풀이 탐색을 하면서 최단 경로를 찾되, 그람의 유무에 따라 경로가 달라질 수 있으므로 그람의 유무에 나눠 탐색을 진행하면 되는 문제이다. 최단 시간을 요구하므로 BFS탐색을 활용하였다. 이 문제에서 경로를 탐색할 때 필요한 값은 다음과 같다. X좌표, Y좌표, 현재 탐색 깊이, 그람의 유무 해당 정보들을 클래스로 만들어 주었다. 탐색을 하는 중에는, 그람의 유무에 따라 작업을 나눠주었다. 🔹 그람이 없을때 이동..
-
[백준]1477: 휴게소 세우기 - JAVA문제풀이/백준 2021. 6. 14. 17:29
[백준]1477: 휴게소 세우기 풀이 딱 보자마자 이분탐색을 통해 풀어야 겠다는 생각이 들지 않았어서 풀이하는데 시간이 좀 걸렸다. 이분탐색 유형에 아직 익숙하지 않아서 그런 것 같다. 이 문제는 휴게소의 간격을 기준으로 이분탐색을 진행한 다음 해당 간격이 형성되도록 M개의 휴게소를 생성할 수 있을 때의 최소값을 찾는 문제이다. 예제 입력1을 예시로 살펴보자. 휴게소가 설치될 수 있는구간은 다음과 같다. 1 ~ 81 83 ~ 200 202 ~ 410 412 ~ 554 556 ~ 621 623 ~ 754 756 ~ 799 휴게소의 위치와 0, L을 포함한 값을 배열에 담아 정렬시켜준다. (범위 값 계산을 하기 위해) 이때, 휴게소 간격의 최소값은 0, 최대값은 L이 된다. 이제 이분 탐색을 시작한다. 탐색..