코딩하는 eroke

문제

입양간 동물이 2마리 이상인 경우에, 가장 보호기간이 길었던 동물 두마리를 보호기간이 긴 순으로 출력한다.

단순하게 OUTS 테이블의 DATETIME에서 INS 테이블의 DATETIME을 뺀걸 기준으로 LIMIT 2 해서 풀었다.

- 풀이 (MySQL)

SELECT A1.ANIMAL_ID, A1.NAME
    FROM ANIMAL_INS A1, ANIMAL_OUTS A2
    WHERE A1.ANIMAL_ID = A2.ANIMAL_ID
    ORDER BY A2.DATETIME-A1.DATETIME DESC
LIMIT 2

 문제

Milk와 Yogurt 를 동시에 구매한 장바구니 ID를 출력하는 문제이다. 

단순하게 CART_ID를 키로 셀프조인해서 NAME에 Milk와 Yogurt가 있는 CART_ID를 출력했다.

- 풀이 (MySQL)

SELECT C1.CART_ID
    FROM CART_PRODUCTS C1, CART_PRODUCTS C2
    WHERE C1.CART_ID = C2.CART_ID
    AND C1.NAME='Milk'AND C2.NAME='Yogurt'
ORDER BY CART_ID
;

문제

ANIMAL_INS 테이블에서 중성화를 안한 동물이 ANIMAL_OUTS 테이블에서 중성화 된 경우를 출력한다.

ANIMAL_ID를 키로 LEFT JOIN하여 풀었다.

- ORACLE

SELECT A1.ANIMAL_ID, A1.ANIMAL_TYPE, A1.NAME
    FROM ANIMAL_INS A1 LEFT JOIN ANIMAL_OUTS A2
    ON A1.ANIMAL_ID = A2.ANIMAL_ID
    WHERE A1.SEX_UPON_INTAKE LIKE 'Intact%'
    AND A2.SEX_UPON_OUTCOME IN ('Spayed Female','Neutered Male')
ORDER BY ANIMAL_ID
;

- MySQL

SELECT i.ANIMAL_ID, i.ANIMAL_TYPE,i.NAME
    FROM ANIMAL_INS i, ANIMAL_OUTS o
    WHERE i.ANIMAL_ID=o.ANIMAL_ID 
    AND i.SEX_UPON_INTAKE LIKE 'Intact%' 
    AND (o.SEX_UPON_OUTCOME LIKE 'Spayed%' 
    OR o.SEX_UPON_OUTCOME LIKE 'Neutered%')
ORDER BY ANIMAL_ID
;

문제

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

가지고있는 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)

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

공부할게 넘 많아~~~~

문제 (2019 KAKAO BLIND RECRUITMENT)

record 문자열배열을 입력받을 때 사용자가 들어오고 나간 이력을 출력하는 문제이다.

닉네임은 변경할 수 있고 최종적으로 변경된 닉네임으로 결과를 출력한다.

풀이

def solution(record):
    dic={}
    res=[]
    id=[]
    
    for i in range(len(record)):
        s = record[i].split()

        if s[0]=='Enter':
            res.append(s[1]+'님이 들어왔습니다.')
            dic[s[1]]=s[2] #id별 이름저장
            id.append(s[1])

        elif s[0]=='Leave':
            res.append(s[1]+'님이 나갔습니다.')
            id.append(s[1])

        elif s[0]=='Change':
            dic[s[1]] = s[2] #이름변경

    for j in range(len(res)):
        tmp=dic[id[j]]
        res[j]=res[j].replace(id[j],tmp)
        
    return res

딕셔너리로 id당 바뀌는 닉네임을 관리하고 사용자가 채팅방에 들어오고 나갈때마다 

'id님이 들어왔습니다/나갔습니다' 로 저장해서 마지막에 id 부분을 최종 닉네임으로 바꿨다.

저 replace() 부분을,,, 좀더 좋은 방법으로 쓸 수 있을 것 같긴한데..

어쨌든 한번에 성공했더니 기분은 좋균 ㅎㅎ

이번주는 구현 위주로 풀고 담주부터 진짜진짜 알고리즘 공부해야지;;

문제

방번호에 필요한 세트 수 를 출력하면 된다. 한 세트는 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;
}

갈 길이 멀다... ㅎㅎ