www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 이 문제는 2667번 단지번호 붙이기 문제와 비슷하다고 생각했다. 2차원배열을 만들어주는 방식만 다르고 탐색하고 덩어리갯수와 덩어리 크기를 구하는 문제였기 때문이다. 좌표를 입력받으면 이차원배열 채우기가 애매하다고 생각이 들 수 있는데 영역을 거꾸로 돌린채로 풀어도 된다. 그래서 풀어봤는데 틀렸습니다가 떴당.. m,n,k = map(int,input().split()) graph = [[0]..

www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 처음에 이 문제를 봤을 때 트리구조를 생각했다. 트리구조로 푸려고 하니 도저히 아이디어가 안떠올랐다. 찾아보니 이 문제는 시작지점부터 목표지점까지 몇번 거쳐야하는지 생각하는 단순 탐색 문제였다. bfs로 입력받은 값 기준으로 시작해서 연결되어있는 곳을 찾아 +1씩 더해나가면 문제를 풀 수 있다. 이 문제에서는 인접리스트를 적용하여 풀었다. from collections import deque im..

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 보아하니 2667번 단지번호붙이기할 때 참고했던 음료수 얼려먹기문제(DFS)와 유사했다. 2667번 문제풀이링크를 참고하겠다.

12813번: 이진수 연산 총 100,000 비트로 이루어진 이진수 A와 B가 주어진다. 이때, A & B, A | B, A ^ B, ~A, ~B를 한 값을 출력하는 프로그램을 작성하시오. www.acmicpc.net 이문제는 비트마스크 문제이다. 기본적인 비트연산자를 이용한 문제인데 not 연산자를 파악하는 데 시간이 걸렸다. 일반적인 not 연산자(~)를 쓰면 결과가 0b0100 -> -0b0101 이런식으로 나와서 not연산자를 사용하지 못했다. 그래서 1의 보수쓰는 법으로 풀었다. ~a를 구하기 위해서 (a가 세자리라면) a^111(mask) 이렇게 xor 연산을 사용해 구하면 된다. ex) a=101 101^111=010 mask값을 구하기 위해서는 이진수가 길이를 알아야하는데 문제에서 1000..

11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 이 문제는 비트마스크를 이용한 문제라고 하는데 어디에 어떻게 적용해야할지 감이 안잡혀서 생각나는대로 풀어봤다. 비트마스크 문제들도 여러개 접해보자. 풀이1 - 시간초과 이렇게 푸니까 시간초과가 나왔다 m = int(input()) S=set() #집합자료형 for _ in range(m): tmp = input().split() if len(tmp)==1: if tmp[0]=='all': s=set([i for i in range(1,21)]) else: s=set() continue a,b=tmp..

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 나는 코딩테스트 이론 공부를 '이것이 취업을 위한 코딩테스트다' 라는 책으로 하고 있다. 이 2667번 문제는 DFS/BFS 챕터에 있던 음료수 얼려먹기문제(DFS)와 유사했다. (검색하면 나옴) (음료수얼려먹기 문제 답) n=int(input()) graph=[] for i in range(n): graph.append(list(map(int,input()))) def dfs(x,y): #주어진 범위를 벗어나는 경우에 즉시 종료 if x = n or y = n:..