알고리즘
접근
- DFS로 풀 수 있겠다고 생각
- 어떤 노드에 방문하면 다음에 방문할 수 있는 노드에 현재 노드의 자식들을 추가
- 양의 수와 늑대의 수가 같아지면 해당 노드의 방문 취소
class Solution {
private final int SHEEP = 0;
private final int WOLF = 1;
public int solution(int[] info, int[][] edges) {
Map<Integer, Node> nodes = new HashMap<>();
for (int i = 0; i < info.length; i++) {
nodes.put(i, new Node(i, info[i]));
}
for (int[] edge : edges) {
Node parent = nodes.get(edge[0]);
Node child = nodes.get(edge[1]);
if (parent.left == null) {
parent.setLeft(child);
} else {
parent.setRight(child);
}
}
Node root = nodes.get(0);
LinkedHashSet<Node> nexts = new LinkedHashSet<>();
if (root.left != null) {
nexts.add(root.left);
}
if (root.right != null) {
nexts.add(root.right);
}
return search(root, nexts, 0, 0);
}
private int search(Node node,LinkedHashSet<Node> next, int sheepCnt, int wolfCnt) {
if (node.TYPE == SHEEP) {
sheepCnt++;
} else {
wolfCnt++;
}
if (sheepCnt == wolfCnt) {
return 0;
}
int max = sheepCnt;
for (Node nextNode : next) {
LinkedHashSet<Node> copied = new LinkedHashSet<>(next);
copied.remove(nextNode);
if (nextNode.left != null) {
copied.add(nextNode.left);
}
if (nextNode.right != null) {
copied.add(nextNode.right);
}
max = Math.max(max, search(nextNode, copied, sheepCnt, wolfCnt));
}
return max;
}
class Node {
final int NUMBER;
final int TYPE;
Node left;
Node right;
Node parent;
public Node(int NUMBER, int TYPE) {
this.NUMBER = NUMBER;
this.TYPE = TYPE;
}
public void setLeft(Node left) {
this.left = left;
left.setParent(this);
}
public void setRight(Node right) {
this.right = right;
right.setParent(this);
}
private void setParent(Node parent) {
this.parent = parent;
}
}
}반성
- 이진 트리라는 것에 사고가 얽매여서 preOrder, postOrder로 어떻게 풀 지에 대해 고민함
- 최대로 양을 가져오려면 연속된 늑대에 대해서 어떻게 처리해야 할지 고민함
- 완전탐색으로 풀어야 할 것 같은데 기존의 방문을 어떻게 취소할 지 고민함
그래프 탐색의 근본적인 해결법에 대해 다시 생각해볼 필요가 있음
- 현재 노드에서 다음 노드로 갈 수 있는 노드는 무엇인가?
- 다음에 갈 수 있는 노드는 현재 그래프와 인접해있을 필요가 없음 -> 이전에 어떤 노드를 방문했다면 그 노드의 자식들은 나중에 언제든지 방문 가능하다.
토큰
기존의 로그인에선 서버가 세션을 가지고 세션키를 클라이언트에게 쿠키로 부여해줬다.
쿠키를 사용할 수 없는 환경에서 인증 문제를 해결한 것이 토큰이다.
토큰은 사용자의 정보에 추가적으로 붙는 데이터이다.
사용자 로그인 -> DB의 사용자 테이블에서 토큰 조회 -> 클라이언트에게 토큰 전송
이제 이 로그인 사용자로부터의 토큰을 DB에 조회에서 유효한 사용자를 찾아내고 요청을 처리하는 것이다.
JWT
이전의 토큰의 단점은 인증 사용자에 대한 처리를 할 때마다 DB에 접속을 해야한다는 것이다.
JWT는 토큰 자체에 사용자 정보를 담아서 서버가 요청자의 토큰에서 바로 데이터를 얻는 방식이다.
사용자 로그인 -> 서버는 사용자정보를 시크릿키로 토큰화하여 발급
이 토큰을 복호화하여 내용을 알아내는 것은 매우 간단하고 클라이언트에서의 변조는 충분히 가능하다. 하지만 서버의 시크릿키를 모르는 이상 서버에 있어서 유효한 토큰을 클라이언트가 만들어 내는 것은 불가능하다.
애초에 해커는 서버의 시크릿 키를 모르기 때문에 액세스 토큰을 만드는 것조차 불가능하다.
결론
JWT의 페이로드를 읽는 것은 base64 디코딩하면 쉽게 알아낼 수 있다. 그러나 유효성을 위해선 시크릿 키를 알아야만 한다.
JwtProvider(jwt의 관련 작업 담당)
@Component
public class JwtProvider {
private SecretKey cachedSecretKey;
@Value("${custom.jwt.secretKey}")
private String secretKeyPlain;
private SecretKey _getSecretKey() {
String keyBase64Encoded = Base64.getEncoder().encodeToString(secretKeyPlain.getBytes());
return Keys.hmacShaKeyFor(keyBase64Encoded.getBytes());
}
public SecretKey getSecretKey() {
if (cachedSecretKey == null) cachedSecretKey = _getSecretKey();
return cachedSecretKey;
}
public String genToken(Map<String, Object> claims, int seconds) {
long now = new Date().getTime();
Date expire = new Date(now + 1000L * seconds);
return Jwts.builder()
.claim("body", Ut.json.toStr(claims))
.setExpiration(expire)
.signWith(getSecretKey(), SignatureAlgorithm.HS512)
.compact();
}
public boolean verify(String accessToken) {
try {
Jwts.parserBuilder()
.setSigningKey(getSecretKey())
.build()
.parseClaimsJws(accessToken);
} catch (Exception e) {
return false;
}
return true;
}
public Map<String, Object> getClaims(String accessToken) {
String body = Jwts.parserBuilder()
.setSigningKey(getSecretKey())
.build()
.parseClaimsJws(accessToken)
.getBody()
.get("body", String.class);
return Ut.json.toMap(body);
}
}jwt 복호화 사이트
백엔드 희망