코딩하는 eroke

문제

M,N,K (행, 열, 직사각형 개수)를 입력받고

K개의 직사각형 왼쪽 아래 좌표와 오른쪽 위 좌표를 입력받아 색칠한다.

<그림1> 같이 색칠이 끝나면 <그림2>처럼 직사각형 외부에 분리된 영역들이 생기는데

이 영역들의 넓이를 각각 구하고 영역의 개수를 첫째 줄에 출력,

영역의 넓이를 오름차순으로 각각 출력해주면 되는 문제이다.

풀이 (python, BFS)

from collections import deque

dx=[1,-1,0,0]
dy=[0,0,1,-1]

m,n,k = map(int,input().split())
sq=[[0]*(n) for _ in range(m)] #n*m 맵

#직사각형 좌표 입력 및 색칠
for tc in range(k):
    a,b,c,d = map(int,input().split()) #0 2 4 4
    for x in range(b,d): #2~4
        for y in range(a,c): #0~4
            sq[x][y]=1

#BFS
dq=deque()
answer=[]
for i in range(m):
    for j in range(n):
        if sq[i][j]==0:
            dq.append((i,j))
            cnt=0
            while dq:
                cx,cy=dq.popleft()
                for i in range(4):
                    nx=cx+dx[i]
                    ny=cy+dy[i]
                    if 0<=nx<m and 0<=ny<n and sq[nx][ny]==0:
                        cnt+=1
                        sq[nx][ny]=2 #visit
                        dq.append((nx,ny))
            if cnt==0: answer.append(1)
            else: answer.append(cnt)

answer.sort()
print(len(answer))
for a in answer:
    print(a,end=' ')

좌표를 입력받고 색칠한 뒤 (1로 표기)

맵에서 0인 영역이 존재하면 해당위치를 큐에 넣고 BFS를 돌려서 풀었다.

백준의 단지번호 붙이기와 매우 유사한 문제였다.

사실 오늘 냅색 알고리즘을 복습했는데 머리 빠개지는줄 알았다..

흑흑스 갈길이 넘멀다

파이팅..

문제

입력 : n=수빈시작위치, k=동생위치(도착지점)

출력 : 수빈이가 걷거나 순간이동한 횟수 

예를들어 n=5, k=17 일떼, 수빈이가 5-10-9-18-17 순으로 가면 4번 만에 동생을 찾을 수 있다.

풀이

from collections import deque

MAX=10**5
dp=[0]*(MAX+1)
dq = deque()

n,k = map(int,input().split())
dq.append(n)
while dq:
    c=dq.popleft() #current
    if c==k:
        print(dp[k])
        break

    for nc in (c-1,c+1,c*2):
        if 0<=nc<=MAX and dp[nc]==0:
            dp[nc]=dp[c]+1
            dq.append(nc)

큐에 현재 위치 c와 다음 위치 c-1, c+1, c*2를 넣으며 횟수를 추가했다.

문제

입력 : n = 동전의 가치, k = 만들어야 할 가치

출력 : 사용한 동전의 개수

동전 종류는 k가치보다 큰 경우가 있을 수 있다.

입력받은 동전 종류는 오름차순 정렬이 된채로 입력이 되기 때문에

동전배열 맨 뒤에서부터 가치 계산을 하도록 접근했다.

풀이

n,k = map(int,input().split())
coin=[0]*n

for i in range(n):
    coin[i]=int(input())

cnt=tmp=0
for i in range(n-1,-1,-1):
    if k>=coin[i] :
        tmp=k//coin[i]
        k-=(tmp*coin[i])
        if tmp==0: cnt+=1
        else: cnt+=tmp

print(cnt)

처음엔 그냥 for문 안에 while을 넣었다가 시간초과가 났고

그 다음은 세부조건을 고려하지 않아 오류가 났다... 따흑

문제

이진탐색의 가장 기본적인 문제이다. 하지만 나는 다 까먹어서 다시 공부했다...

