본문 바로가기

728x90

boj12

[BOJ] 2230번 - 수 고르기 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램 → 차이를 비교할 두 수가 같은 수일 수도 있고 조건을 만족하는 최솟값을 구해야 한다. 두 수의 차이를 구해야하는데 입력된 수열이 정렬되어 있지 않으면 모든 원소끼리 비교해야 한다. 예를 들어 5개의 원소가 있으면 하나의 원소와 나머지 4개의 원소를 모두 비교해보아야 한다. 총 반복되는 횟수는 4 X 3 X 2 X 1 = 24 이다. 하지만 이 문제에서 수열의 길이는 최대 100,000까지 가능하기에 시간초과가 뜬다. 그렇다면 시간을 줄이기 위해 원소를 비교하는 반복 횟수를 줄여야한다. 먼저, 수열을 정렬한다. 그러면 아래의 그림과 같이 두 수의 차이가 어떻게 변화할지 .. 2024. 3. 22.

[BOJ] 13023번 - ABCDE (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다. - A는 B와 친구다. - B는 C와 친구다. - C는 D와 친구다. - D는 E와 친구다. 우선 여기서 알 수 있는 것은 N명 중 5명이 이와 같은 관계를 가지고 있으면 된다. 이러한 친구 관계를 구하기 위해서는 깊이 우선 탐색을 하여 구할 수 있다. 그래프의 깊이가 5이상일 경우 위와 같은 관계가 존재한다는 것을 알 수 있다. 단, 이는 판별만 하면 되기 때문에 관계를 발견하면 모든 탐색을 멈출 수 있도록 했다. 🍀 풀이 🍀 package Baekjoon; import java.io.*; import java.util.*; public class DFS13023 { sta.. 2024. 3. 1.

[BOJ] 2477번 - 참외밭 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 참외밭은 ㄱ자 모양이거나 ㄱ자를 90도, 180도, 270도 회전한 모양(┏, ┗, ┛ 모양)의 육각형 밭의 경계(육각형의 변)는 모두 동서 방향이거나 남북 방향 → 밭의 모양은 항상 그림과 같은 육각형이다.(회전할 수 있다.) 그러므로 밭의 넓이는 [전체적인 사각형의 넓이 - 빠져야할 작은 사각형의 넓이] 이다. 우리는 가장 긴 가로의 길이와 세로의 길이, 빼야할 가로의 길이와 세로의 길이를 구해야한다. 1. 가장 긴 가로와 세로 구하기 입력받을 때 동쪽은 1, 서쪽은 2, 남쪽은 3, 북쪽은 4 이므로 1, 2일 경우 가로 확인, 3,4일 경우 세로 확인 2. 빼야할 가로와 세로 구하기 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 입력을 받는다... 2024. 2. 19.

[BOJ] 31066번 - 비 오는 날 (Java) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 2023.12.30일에 처음으로 SciOI 2023 Open Contest · Arena #16 에 참가했다. 코딩테스트를 본다는 생각으로 긴장감을 가지고 시작했다. 이 문제가 첫 문제였다. 당시에 너무 복잡하게 생각했는지 꼬여버렸던 문제를 오늘 다시 정리해서 풀어보았다. 풀이 과정에서 2가지 문제를 알게되어 이를 정리하려고 한다. 1. 틀린 예외처리 if(m == 1 && k == 1) return -1; 처음에는 위와 같이 우산이 1개이고 우산을 쓸 수 있는 사람 수가 1명일 경우에는 무조건 불가능하다고 했다. 하지만 만약에 사람이 건너야 하는 사람이 1명이면 이 경우에도 불가능할까? 내가 생각하지 못했던 부분 첫번째였다. 사람이 1명일 경우에는 1회로 가능하다는 것을.. 2024. 1. 2.

[BOJ] 2437번 - 저울 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 우선 예시 중에서 추 [1, 1, 2]만 가지고 있다고 생각해보자. 그러면 측정할 수 있는 무게는 위의 그림과 같다. 다른 예시로 [1, 2, 3]으로 생각해보면, 1 = 1 2 = 2 3 = 3 4 = 1+3 5 = 2+3 6 = 1+2+3 위와 같이 측정할 수 있다. 즉, 가지고 있는 추들의 무게를 합한 값 이하의 값들은 측정할 수 있다는 것을 알 수 있다. 단, 추의 무게들이 정렬이 되어있어야 하며 추와 추 사이의 무게 차이가 크게 나면 안된다. 여기서 추 사이의 무게 차이가 얼마만큼 차이가 나면 안되는지를 생각해봐야한다. 문제에서 주어진 예시로 현재 [1, 1, 2, 3]의 추를 가지고 있어 7까지 측정할 수 있다고 하자. 다음 추가 현재 측정할 수 없는 8보다 작.. 2023. 10. 27.

[BOJ] 15657번 - N과M(8) (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 백트래킹 연습하기 편한 문제라고 생각한다. 오늘 풀면서 틀렸던 이유에 대해 간단하게 남겨놓으려고 한다. 내가 잘못 생각했던 부분은 타입을 생각하지 않고 정렬한 것이다. 처음에는 결과를 쉽게 저장하기 위해 문자형 그대로 사용하여 주어진 예제는 전부 통과해 제출했지만 틀렸다. 다른 동작의 오류가 있나 고민해보았지만 없었고 다른 사람의 풀이를 참고해봐도 동작은 완벽했다. 단 하나 다른 점이 입력받은 데이터 타입이었는데 생각해보니 [입력으로 주어지는 수는 10,000보다 작거나 같은 자연수]이므로 이는 정수로 정렬해야 올바르게 정렬된다는 것을 깨달았다. 🍀 풀이 🍀 import sys n, m = map(int, sys.stdin.readline().split()) nums = .. 2023. 10. 5.

[BOJ] 1911번 - 흙길 보수하기 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 이 문제는 [물웅덩이들을 모두 덮으려고 한다.] 라는 조건이 있으므로 물웅덩이가 보이면 일단 덮으면 된다. 그러나 널빤지의 길이는 정해져 있으므로 덮다보면 입력받은 물웅덩이의 위치가 이미 덮여져 있을 수 있다. 어차피 모든 웅덩이는 덮어야하니 웅덩이의 [끝 위치 - 시작 위치]를 통해 웅덩이의 길이를 구하여 필요한 널빤지의 개수를 구했다. 단, 위에서 설명했듯이 이미 덮여져 있는 위치가 존재할 수 있으므로 이에 대한 처리로 current라는 변수를 두어 시작 위치를 덮여져 있지 않은 위치로 변경할 수 있도록 했다. 🍀 풀이 🍀 import sys n, l = map(int, sys.stdin.readline().split()) water = [list(map(int, sy.. 2023. 9. 7.

[BOJ] 13549번 - 숨바꼭질3 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 어제 공부한 다익스트라 알고리즘을 연습해보았다. 다익스트라 알고리즘과 BFS 2가지 방식으로 풀어보았다. (코드는 아래에) 1. 다익스트라 알고리즘을 이용한 풀이 1. 수빈이의 위치를 시작 정점으로 둔다. 2. 현재 위치 i에 +1, -1 *2 한 위치에 대해 저장되어 있는 시간 times[k]와 도달한 시간(times[i] + 1 또는 times[i])을 비교하여 도달한 시간이 더 작으면 times[k]를 갱신한다. 3. heap이 빌 때까지 2번 과정을 반복한다. 이때, 주의할 점은 가중치가 없지만 가중치로 생각한 값은 도달한 시간으로 times의 값이다. 만약 이를 times를 도착 정점의 개수만큼만 만들면 올바른 값을 도출하지 못할 것이다. 위의 문제에서 주어진 예.. 2023. 9. 5.

[BOJ] 1753번 - 최단경로(Python) + Dijkstra Algorithm 🗒️ 다익스트라 알고리즘 (Dijkstra Algorithm) 모서리 또는 정점에 가중치가 부여된 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘 가중치가 없는 그래프에서의 최단경로는 BFS를 사용! 어떤 시작점 s가 주어졌을 때, 그 정점에서 시작하여 다른 모든 정점으로 가는 최단 경로를 찾는다. 단, 음수인 가중치가 없는 경우에만 쓸 수 있다. 실제 최단 경로는 우리집에서 옆집으로 이동하는 것이지만, 우리집에서 은행을 거쳐 가는 것이 비용상 이득이 되는 경우가 발생한다. 즉, 값이 음수인 모서리가 있으면 경로를 만들어가는 도중에 아주 작은 음수 값을 가지는 모서리가 있어서 이미 트리에 들어있는 최단 경로와 전혀 다른 경로를 만들어야 할 수 있다. 동작 과정(간선 완화 과정) 1. 모든 꼭짓점을 .. 2023. 9. 4.

[TIL] 1377번 - 버블 정렬 1. 1377번 - 버블 정렬 import sys N = int(sys.stdin.readline()) array = [[int(sys.stdin.readline()), i] for i in range(N)] array.sort() max = -sys.maxsize for i in range(N) : t = array[i][1] - i if max < t : max = t print(max+1) 이 문제는 버블 정렬시 완료되는 반복 횟수를 구하는 문제이다. 주어진 c++ 코드로도 답은 구할 수 있지만 시간초과가 발생했다. 즉, 이중 반복문을 제거할 수 있어야 한다. 위의 그림은 버블 정렬 과정을 써본 것이다. 버블 정렬은 맨 뒤에서 부터 큰 값이 먼저 정렬된다. 그러므로 정렬되지 않은 값 중 가장 큰 값.. 2023. 6. 7.

[BOJ] 6064번 - 카잉 달력(JAVA) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 중국인의 나머지 정리 참고 블로그 https://blog.joonas.io/23 중국인의 나머지 정리 - 이해하기 쉬운 설명 중국인의 나머지 정리(CRT; Chinese Remainder Theorem)연립 합동식의 유일한 해를 찾는 정리이다. 예를 들면서 설명과 함께 전개하는 게 가장 이해하기 쉽다. 개념 이해를 위해 연립 합동식이 2개일 때 blog.joonas.io 나머지 연산을 사용해보려고 했지만 어려워서 구현 실패 그래서 문제 풀이 블로그를 참고했는데 여기서 내가 이해한 부분을 정리하기 위해 글을 작성 문제풀이 참고 블로그 https://girawhale.tistory.com/10 [백준] 6064번: 카잉 달력 - JAVA 문제 링크 BOJ 6064번: 카잉 .. 2023. 3. 27.

[BOJ] 2667번 - 단지번호붙이기(JAVA) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 시작 정점 찾기 이미지 상으로 확인했을 때 왼쪽 위 > 오른쪽 위 > 왼쪽 아래 > 오른쪽 아래 와 같이 Z 모양으로 시작 정점을 찾는다. 현재 위치의 값이 1이면서 방문하지 않으면 시작 정점이다. 시작 정점을 기준으로 그래프 탐색 BFS 그래프 탐색 사용 대각선을 제외한 상하좌우 위치에 아파트가 있으면 현재 단지에 있는 아파트 수 증가 BFS 탐색이 끝나면 탐색한 아파트 수 반환 탐색이 끝나고 아직 남은 정점이 있으면 ①,②번 과정 반복 모든 정점의 탐색이 끝나면 올바른 형식으로 출력 후 프로그램 종료 ★ 아파트 단지내에 있는 아파트 수를 저장하는 배열(aparts[]) 초기화 ★ 🍀 풀이 코드 🍀 import java.io.BufferedReader; import ja.. 2023. 3. 23.

이전 1 다음

728x90

티스토리툴바