백준 write-up (91) 썸네일형 리스트형 [백준] Yangjojang of The Year : 11557번 - Python https://www.acmicpc.net/problem/11557 11557번: Yangjojang of The Year 입학 OT때 누구보다도 남다르게 놀았던 당신은 자연스럽게 1학년 과대를 역임하게 되었다. 타교와의 조인트 엠티를 기획하려는 당신은 근처에 있는 학교 중 어느 학교가 술을 가장 많이 먹는지 www.acmicpc.net 문제를 풀면서 몰랐던 개념 - 이중 반복문 안에서 입력 받은 값들을 각기 다른 리스트에 저장하는 방법 : 빈 리스트를 선언할 때 항상 전역 변수로만 선언했었는데, 첫 번째 반복문의 횟수만큼 두 번째 반복문이 돌아갈 때마다 리스트를 생성하려면 for 문 내에 선언해야 한다는 것을 알게 되었다. for _ in range(T): arr = []# 이거!!! N = int(i.. [백준] 방탈출 : 15729번 - Python https://www.acmicpc.net/problem/15729 15729번: 방탈출 첫째 줄에 N(1 ≤ N ≤ 1,000,000)가 주어지고 둘째 줄에는 쪽지에 적혀 있는 N자리의 수가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제를 풀면서 몰랐던 개념 (1) [Python] 일정구간 리스트 값을 한 번에 바꾸고 싶을 때 : 원소 하나만 바꿀 때는 해당 인덱스를 지정해서 바꾸면 되지만 구간을 정해서 여러 개를 한 번에 바꾸려고 할 때는 인덱스 슬라이싱을 이용하고 바꾸려고 하는 값 역시 해당 구간만큼(리스트 형식) 가지고 있어야 한다. A = [0, 0, 0, 0, 0] B = [1, 1, 1] # 리스트 A에서 0번째에서 2번째까지 리스트 B의 값으로 바꾸고 싶을 때 A[0:2.. [백준] N과 M(1) : 15649번 - Python https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제를 풀면서 몰랐던 개념 백트래킹에 대한 개념 -> https://ye5ni.tistory.com/110 참고! 문제의 접근 방법 1. 아이디어 - 백트래킹 재귀함수 안에서, for문을 돌면서 1부터 N중에서 숫자를 하나 선택 - 다음 1부터 N까지 선택할 때, 이미 선택한 값이 아닌 경우 선택(방문여부 체크) - 재귀함수에서 M개를 선택할 경우 출력 2. 시간복잡도 - N^N : 중복이 가능.. [백준] 바닥 장식 : 1388번 - Python https://www.acmicpc.net/problem/1388 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net 문제를 풀면서 몰랐던 개념 DFS 알고리즘에 대한 개념 -> https://ye5ni.tistory.com/108 참고! 문제의 접근 방법 👀 '-' 모양의 나무 판자와 '|' 모양의 나무 판자를 나누어서 계산하기 👀 '-' 모양은 좌우(가로) 노드의 값을 비교하고 '|' 모양은 상하(세로) 노드의 값을 비교하기 👀 특정 조건을 만족해야 하는 탐색 기법의 경우에는 DFS를 사용하는 것이 유리함! 내가 막.. [백준] 로봇 청소기 : 14503번 - Python https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제를 풀면서 몰랐던 개념 - while, for문에서 break 잘 걸어주기 - 음수 번째 인덱스를 표현하는 방법 문제의 접근 방법 1. 아이디어 while 문으로 계속 작동하도록 함 -> 특정 조건을 맞춘다면 종료! 4방향 for 문으로 탐색 먼저 수행 -> 빈칸이 있을 경우 이동 4방향 탐색이 안될 경우 -> 뒤로 한 칸 가서 반복 뒤로도 못간다면 -> while 문에서 빠져나오기 2. 시.. [백준] 단지번호붙이기 : 2667번 - Python https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제를 풀면서 몰랐던 개념 DFS 알고리즘에 대한 개념 ->https://ye5ni.tistory.com/108 참고! 문제의 접근 방법 1. 아이디어 - 2중 for문, 값 1 && 방문 X => DFS - DFS를 통해 찾은 값을 저장 후 정렬해서 출력하기 2. 시간복잡도 - DFS : O(V+E) - V, E : N^2, 4N^2 - V+E = 5N^2 ~= N2 ~= 625 >> 가능함 3... [백준] 그림 : 1926번 - Python https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 문제를 풀면서 몰랐던 개념 BFS 알고리즘에 대한 개념 -> https://ye5ni.tistory.com/105 참고! 문제의 접근 방법 1. 아이디어 - 2중 for => 값 1 && 방문 X => BFS - BFS 돌면서 그림 개수 +1, 최댓값을 갱신 2. 시간복잡도 - BFS : O(V+E) = V + 4V = 5V = 5(m*n) - V : m * n = 500 * 500 (m, n이 최대 .. [백준] 거스름돈 : 14916번 - Python https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제를 풀면서 몰랐던 개념 - 어떤 계산의 몫이 3이라고 하자. 그 몫에서 1을 빼주어서 2로 만들어주고 싶을 때는 나머지에 나누는 수를 더해주면 됨. ex) n // 5 = 3 3 -> 2 로 취급해서 계산을 하고 싶다면, (n % 5)에 + 5 를 해주기! 문제의 접근 방법 - 거스름돈이 1과 3일 경우에는 5와 2 모두로 나누어 떨어질 수 없기 때문에 계산 불가하다. 따라서 -1을 출력해주어야 함. - 거스름돈이 5로 나누었을 때의 나머지가 짝수이면, 2로 나눌 수 있다는 것이므로 5로 먼저 나눠준 후(최대 횟.. 이전 1 2 3 4 5 6 ··· 12 다음