가지고있는 k개의 랜선을 잘라 같은 길이로 n개를 만들 수 있는 최대 길이를 출력하는 문제이다.

풀이

k, n = map(int, input().split())
lan = []

for i in range(k):
    lan.append(int(input()))

lan.sort()  # 이분탐색을 위해 정렬
s = 1
e = max(lan)

res = 0
while s <= e:
    total = 0
    mid = (s + e) // 2

    for x in lan:
        if x >= mid: total += (x // mid)

    if total < n:
        e = mid - 1
    else:
        res = mid
        s = mid + 1

print(res)

현타...ㅎㅎ 알고리즘도 종종 풀어줘야 잊지 않는거 같다...

공부할게 넘 많아~~~~

문제

방번호에 필요한 세트 수 를 출력하면 된다. 한 세트는 0~9의 숫자이고 6, 9는 서로 뒤집어 사용할 수 있다.

풀이

import collections

n=input()
d=collections.defaultdict(int)

for x in n:
    x=int(x)
    if x!=6 and x!=9: d[x]+=1
    else:
        if d[6]>d[9]:d[9]+=1
        else: d[6]+=1

res = list(d.values())
res.sort(reverse=True)
print(res[0])

default 딕셔너리를 사용해 구현하였다. 

6, 9 가 아닌 경우는 세트 값을 추가하고 6 혹은 9일 경우엔 적은 수를 더해가며 세트를 추가했다.

딕셔너리의 values 를 리스트화 시켜 정렬 후 가장 큰 값 (세트)을 출력했다.

문제

단지번호붙이기 (BOJ2667) 문제와 비슷한 문제이다.

그런데 DFS 재귀로 풀었더니 예제 코드는 정답으로 출력되지만 제출 시 런타임 에러 (RecursionError)가 발생했다.

RecursionError 관련해서는 아래 링크로 확인해보면 발생 이유와 대응 방법에 대해 나온다.

그래서 재귀방식 대신 큐를 사용해 BFS로 다시 풀었더니 이번엔 시간초과가 나왔다;; (개빡취네)

질문검색 탭을 보니 나랑 똑같은 문제로 틀린 사람이 있었다. (https://www.acmicpc.net/board/view/78364)

다행히 어느 천재님이 아래 내용으로 댓글을 달아주셨다.

BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다. 
BFS 문제에서 시간 초과나 메모리 초과가 나면 이것부터 의심해 보시면 됩니다.

소름돋게 내 코드도 큐에서 뺀 다음에 visit 처리하고 있었다...

존잘님의 방법대로 코드를 수정했더니 바로 정답처리 되었다. (감사합니다..)

풀이 (Python)

from collections import deque

dx = [1,0,-1,0]
dy = [0,1,0,-1]

if __name__ == '__main__':
    t = int(input())

    for _ in range(t):
        dq = deque()
        m,n,k = map(int, input().split())
        v = [[0]*n for _ in range(m)]
        arr = [[0]*n for _ in range(m)]
        cnt=0

        for _ in range(k):
            a,b = map(int,input().split())
            arr[a][b]=1

        for i in range(m):
            for j in range(n):
                if v[i][j]==0 and arr[i][j]==1:
                    cnt+=1
                    dq.append([i,j])
                    v[i][j]=1
                    while dq:
                        cx, cy = dq.popleft()
                        #v[cx][cy] = 1 <<문제의 기존 visit 처리
                        for k in range(4):
                            nx = cx + dx[k]
                            ny = cy + dy[k]
                            if (0 <= nx < m and 0 <= ny < n and v[nx][ny] == 0 and arr[nx][ny] == 1):
                                dq.append([nx,ny])
                                v[nx][ny]=1
        print(cnt)

문제

유명한  dfs 문제이다. (그림 출처 : 백준사이트)

n을 입력받은 뒤 첫 번째 그림처럼 n*n 배열이 주어지는데

1이 상하좌우로 이어지는 영역을 하나의 단지로 구분한다.

한 단지 영역내의 1들은 각 단지의 집의 개수이다.

두번재 그림을 보면 3단지가 있고 각각 집의 개수는 7,8,9개씩 이다.

단지의 개수와 집의 개수를 오름차순으로 정렬해 출력하면 되는 문제이다.

예전에 C++로 풀었던 문제여서 이번엔 파이썬으로 풀어봤는데

계속 이맞왜틀 ㅡㅡ 상태였는데 집개수가 0인 경우를 출력을 안했었다는걸 알게됨;

풀이1 (python)

dx = [1,0,-1,0]
dy = [0,1,0,-1]

cnt=0
def dfs(x,y):
    global cnt
    v[x][y]=1
    cnt+=1 #집 count
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if(0<=nx<n and 0<=ny<n and v[nx][ny]==0 and arr[nx][ny]==1):
            dfs(nx,ny)

if __name__ == '__main__':
    n = int(input())
    v = [[0]*n for _ in range(n)]
    arr = []
    dan = [] #단지수

    for _ in range(n):
        arr.append(list(map(int,input())))

    for i in range(n):
        for j in range(n):
            if arr[i][j]==1 and v[i][j]==0:
                dfs(i,j)
                dan.append(cnt)
                cnt=0

    dan.sort()
    print(len(dan)) #단지 수
    if len(dan)==0:print(0)
    for d in dan:print(d) #집 수

풀이2 (C++)

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N, M, A[25][25], visit[25][25],ny,nx;
int dan_cnt =1, cnt = 1;
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };

vector<int>dan;
vector<pair<int, int>>pos;
queue<pair<int, int>>q;

void BFS(int y, int x, int dan_cnt) {
	q.push({ y,x });
	visit[y][x] = dan_cnt;
	cnt = 1;
	while (!q.empty()) {
		int cy = q.front().first;
		int cx = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ny = cy + dy[i];
			int nx = cx + dx[i];
			if (A[ny][nx]!=1||visit[ny][nx] !=0|| ny < 0 || nx < 0 || ny >= N || nx >= N)continue;

			visit[ny][nx] = dan_cnt;
			q.push({ ny,nx });
			cnt++;
		}
	}
}

