본문 바로가기

공부55

[백준] 1920번 수 찾기 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/1920 쉬운 이분 탐색 문제였다. [문제] N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. [입력] 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다. [출력] M개의 줄에 답을 출력한다. 존재하면 1을, 존재하.. 2023. 2. 14.
이진 탐색 - 정렬된 배열에서 특정 수의 개수 구하기 [문제] N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1,1,2,2,2,2,3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다. [입력] 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다. (1 2023. 2. 14.
이진 탐색 - 떡볶이 떡 만들기 이 문제는 백준 나무 자르기 문제와 동일한 문제로 아래 링크에서 채점이 가능합니다. https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net [문제] 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다... 2023. 2. 14.
이진 탐색 이론 bisect이진 탐색이란, 기존의 하나하나 검사하는 탐색 방법보다 더 빠른 탐색 알고리즘이다. 원래대로라면 길이가 N인 배열에서 어떠한 원소를 찾고자 한다면, 처음부터 N개의 원소를 하나하나 검사해보는 방식으로 탐색을 한다. 따라서 기존의 탐색 시간복잡도는 O(N)이다. 하지만 배열이 정렬되어 있다는 가정 하에 이진 탐색은 더 빠른 시간복잡도를 보장한다. 이진탐색이란? 이진탐색이란 정렬되어있는 배열에서 특정 값을 찾는 방법이다. 찾고자 하는 값을 target이라고 할 때, 배열의 중간 위치의 값이 target보다 작은지 큰지를 검사한다. 배열을 반으로 나눈 후 중간 위치의 값이 target보다 작다면 뒤의 배열에서 같은 방식으로 탐색을 반복하고, 크다면 앞의 배열에서 같은 방식으로 탐색을 반복한다. 길이.. 2023. 2. 13.
정렬 이론 이것이 코딩테스트다에 있는 정렬은 다음과 같다. 선택정렬 삽입정렬 퀵정렬 계수정렬 1. 선택정렬 선택정렬은 가장 작은 값을 선택해 앞으로 보내는 과정을 반복하여 배열을 정렬해준다. 예를 들어 [3, 2, 5, 1, 4]라는 배열이 있다면, 이 배열에서 가장 작은 값인 1을 맨 앞의 3이랑 위치를 바꿔준다. [1, 2, 5, 3, 4]에서는 이미 정렬된 1을 제외한 [2, 5, 3, 4] 중 가장 작은 데이터인 2를 맨 앞으로 보낸다. (2가 이미 맨 앞의 숫자라 달라진 점은 없다.) 그 다음엔 [1, 2, 5, 3, 4]에서 이미 정렬된 1, 2를 제외한 [5, 3, 4] 중 가장 작은 데이터인 3을 맨 앞의 5랑 바꾼다. [1, 2, 3, 5, 4]에서 같은 방식으로 남은 5, 4의 위치를 바꿔주면 완.. 2023. 2. 13.
[백준] 1707번 이분 그래프 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/1707 이분 그래프의 개념만 익힌다면 수월하게 구상, 구현할 수 있다. [문제] 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph)라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. [입력] 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을빈칸을 사이에 두고 순서대로 .. 2023. 2. 1.
[백준] 2206번 벽 부수고 이동하기 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/2206 구상이 상당히 힘들었다. 시간을 꽤나 사용한 것 같다. 난이도가 꽤 있었던 bfs문제이다. [문제] N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다. 한 .. 2023. 2. 1.
[백준] 7576번 토마토 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/7576 예전에 풀었을 땐 꽤나 어려웠던 것 같다. 다시 풀어보니 난이도 적당한 bfs문제였다. [문제] 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는.. 2023. 1. 31.
[백준] 2606번 바이러스 (Python) 정답 코드 및 풀이는 맨 아래에 있습니다. https://www.acmicpc.net/problem/2606 난이도 낮은 개념 공부용 문제이다. [문제] 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 .. 2023. 1. 30.

티스토리툴바