int main() {//플러드필,연결요소
	/*ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);*/
	
	//memset(visit, -1, sizeof(visit));
	
	scanf("%d", &N);
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			scanf("%1d", &A[y][x]);
			if (A[y][x] == 1)  pos.push_back({ y,x });
		}
	}

	for (int i = 0; i < pos.size(); i++) {
		int y = pos[i].first;
		int x = pos[i].second;
		if (visit[y][x] == 0) { BFS(y, x, dan_cnt++); dan.push_back(cnt); }
	}

	sort(dan.begin(),dan.end());
	printf("%d\n", dan_cnt-1);
	for (int i = 0; i < dan.size(); i++) {
		printf("%d\n", dan[i]);
	}
	return 0;
}

C++ 코드는 2년 전 코드여서인지 내가 짰는데도 낯선느낌이다..ㅎ ;;

문제

어제 풀었던 DFS와 BFS 문제와 거의 똑같은 문제이다. DFS로 단순하게 풀었다.

풀이1 (Python)

cnt = 0
def dfs(c):
    global cnt
    v[c]=1
    for i in range(1,n+1):
        if g[c][i]==1 and v[i]==0:
            cnt += 1
            dfs(i)

if __name__ == '__main__':
    n = int(input())
    pair = int(input())

    g = [[0] * (n + 1) for _ in range(n + 1)]
    v = [0] * (n + 1)

    for _ in range(pair):
        a,b = map(int,input().split())
        g[a][b] = g[b][a] = 1

    dfs(1)
    print(cnt)

풀이2 (C++)

#include <iostream>
using namespace std;
int N, link, com[101][101], visit[101], a, b,cnt;

void DFS(int n) {
	cnt++;
	visit[n] = 1;
	for (int i = 1; i <= N; i++) {
		if (com[n][i] && !visit[i])DFS(i);
	}
}

int main() {
	cin >> N;
	cin >> link;
	for (int i = 0; i < link; i++) {
		cin >> a >> b;
		com[a][b] = com[b][a] = 1;
	}
	DFS(1);
	cout << cnt - 1;
	return 0;
}

3년 전에 C++로 풀었던 문제들을 파이썬으로 다시 풀어보았다.

문제

정점의 개수(N), 간선의 개수(M), 시작정점(V)을 입력받고 간선의 수만큼 연결된 정점들의 번호를 입력받아 

시작정점부터 각각 DFS, BFS로 수행한 결과를 출력하면 된다.

DFS는 재귀함수로, BFS는 큐를 사용해 풀었다. 

풀이1 (Python)

from collections import deque

def dfs(v):
    dv[v]=1
    print(v,end=' ')
    for i in range(1, n+1):
        if dv[i]==0 and g[v][i]==1:
            dfs(i)

if __name__ == '__main__':
    n,m,v=map(int,input().split())
    g = [[0]*(n+1) for _ in range(n+1)]
    dv=[0]*(n+1) #dfs visit
    bv=[0]*(n+1) #bfs visit
    q = deque()

    for _ in range(m):
        x,y=map(int,input().split())
        g[x][y] = g[y][x] = 1  #간선연결

    #DFS
    dfs(v)
    print()
    #BFS
    q.append(v)
    bv[v] = 1
    while q:
        v = q.popleft()
        print(v, end=' ')
        for i in range(1, n + 1):
            if bv[i] == 0 and g[v][i] == 1:
                q.append(i)
                bv[i] = 1

풀이2 (C++)

//DFS와 BFS
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <memory.h>
using namespace std;

int N, M, V,V1,V2;
//stack<int>S;
queue <int> q;
int visit[1001];
int graph[1001][1001];

void dfs(int V) {
	cout << V << " ";
	for (int i = 1; i <= N; i++) {
		if (!visit[i] && graph[V][i]) {
			visit[i] = true;
			dfs(i);
		}
	}
}

void bfs(int V) {
	q.push(V);
	visit[V] = 1;
	while (!q.empty()) {
		V = q.front();
		q.pop();
		cout << V << " ";

		for(int i=1;i<=N;i++)
			if (!visit[i] && graph[V][i]) {
				visit[i] = 1;
				q.push(i);
			}
	}
}

int main() {
	cin >> N >> M >> V;
	for (int i = 0; i < M; i++) {
		cin >> V1>> V2;
		graph[V1][V2] = 1;
		graph[V2][V1] = 1;
	}

	visit[V] = 1;
	dfs(V);
	cout << endl;

	memset(visit, false, sizeof(visit));
	bfs(V);
	cout << endl;
	
	return 0;
}

갈 길이 멀다... ㅎㅎ 

오랜만에 그리디 ! 

문제

끊어진 기타줄 N개와 M개의 기타 브랜드들이 주어지고 

각 M개의 기타줄을 6개 패키지로 구매할때와 낱개로 구매할때 1개 가격이 주어진다.

모든 브랜드들을 고려해 가장 저렴하게 구매할 수 있는 가격을 출력하면 된다!

처음에 한 브랜드만 선택해야 한다 생각하고 구현했다가 틀리고,

패키지로만 구매하는 경우를 고려하지 않아 또 틀렸다!

풀이

if __name__ == '__main__':
    N, M = map(int, input().split()) # N=끊어진줄, M=브랜드
    minp = mins = 7000
    ps = N // 6 #패키지
    p = N % 6   #낱개

    for i in range(M):
        pak, sol = map(int,input().split())
        minp = min(minp,pak) 
        mins = min(mins,sol)
        tmp = min(minp*ps+mins*p, mins*N, minp*(ps+1))

    print(tmp)

결과